一斉射撃問題
一斉射撃問題（いっせいしゃげきもんだい）は、計算機科学とセル・オートマトンにおける数学パズル的な問題の一つである。この問題の目標は、一つのセルのみが活動している状態から始めて、最終的に全てのセルが同時に特定の状態に到達するように、セル・オートマトンを設計することである。 この問題は1957年にジョン・マイヒル（en:John Myhill）によって提案された。出版物としては、1964年に[1]、エドワード・ムーア（en:Edward F. Moore）[2]の編集による、この問題が解法とともに収録された文献集が出版されている。
問題
[編集]一斉射撃問題 (firing squad synchronization problem) という名前は、現実世界の銃殺隊 (firing squad) の類推から来ている: この問題の目標は、銃殺隊のように、1人の「将校」の「指令」から始まって、全ての「兵士」が同時に[3]ライフルを発砲するような、セル・オートマトンを構成することである。
以下ではより形式的に記述する。これは1次元のセル・オートマトン、すなわち、一直線に並んだ有限オートマトンの列であり、その一つ一つのオートマトンを「セル(細胞)」と呼ぶ。
他の種類の1次元セル・オートマトンでも一般的なルールとしては、各セルは離散的な状態を持ち、1ステップごとに同時に（一斉に）それぞれの次の状態に遷移する。各セルの次の状態は、自分自身のその時の状態と隣接する2つのセルの状態とのみから計算される。というルールがある。
一斉射撃問題では、さらに、全体は連続した有限個のセルからなり[4]、どの位置のセルも同じ規則に従って遷移する（端については、後述する制限を除いて、特別扱いがあってよい）。
セルの状態には、3つの特別な状態、「休止」「指令」「発砲」が問題の側で用意される（解答者は必要なだけ状態を追加して、解答を考える）。前述のように、どの位置のセルも同じ規則に従って遷移しなければならない。すなわち、全てのセルは全く同じ状態遷移関数を持たなければならない[5]。初期状態、つまり時刻 t = 0 においては、片方の端のセル以外の全てのセルは「休止」であり、片方の端の1個のセル（「将校」などと呼ばれる）のみが「指令」である。[6]
この問題の目標は、どんなにセルの数が多くても[7]、ある時刻 t で全てのセルが「発砲」状態であり、かつ、時刻 t より前に発砲状態になってしまうセルが一つもないような、状態遷移関数を設計することである。
ただし、（初期状態から全体で一緒に遷移する、という自明で面白みのない解を防ぐものとして）次のような制限を設ける。
- セルは、自身が「休止」で両方の隣接セルも「休止」の場合は、次も「休止」でなければならない
- 「将校」の反対側の端のセルの場合は、このルールの「両方の隣接セルも」を、「唯一の隣接セルが」とする（隣がいないことを利用して、あたかも「将校のダミー」のように振る舞うような遷移は禁止される）
また、あるセルの影響は1ステップでは隣接するセルにしか及ばないことから、このセル・オートマトンにおける「光速 (セル・オートマトン) 」は「1セル/1ステップ」である
解法
[編集]一斉射撃問題に対する最初の解法は、ジョン・マッカーシーとマービン・ミンスキーにより与えられ、ムーアの Sequential Machines: Selected Papers[8]に収録されて出版された。これは最もオーソドックスな解法であり、兵士の列上を伝搬する2つの「波」が基本的な役割を果たす。1つめの波は「光速」で、もう1つの波はその1/3の速度で伝搬する。片方の端からそのような2つの「波」が発生し、速いほうの波が反対側の端で跳ね返った後、遅いほうの波と衝突した瞬間のことを考えてみよう。その時、兵士の数をnとすると1.5nステップが経過していて、衝突はちょうど中央で起きている。これにより兵士の列は2等分されたことになる。そこで2つの波をそれぞれ、計4つの波に分割し、左右が鏡像になるように同様に繰り返すようにする。等分された各列について再帰的に同様の現象が発生し、最終的に1人ずつに分割されるまで繰り返されたならば特別な状態遷移に入り、全ての兵士が同時に発砲する。この解法はn人の兵士に対して3nステップ前後を必要とする。
最小時間を達成する解法 (兵士 n 人に対して 2n − 2 単位時間)を最初に発見したのは後藤英一(1962)だが、彼の解法は比較的多数[9]の状態を必要とするものであった。 Waksman (1966) がこれを16状態まで改善し、 Balzer (1967) がさらに8状態まで減らした上で、4状態の解法がないことを示したと主張した。その後、ピーター・サンダースはBalzerの探索方法が不完全であったことに気付いたが、正しい方法で探索した結果、4状態の解法がないことを再確認することができた。現在知られている最良の解法は6状態で、 Jacques Mazoyer (1987) により与えられた。5状態の解法については、存在するかもしれないし不可能かもしれないが、いずれともまだわかっていない。
最小時間の解法では、将軍は右方にシグナル S1, S2, S3, ..., Si を速度 1, 1/3, 1/7, ..., 1/(2 i−1 − 1) で送信する。シグナル S1 は列の右端で反射し、 Si (i ≥ 2) は n/2 i−1 番目のセルで反射する。 S1 が反射するとき、右端に新たな将軍が生成される。この位置からは、補助的な状態を用いて、シグナル Si が左向きに伝搬される。シグナルが右に2ステップ移動するたびに、このシグナルは補助的な左向きのシグナルを送信する。 S1 は速さ1で自律的に移動するが、より遅いシグナルたちは、補助的なシグナルを受け取ったときだけ移動する。
ファインマンが、この最小時間解について（自力で）解こうとすることが「魅力的な問題であり」「しばしば飛行機の中でこの問題を解こうとして時間をつぶしている」が「まだ解いていない」と、『ファインマン計算機科学』に書かれている[10]。
一般化
[編集]一斉射撃問題は多くの異なる種類のセル・オートマトンに一般化されてきた。例えば、Shinahr (1974)では高次元の配列に一般化されている。初期条件の異なる亜種も検討されている(Kobayashi & Goldstein 2005)。
一斉射撃問題の解法は他の問題にも適応させられる場合がある。例えば、 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.
- 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.
- 野口健一郎 (2001), "<原報>一斉射撃問題を解いてみる : 分かりやすい 8 状態最少時間解まで"
注
[編集]- ^ 英語版ではこの部分に in 1962 とあるのだが、別の部分に published in Sequential Machines by Moore. とあり、該当するタイトルの書籍は、ACMの文献データベース等を見る限り（そのソースがAmazonの古書情報のようにも見えるため不安はあるが）1964年となっているので、ここでは1964年とする。
- ^ 「ムーア近傍とノイマン近傍」 (en:Moore neighborhood, en:Von Neumann neighborhood) や「ムーア・マシンとミーリ・マシン」のムーアである。
- ^ 銃殺刑は一般に、それを執行する兵士の心理的負担を軽減するため、多数の兵士のうち一人にだけ実砲が、他には空砲が渡され、それを全員が同時に射撃する、という手続きによって執行される。
- ^ 一般的にはセル・オートマトンでは、無限に続く1次元の列を考えることも多い。
- ^ 細かくは他に、関数はセルの個数（「兵士」の人数）に依存するものであってはならず、任意の自然数個のセルの場合において、題意を満たすよう機能するものでなければならない、というルールもある。
- ^ なお厳密には、「指令」は単に片方の端にあるセルの、他と異なる初期状態という以上の意味はない。状態遷移関数の設計上の都合によっては、直感的に見て「指令」とは感じられないような他のセルの他の状態と共通の状態としてもよい。
- ^ 少ない場合についても考えるのもよいが、初めのうちは数個以上を前提としたほうがいいだろう。
- ^ Sequential Machines: Selected Papers https://dl.acm.org/citation.cfm?id=1102050
- ^ これについてネット等ではthousandsないしmillionsといった表現が見られることもあるが、実際の検討によればそんなに多数を必要とはしない。『一斉射撃問題を解いてみる : 分かりやすい 8 状態最少時間解まで』で示されているナイーブな検討例では、25状態となっている。
- ^ 岩波『ファインマン計算機科学』 p. 48
外部リンク
[編集]- Weisstein, Eric W. "Firing Squad Problem". mathworld.wolfram.com (英語).