接触インベーダーゲームに対するオフラインアルゴリズム(セッション1)
スポンサーリンク
概要
- 論文の詳細を見る
接触インベーダーゲームとは, 各インベーダーが侵入してくるのみで玉を打ってこない, また玉を打つのでなく迎撃機をインベーダに接触させることで, 自陣への侵入を防ぐようなインベーダーゲームである.本稿ではオフラインアルゴリズム, すなわちゲーム開始から終了までの間に飛来する各インベーダーに関する情報が前もって与えられる状況のもとで, インベーダーの侵入数を最小化(迎撃可能インベーダー数を最大化)するような戦略を求める問題を考察し, そのような最適戦略がO(nlogn)の時間計算量で求まることを示す.ここに, nはインベーダー総数である.
- 一般社団法人情報処理学会の論文
- 2005-11-11
著者
関連論文
- リバウンドチューリング機械に関するある性質
- 確率リバウンドチューリング機械
- 確立リバウンドチューリング機械
- 交代リバウンドチューリング機械のリーフサイズ階層性
- 交代リバウンドチューリング機械
- 確率リバウンドオートマタについて
- 2次元確率有限オートマタに関して
- 2方向決定性1カウンタオートマタと対数以下の空間における1ペブル決定性チューリング機械の関係について
- 対数以下の空間量をもつ交代プッシュダウンオートマタについて
- ドント方式の計算について(研究速報)
- 1触手を持つコミュニケーティングPシステムについて(セッション1)
- 全称状態のみを持つ対数以下空間限定1ペブル交代性チューリング機械
- 回転入力を持つ3方向2次元交代性有限オートマタ
- 回転入力を持つ3方向2次元決定性有限オートマタ
- 議席配分法に対する線形時間アルゴリズム (計算機科学基礎理論の新展開)
- D-1-6 基数ソートに基づく選択アルゴリズム(D-1. コンピュテーション)
- パス限定1方向マルチヘッド有限オートマタ
- ジャンケンの計算量(計算量理論)
- 次元確率チューリング機械の空間量下界
- ジャンケンの計算量 (計算理論とアルゴリズムの新展開)
- On the Power of Cooperating Systems of One-way Hybrid Finite Automata (New Developments of Theory of Computation and Algorithms)
- 自己検証非決定性ならびにラスベガスマルチヘッド有限オートマタ
- 2次元スタッキングルーラーオートマトン (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- 空間限定2次元交代チューリング機械の閉包性
- 空間限定2次元確率チューリング機械によって認識される集合族の閉包性
- Optimal Simulation of Two-Dimensional Alternating Finite Automata by Three-Way Nondeterministic Turing Machines
- 対数以下の空間量を持つ交代プッシュダウンオートマタに関するいくつかの考察
- 対数以下の空間量を持つ2方向(1-インクドット)オルタネーティングプッシュダウンオートマタの交代性
- 70+.3rの法則 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 切断オートマトン(セッション1)
- 接触インベーダーゲームに対するオフラインアルゴリズム(セッション1)
- 2次元オルタネーティング o(log log m) 領域計算量クラスの補集合に関する非閉包性(計算量理論とアルゴリズム論文小特集)
- Alternating Automata Characterizations of One-Way Iterative Arrays (Algorithms and Theory of Computing)
- A Note on Two-dimensional Probabilistic Turing Machines (Algorithms and Theory of Computing)
- 1方向シンプルマルチヘッド有限オートマタの検知機能について
- 4分木の線形時間正規化
- 消費税に対する「分割買い」について(アルゴリズムと計算量の理論)
- 2次元マーカオートマトンのある性質 : 3方向チューリング機械による模倣(計算アルゴリズムと計算量の基礎理論)
- A Note on Three-Way Two-Dimensional Alternating Turing Machines
- 2次元交代チューリング機械、交代プッシュダウンオートマタおよび交代カウンターオートマタの空間階層性について
- 二方向検知型2ヘッドと3ヘッドの関係について
- 3次元マルチインクドットオートマトンの基本的な性質
- ルーラーの本数に基づく2次元ルーラーオートマトンの階層性
- 2次元ルーラーオートマトン
- PR4分木の正確な空間計算量について
- シンプル・マルチヘッド・プッシュダウンオートマタについて
- 2次元オルタネイティングo(loglog m)領域計算量クラスの補集合に関する非閉包性(アルゴリズムと計算量理論)
- On the Power of Two-Dimensional Synchronized Alternating Finite Automata