2次元一般化一斉射撃アルゴリズムについて

スポンサーリンク

概要

論文の詳細を見る
2次元セル空間に対する一斉射撃アルゴリズムの設計例は,1次元アレイと比較して非常に少ない.本稿では,2次元セル空間上の任意の位置に将軍セルを配置した2次元一般化一斉射撃問題について考察し,14状態の同期アルゴリズムを提案する.2次元セル空間上ではSzwerinski[1982]による25600状態の最適時間アルゴリズムが,知られている唯一の一般化一斉射撃アルゴリズムである.本稿で提案する一般化一斉射撃アルゴリズムの動作時間は,サイズがm×nの長方形アレイに対して,m+n+max(r+s,m+n-r-s+2)-4ステップであり,最適時間よりもmax(r+s,m+n-r-s+2)-max(m,n)+min(r,m-r+1)+min(s,n-s+1)-3ステップ遅いものとなっている.セル当たりの内部状態数が14と非常に少ない点が特徴である.ここで,(r,s)はt=0時における将軍の位置である.計算機上への実装結果も示す.
社団法人電子情報通信学会の論文
2002-03-05

著者

関連論文

もっと見る

スポンサーリンク