A*経路探索ビジュアライザー

マンハッタン距離ヒューリスティックを使ったA*経路探索をグリッド上でインタラクティブに可視化。壁を描いてスタート/ゴールを動かし、迷路を自動生成し、探索をステップごとに実行できます。すべてブラウザ内で完結します。

無料登録不要クライアントサイドプライバシーに配慮 Updated 6月 11, 2026

速度

Move the indigo token with ↑ ↓ ← → / WASD (or tap an adjacent cell) from the green start to the red goal. Walls block you.

Moves: Time: 🎉 Reached the goal!

疑似コード

使い方

1 クリック&ドラッグで壁を描画できます。緑のスタート地点や赤のゴール地点はドラッグして移動できます。
2 「Play」を押すと、A*が距離ヒューリスティックを使ってゴールへ向かって進む様子が見られます。
3 「Maze」で瞬時に障害物を生成、または「Step」で1ノードずつ探索を進められます。
4 DijkstraやBFSと比べて、A*がいかに少ないマス目しか探索しないかに注目してください。

このツールを使う理由

マンハッタン距離ヒューリスティックが探索をゴールへまっすぐ引き寄せる様子を確認できます。
A*は非情報探索よりもはるかに少ないノード数で最短経路を見つけ出します。
本ツールとDijkstra/BFSビジュアライザーを切り替えて、探索パターンの違いを比較できます。
すべてブラウザ内で完結します。登録もアップロードも不要です。

よくある質問

A*アルゴリズムとは何ですか?

A*(エースターと読みます)は、フロンティア(探索候補ノード)を f = g + h で並べ替えるベストファースト型の経路探索アルゴリズムです。ここで g はスタート地点からの実コスト、h はゴールまでのコストのヒューリスティックな推定値を表します。

このツールではどのヒューリスティックを使っていますか?

マンハッタン距離(|Δrow| + |Δcol|)を使用しています。これは4方向グリッドにおいて admissible(過大評価しない)ヒューリスティックであり、そのためA*は常に最短経路を見つけることが保証されます。

A*の時間計算量はどれくらいですか?

最悪計算量はDijkstraと同じくO(E log V)ですが、優れたヒューリスティックがあれば実際に探索するノード数は大幅に少なくなります。

どのような場合にA*はDijkstraより優れていますか?

目的地が1つに定まっていて、有用なヒューリスティックが使える場合はいつでもA*が有利です。A*はゴール方向に探索を集中させるのに対し、Dijkstraは全方向を均等に探索します。