レッスン
理論 — 経路探索アルゴリズム・ビジュアライザー
ドロップダウンにある4つのアルゴリズムのうち、3つは本質的に同じアルゴリズムです。これらはすべて、探索待ちのマスを1つの式 f(n) = g(n) + h(n)（ここまでのコスト ＋ 残りの推定コスト）で順位付けしており、2つの項のどちらを残すかだけが異なります。h を除外すればダイクストラ法になり、g を無視すれば貪欲最良優先探索になります。4つ目の幅優先探索（BFS）は、すべてのステップのコストが等しい場合にダイクストラ法が帰着する姿です。
各記号の意味
g(n)- スタートからマス n までの、これまでに発見された最安経路のコストです。縦横の移動コストは
1、斜めの移動コストは√2となります。これは移動を1回と数えるのではなく、距離（長さ）として測定するためです。 h(n)- ゴールまでに予想される残りコストの推定値です。ダイクストラ法と幅優先探索では単に使われていないだけでなく、ゼロになっています。これこそが、これらのアルゴリズムが項を1つ欠いた同じ式であることを示しています。
f(n)- 順位付けのキーです。
fの値が最も小さいマスが次に探索されます。グリッドの上部には、現在のマスの具体的な数値が代入されて表示されるため、アルゴリズムが今行った選択を視覚的に確認できます。 frontier- 琥珀色のマスで、発見済みですが未探索のものです。展開したノード数はこの集合から抜け出たマスの数をカウントするため、解の質ではなく処理量の指標となります。
公式の導き方
- アルゴリズムを選ぶ前に、「最短」が何を意味するかを定義しておきましょう。経路のコストは各ステップの長さの合計です。縦横の移動は
1、斜めの移動は√2となります。マスの数を数えるのではなく、距離を加算します。 - 次に、4つすべてのアルゴリズムで共通のメインループを行います。フロンティアからマスを1つ取り出して訪問済みにし、通行可能な隣接する各マスに対して更新された
gの値とともにフロンティアへ追加します。このループ処理の中には、ヒューリスティック、ゴールの方向、あるいは選択したアルゴリズムに関する言及が一切含まれていないことに注目してください。 - したがって、残された唯一の決定事項はどのマスを取り出すかであり、それはたった1つの式で表されます。
g + hで順位付けすればA*探索になります。h = 0に設定すると、ここまでのコストのみで順位付けされます。これがダイクストラ法であり、ゴールの場所を知らないため同心円状に外側へ広がっていきます。逆にgを無視すると推定値のみで順位付けされます。これが貪欲最良優先探索であり、まっすぐゴールに向かって突き進み、たどり着いたルートをそのまま採用します。 - 幅優先探索（BFS）は順位付けを一切行わず、先入れ先出しで処理します。斜め移動を許可をオフにすると、すべてのステップのコストがちょうど
1になるため、マスが追加された順番こそがgの値が増加する順番となります。したがって、幅優先探索はダイクストラ法とまったく同じ順序で探索を行います。グリッドを再生成せずに確認できます。2つのアルゴリズムを切り替えても、展開したノード数はまったく変化しません。斜め移動をオンにすると、斜め移動のコストが1ではなく√2になるため、追加順序とコストの上昇順が一致しなくなり、この理屈は成り立たなくなります。
表示の読み方
優先度スコアはグリッドの上部に表示され、現在のマスの g と h の値が代入されているため、直前の選択を生み出した順位付けを読み取ることができます。その下には、展開したノード数と経路の長さという2つのカウントが表示されます。琥珀色はフロンティア、インディゴは探索済みを表します。アルゴリズムを変更しても、新しいグリッドが生成されるわけではありません。それこそが比較に価値をもたらす理由です。同じ4方向移動の配置において、ダイクストラ法の展開したノード数がA*探索より小さくなることはなく、貪欲最良優先探索のノード数はどちらのほんの一部に過ぎません。
- 前提
- ステップのコストが負にならないこと、および探索の実行中にグリッドが変化しないことを前提としています。スタートは常に左上のマス、ゴールは右下のマスです。マスの処理完了（クローズ）は確定的なものであり、ループ内で再検討されることはありません。すべてのステップが非負の値を加算するため、後からより安く到達できるルートが現れることはなく、これによって安全性が保証されています。
- 成り立たない場合
- 展開したノード数は最も劇的に変化する数値ですが、これは解の質を示す指標ではありません。貪欲最良優先探索を選んでみてください。同じグリッド上でA*探索が探索する量のほんの一部しか探索しませんが、多くの配置でより長い経路の長さを返します。グリッドを何度か新規生成して、2つのカウントが反対方向に動く様子を観察してみてください。調べたマスが少ないというのは、アルゴリズムがどれだけ効率よく働いたかについての主張であり、得られた解の良さについての主張では決してありません。
学習の道すじ
秒ではなく仕事量を数える
参考文献 (3)
- Where A*, the f = g + h scoring and the admissibility condition were introduced: P. E. Hart, N. J. Nilsson & B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths." IEEE Transactions on Systems Science and Cybernetics 4, 100–107, 1968.
- And the algorithm A* generalises, for comparison in the dropdown: E. W. Dijkstra, "A note on two problems in connexion with graphs." Numerische Mathematik 1, 269–271, 1959.
- The fourth option in the dropdown, and the wavefront it spreads: E. F. Moore, "The shortest path through a maze." Proceedings of an International Symposium on the Theory of Switching, Part II, 285–292. Harvard University Press, 1959.