ダイクストラとA *を比較するにはどうすればよいですか？

Question

私はGPSシステムを開発しています。その目的は、問題を解決するためにより適切なアルゴリズムを開発することです。私はDijkstraとA *を使用しています。私の報告書では、その周りにいくつかの理論を作り、どれが最良かを示す必要があります。

私は、頂点とエッジ（ストリート）がいっぱいのマップを持っています。なぜ、どちらが他のものよりも優れているのか、理由について両方のアルゴリズムを比較する方法を知りたいのですが。

私はDijkstraを実行するとすべての頂点のパスが得られるので、これは私が知りたい点の間のパスを増やしても同じですテストA *。私に匹敵する言葉を得る方法はありますか？

Answer 1

スターは、基本的にダイクストラの情報に基づいたバリエーションです。また、スターは幅優先探索を使用して検索を高速化し、貪欲なアプローチになります。

最終コスト=移動コスト+ヒューリスティックは、上記の式は、Aスターアルゴリズムに使用される

を要します。それはDijkstraのアルゴリズムに似ています。だから、それを速度と比較することができます。 Nが増えると、A Starを使うのは最高ではないでしょう。できるだけ最適パスを選択するのは、次の2つの条件の場合です。

1. 推定コストは常に実際のコストよりも低くなります。
2. 解決策を見つけて表現するのに十分なメモリがあります。

これは、別のスタックオーバーフローの質問にダイクストラ&星間違いと利点を説明しています。