経路探索の可視化

マス目に壁や重いマスを描き、BFS・ダイクストラ法・A* など 5 種類の経路探索がゴールへの道を探す順番をアニメーションで見せます。迷路の自動生成や、同じマス目での結果の比較もできます。

手数0 / 220

設定

アルゴリズム

マス目の大きさ（変えると最初の配置に戻ります）

速さ（1 秒あたりの手数）

道具

A*: 再生を押すと探索を始めます

同じマス目での比較

行を押すとそのアルゴリズムに切り替えます。探索したマスが少ないほど速く見つけたことになります。

探索したマス	経路の長さ	コスト	最小コスト
846	34	34	○
295	294	294	×
846	34	34	○
185	34	34	○
83	34	34	○

アルゴリズムを選んで「再生」を押すと、スタート（緑）からゴール（赤）までの道を探す様子をアニメーションで見られます。
マス目をドラッグすると、選んだ道具で壁や重いマスを描けます。同じ種類のマスから描き始めると消せます。スタートとゴールはドラッグで動かせます。
「迷路」「ランダムな壁」「ランダムな重いマス」で、マス目を自動で作れます。
最後まで再生した後にマス目を編集したりアルゴリズムを切り替えたりすると、新しい結果がすぐに表示されます。壁を動かしながら経路の変わり方を確かめられます。
下の比較表には、同じマス目で 5 種類のアルゴリズムを動かした結果が並びます。
「1 手」は 1 つのマスを取り出して調べること（経路を描く間は 1 マス描くこと）です。手数のスライダーで好きな場面に移動できます。
キーボードでは Space で再生 / 一時停止、← → で 1 手戻る / 進む、Home で最初へ。マス目にフォーカスがあるときは矢印キーでカーソルを動かし、Enter で道具を使う、S / G でスタート / ゴールを置きます。

g はスタートからそのマスまでのコストです。

アルゴリズム	候補の入れ物	見つかる経路	しくみ
幅優先探索（BFS）	キュー	マスの数が最小（コストは見ない）	スタートから近い順に、波紋のように広がる。重いマスを区別しない
深さ優先探索（DFS）	スタック	最短とは限らない	行き止まりまで一方向に進んでから引き返す。見つかる経路は遠回りになりやすい
ダイクストラ法	優先度付きキュー（g）	コストが最小	スタートからのコスト g が小さい順に調べる。重いマスを避ける
A*	優先度付きキュー（g + h）	コストが最小	g にゴールまでの見積もり h（マンハッタン距離）を足した値が小さい順に調べる。ゴールの方向へ絞って探す
最良優先探索（貪欲法）	優先度付きキュー（h）	最短とは限らない	ゴールまでの見積もり h だけを見て進む。速いが、壁に回り込むと遠回りになる

A* の見積もり h はゴールまでの実際のコストを超えないので、A* はダイクストラ法と同じく最小コストの経路を見つけます。そのうえでゴールの方向を優先するため、調べるマスが少なく済みます。