DijkstraとA *最短ルート

本ブログ作成文は、講義を目指して製作されました。 また、作成された文章の情報も間違っている可能性がありますので、ご注意ください。

タイルごとに移動コストが異なると、単純なBFSだけで最も安い経路を保証できない。 このとき、DijkstraやA *のような最短パスアルゴリズムを使用します。

Dijkstra

開始点から現在までの累積コストが最も小さい頂点を最初に拡張します。

新しい費用=現在までの費用+次の幹線費用

新しい費用が従来の記録よりも小さい場合
距離と前の頂点を更新します。

Priority Queueを使用すると、通常O((V + E) log V)程度に実装できる。 負の幹線があると、すでに確定した最短距離が再び減る可能性があるため、デフォルトのDijkstraを使用しないでください。

A*

A*は出発点からの実際の費用gと目標までの予想費用hを加えて優先順位を決める。

f(n) = g(n) + h(n)

格子ではManhattan DistanceやEuclidean DistanceをHeuristicとして使うことができる。 六角グリッドには、六角座標に合った距離関数を使用する必要があります。

予想コストが実際に残った最低コストを過大評価しない場合、最短経路を保証することができる。 Heuristicが0の場合、A *はDijkstraのように動作します。

どちらを使うか？

1つの出発点で複数の目的地が必要：Dijkstra
1つの目的地まですばやく移動：A *
すべての幹線コストが同じ：BFS

経路探索性能はアルゴリズム名だけでは決定されない。 ネイバー作成コスト、障害物表現、Priority Queue、Heuristic品質も一緒に確認する必要があります。