神のアルゴリズム – ウィキペディア

神のアルゴリズム （英語 神のアルゴリズム ）は、マジックキューブの最適な解決策に関する議論からの用語です。文言は、英語のグループ理論家ジョン・コンウェイまたはケンブリッジの彼の同僚の一人から来ています。 ^[初め] また、組み合わせやゲーム理論の他の問題にも関連している可能性があります。アルゴリズムはです 神のアルゴリズム 問題やパズルの場合、可能な限り最小のステップまたは列車で常にソリューションを生成する場合。

用語 神のアルゴリズム 構成間の変換を表す、かなり小さく定義された量の「列車」と組み合わせて、有限の数の「構成」をとることができる問題またはパズルを指します。パズルを緩め、一連の列車を使用して、1つまたは複数の特定の特定の「最終構成」（有限数）から任意の開始構成を達成することを意味します。このような引張配列は1つに対応します 解決 パズル。

説明は、いくつかのよく知られているパズルに適用されます。 B.マジックキューブ、ハノイの塔、15パズルなどの機械的な忍耐ゲーム。ソリティアには、宣教師や人食いの問題と同じくらい多くのロジックパズルも含まれています。一緒になって、それらは指示されたグラフとしての数学的モデル性であり、ノット（「ポイント」）の構成、および列車はグラフのエッジ（「矢印」）に対応しています。解く引張シーケンス（パズルの解決策）は、出力から最終的な構成につながるグラフの（指示された）パスに対応します。

アルゴリズムは意味します 解決 彼が入力として任意の初期構成である場合

• パズルを初期構成によって解決できる場合、およびそれ以外の場合は解決策を発行します
• 解決策がないことを出力します。

解決策は意味します 最適な 列車のシーケンスができるだけ短い場合。パズルの解決アルゴリズムが行われます 神のアルゴリズム 常に最適なソリューションを費やしているときに名前が付けられています。 神の数 最後に、最も長い張力シーケンスの長さは、パズルのすべての最適なソリューションの下で定義されます。

本当の「神のアルゴリズム」も必要です 実行可能 ベッド。 H.多くのストレージスペースや時間は必要ありません。多くのパズルを使用すると、すべての開始構成を介してインデックス化された巨大なルックアップテーブルの助けを借りてソリューションをすばやく使用できますが、この手順にはあまりにも多くのストレージスペースが必要です。

完全なソリューションを要求する代わりに、最高の最初のシングルトレインの後に開始構成について尋ねることもできます。個々の列車のアルゴリズムは、最終的な構成まで繰り返すことにより、全体のソリューションのアルゴリズムに変換できます。逆に、個々の列車のアルゴリズムの全体的なソリューションのアルゴリズムも分解できます。

• デビッド・ジョイナー： グループ理論の冒険。 Johns Hopkins University Press（2002）、ISBN 0-8018-6947-1。

1. ↑ VGL。ジェリー・スローカム： キューブ。世界のベストセラーパズルの究極のガイド。秘密 – ストーリー – ソリューション。 ニューヨーク：Black Dog＆Leventhal、2009、S。26。
2. ↑ D.ラトナー、M。ウォーマス： 15パズルの（n x n）拡張のための最短ソリューションを見つけることは扱いにくい 。 Journal of Symbolic Computation 10（1990）、S。111–137
3. ↑ リチャードE.コルフ;ピーター・シュルツェ： 大規模な並列幅最初の検索 （PDF; 104 kb）。 In：人工知能に関するAAAI会議。人工知能3（2005）に関する第20回全国会議の議事録、S。1380–1385、Hier S. 1384–1385（15パズル）、表2（15パズルの深さの関数としての状態）。
4. ↑ ^{a b} アレクサンダー・レインフェルド： 8パズルの完全なソリューションとIDA*でのノード注文の利点。 In：人工知能に関する第13回国際共同会議（1993）、Chambery Savoi、France、S。248–253の議事録。
5. ↑ カルロス・ルーダ：「ハノイパズルの塔に対する最適なソリューション」 （ms word; 33 kb）
6. ↑ 神の数は20です （cube20.org）