ダイクストラのアルゴリズムとベストファーストサーチ#
ダイクストラのアルゴリズムは、オブジェクトの始点からグラフ内の頂点を訪問して動作します。 そして、最も近い未調査の頂点を繰り返し調べ、その頂点を調査すべき頂点の集合に追加する。 そして、ゴールに到達するまで、出発点から外側へ拡張していく。 ダイクストラのアルゴリズムは、負のコストを持つ辺がない限り、出発点からゴールまでの最短経路を見つけることが保証されている。 (「最短経路」と書いたのは、同等に短い経路が複数存在することが多いからである)。 下図では、ピンクの四角が出発点、青の四角がゴール、茶色の部分はダイクストラのアルゴリズムがどの範囲をスキャンしたかを示しています。 最も明るい青緑色の領域は、出発点から最も遠い領域であり、したがって、探索の「フロンティア」を形成します。
グリーディ ベスト ファースト検索アルゴリズムは、どの頂点がゴールからどれだけ遠いかについて何らかの推定（発見的と呼ぶ）を行っていることを除いて、同様の方法で動作します。 出発点に最も近い頂点を選ぶのではなく、ゴールに最も近い頂点を選ぶのである。 貪欲な最短探索は最短経路を見つけることを保証していない。 しかし、ヒューリスティック関数を用いてゴールに向かう道を非常に速く導くので、ダイクストラのアルゴリズムよりもずっと速く実行される。 例えば、ゴールが開始位置の南にある場合、グリード・ベスト・ファースト・サーチは、南へ向かう経路に焦点を当てる傾向がある。 以下の図では、黄色がヒューリスティック値の高いノード（ゴールまでのコストが高い）、黒がヒューリスティック値の低いノード（ゴールまでのコストが低い）を表しています。 これは、グリーディ ベスト ファースト検索がダイクストラ アルゴリズムと比較して非常に速く経路を見つけることができることを示しています：
ただし、これらの例は両方とも、地図に障害物がなく、最短経路が本当に直線であるという最も単純な場合を示しています。 前節で説明したような凹型の障害物を考えてみよう。 ダイクストラ アルゴリズムはより困難な作業を行いますが、最短経路を見つけることが保証されています。
一方、貪欲探索はより少ない作業で、その経路は明らかに優れてはいません。 ゴールに到達するためのコストだけを考え、これまでの道のりのコストは無視するので、今いる道が本当に長くなっても進み続けます。
両方の長所を組み合わせるのはいいことだと思いませんか。 A* は 1968 年に開発され、Greedy Best-First-Search のような発見的アプローチと Dijsktra’s Algorithm のような形式的アプローチを組み合わせました。 ヒューリスティックなアプローチは通常、最適な答えが得られることを保証せずに、問題を解くための近似的な方法を与えるという点で少し変わっています。 しかし、A*はヒューリスティックの上に構築されており、ヒューリスティック自体は保証を与えてくれませんが、A*は最短経路を保証することができます
。