A*探索（ヒューリスティック付き最短経路）

評価値 f(n) = g(n) + h(n) でグリッド上の最短経路を探す。ヒューリスティック h を変えると展開セルがどう変わるかを、ダイクストラ（h=0）と並べて体感します。

ヒューリスティック h

h の重み w（重み付きA*） 1.0×

アニメ速度 14

ドラッグの操作

グリッドをクリック／ドラッグで壁・始点・終点を配置できます（変更すると探索は自動でリセット）。

A* 展開数

—

ダイクストラ展開数

—

削減率

—

経路長（マス）

—

A*（f = g + w·h）— 現在の設定

ダイクストラ（h = 0）— 比較用

始点終点壁展開済み（closed）フロンティア（open）最短経路

A*探索は、各セル n を 評価値 f(n) = g(n) + h(n) の小さい順に展開する最短経路アルゴリズムです。
g(n) は始点からそのセルまでの実コスト、h(n) はそのセルから終点までの推定コスト（ヒューリスティック）です。h が「真の残り距離を超えない」（許容的）なら、A* は必ず最短経路を見つけます。
h = 0 にすると f = g となり、これはダイクストラ法そのものです。終点の方向を全く考えないので四方に均等（扇形）に広がります。h を強くするほど終点方向へ絞り込まれ、展開セルが減ります。

いま何が起きている？

ここがポイント

f = g + h ── 実コスト g と推定コスト h を足した評価値が小さいセルから展開する。
h = 0 はダイクストラ ── 終点を意識しないので四方へ均等に広がり、展開数が最大になる。
h を強める（重み w を上げる）と探索が細くなる ── 終点方向へ絞られ展開数は減るが、w>1 では最短保証が崩れて経路が伸びることがある。
許容的（admissible）な h ── 真の残り距離以下なら最短を保証。グリッドの4方向移動ではマンハッタン距離が許容的で精度も高い。