経路探索アルゴリズム・ビジュアライザー

f(n)=g(n)+h(n)という式により、A*はこれまでの費用が安く、かつゴールに近いと思われるノードを優先する。hが残りのコストを決して過大評価しない限り、A*は最短経路の保証を維持する。より強い許容的なhを使うほど、不要なセルの探索が減る。アルゴリズムのドロップダウンを切り替えて、ヒューリスティックを外した場合(ダイクストラ法)、これまでのコストを外した場合(貪欲法)、スコアリングを完全になくした場合(BFS)に何が起こるか確認してみよう。

4つのアルゴリズムはまったく同じループを回します。待機リストから最も有望なマスを取り出し(琥珀色のフロンティア)、訪問済み(藍色)として印を付け、その空いた隣接マスをリストに戻します。違うのは「どのマスが最も有望に見えるか」の判断だけです。ポイント:展開したノード数こそが本当のスコアで、藍色のマスが少ないほど、同じゴールへ無駄な作業を減らして到達したことを意味します。

「斜め移動を許可」をマンハッタン・ヒューリスティックと組み合わせると、A* は最短でない経路をこっそり返すことがあります。ここでは斜めの一歩のコストはわずか √2 ≈ 1.41 ですが、マンハッタン距離はそれを 2 として計上します。つまりヒューリスティックが過大評価となり、許容的でなくなり、最適性の保証が失われます。直線距離を決して超えないユークリッド距離に切り替えれば、最短経路が戻ってきます。