Dijkstra法 と A*

経路探索アルゴリズム「A*(Aスター)」を分かりやすく教えてください。

Dijkstra 法では「出発点からその点までの実合計距離」が短い点から順に評価していくのに対して、A*法では「出発点からその点までの実合計距離」＋「その点から到着点までの予想距離」が短い点から順に評価をおこないます。ただし「その点から到着点までの予想距離」が「その点から到着点までの実合計距離」を超えていると正しい解が得られないので、たとえば平面地図においては「予想距離」に「直線距離」を用いたりします。なお「予想距離」を全て0とした場合のA*法は、Dijkstra法と同じになります。

A*は「ダイクストラ法の一般化」として捉えられるんだなあ。この二つを直接比較して考えてみたことがなかったのでなんか新鮮だった。

それにしても、ハンゲームにもこういうコミュニティがあったのか。小中学生ばかりという印象しか持ってなかったので驚いた。