一斉射撃問題

一斉射撃問題は、計算機科学とセル・オートマトンにおける問題の一つである。この問題の目標は、一つのセルのみが活動している状態から始めて、最終的に全てのセルが同時に特定の状態に到達するように、セル・オートマトンを設計することである。 この問題は1957年にジョン・マイヒルによって初めて提案され、1962年にエドワード・ムーアにより解法とともに出版された。

問題

一斉射撃問題 (firing squad synchronization problem) という名前は、現実世界の銃殺隊 (firing squad) の類推から来ている: この問題の目標は、将校の指令により全ての兵士らが同時にライフルを発砲できるような規則集を考えることにある。

より形式的に言えば、これはセル・オートマトンを設計する問題である。セル・オートマトンとは、一直線に並んだ有限オートマトンの列(これら一つ一つを「セル(細胞)」と呼ぶ)である。各セルは1ステップごとに別の状態に遷移するが、その状態は、隣接する2つのセルと自分自身の直前の状態のみから計算される。一斉射撃問題の場合、この列は有限個のセルからなり、どの位置のセルも同じ規則に従って遷移する。ただし、両端のセルは隣接セルを1つしか持たないため、異なる規則を使ってよい。

セルの状態集合の中には、3つの特別な状態、「アクティブ」「休止」「発砲」が含まれる。セルの状態遷移関数は、隣接セルが休止状態で自身も休止状態なら、次の状態も休止状態でなければならない。初期状態、つまり時刻 t = 0 においては、左端以外の全てのセルは休止状態であり、左端(将軍)はアクティブ状態である。この問題の目標は、どんなにセルの数が多くても、ある時刻 t で全てのセルが発砲状態であり、時刻 t より前に発砲状態になってしまうセルが一つもないように、遷移関数を設計することである。

解法

一斉射撃問題に対する最初の解法は、ジョン・マッカーシーとマービン・ミンスキーにより、ムーアの「順序機械」の一部として出版された。 彼らの解法には、兵士の列上を伝搬する2つの波が登場する。2つの波のうち、一方はもう一方の3倍の速さで移動する。速いほうの波は列の端で跳ね返り、列の中央で遅いほうの波と衝突する。そこで、2つの波は前後それぞれ、計4つの波に分割される。これにより兵士の列は2等分されたことになる。等分された各列について同じ現象が発生し、1人ずつに分割されるまで繰り返される。この時点で、全ての兵士が発砲する。この解法は n 人の兵士に対して 3n 単位時間を必要とする。

最小時間を達成する解法 (兵士 {{mvar|n}} 人に対して 2n − 2 単位時間)を最初に発見したのは英一 後藤 (1962) だが、彼の解法は約百万の状態を必要とするものであった。 Waksman (1966) がこれを16状態まで改善し、 Balzer (1967) がさらに8状態まで減らした上で、4状態の解法がないことを示したと主張した。その後、Peter SandersはBalzerの探索方法が不完全であったことに気付いたが、正しい方法で探索した結果、4状態の解法がないことを再確認することができた。現在知られている最良の解法は6状態で、 Jacques Mazoyer (1987) により与えられた。5状態の解法があるかどうかは未だに知られていない。

最小時間の解法では、将軍は右方にシグナル S₁, S₂, S₃, ..., S_i を速度 1, 1/3, 1/7, ..., 1/(2 ⁱ⁻¹ − 1) で送信する。シグナル S₁ は列の右端で反射し、 S_i (i ≥ 2) は n/2 ⁱ⁻¹ 番目のセルで反射する。 S₁ が反射するとき、右端に新たな将軍が生成される。この位置からは、補助的な状態を用いて、シグナル S_i が左向きに伝搬される。シグナルが右に2ステップ移動するたびに、このシグナルは補助的な左向きのシグナルを送信する。 S₁ は速さ1で自律的に移動するが、より遅いシグナルたちは、補助的なシグナルを受け取ったときだけ移動する。

一般化

一斉射撃問題は多くの異なる種類のセル・オートマトンに一般化されてきた。例えば、 ([[#CITEREF|]]) では高次元の配列に一般化されている。初期条件の異なる亜種も検討されている ([[#CITEREF|]])。

一斉射撃問題の解法は他の問題にも適応させられる場合がある。例えば、 Patrick Fischer (1965) は、一斉射撃問題に対する初期の解法をもとに、素数を生成するセル・オートマトンのアルゴリズムを設計した。

参考文献

• Balzer, Robert (1967), “An 8-state minimal time solution to the firing squad synchronization problem”, Information and Control 10 (1): 22–42, doi:10.1016/S0019-9958(67)90032-0 .
• Fischer, Patrick C. (1965), “Generation of primes by a one-dimensional real-time iterative array”, Journal of the ACM 12 (3): 388–394, doi:10.1145/321281.321290 .
• Goto, Eiichi (1962), A minimal time solution of the firing squad problem, Dittoed course notes for Applied Mathematics 298, Cambridge, MA: Harvard University, pp. 52–59 . As cited by Waksman (1966).
• Kobayashi, Kojiro; Goldstein, Darin (2005), “On formulations of firing squad synchronization problems”, Unconventional Computation, Lecture Notes in Computer Science, 3699, Springer-Verlag, pp. 157–168, doi:10.1007/11560319_15, http://www.cecs.csulb.edu/~daring/research/formulations.pdf .
• Mazoyer, Jacques (1987), “A six-state minimal time solution to the firing squad synchronization problem”, Theoretical Computer Science 50 (2): 183–238, doi:10.1016/0304-3975(87)90124-1 .
• Moore, F. R.; Langdon, G. G. (1968), “A generalized firing squad problem”, Information and Control 12 (3): 212–220, doi:10.1016/S0019-9958(68)90309-4 .
• Shinahr, Ilka (1974), “Two- and three-dimensional firing-squad synchronization problem”, Information and Control 24 (2): 163–180, doi:10.1016/S0019-9958(74)80055-0 .
• Waksman, Abraham (1966), “An optimum solution to the firing squad synchronization problem”, Information and Control 9 (1): 66–78, doi:10.1016/S0019-9958(66)90110-0 .
• Wolfram, Stephen (2002), “Firing squad synchronization”, A New Kind of Science, Wolfram Media, p. 1035, ISBN 1-57955-008-8, http://www.wolframscience.com/nksonline/page-1035b-text .

外部リンク

• Weisstein, Eric W. "Firing Squad Problem". mathworld.wolfram.com (英語).