如何比較Dijkstra和A *？

Question

我正在開發GPS系統。目標是開發更適合於解決問題的算法。我正在使用Dijkstra和A *，現在在我的報告中，我需要圍繞它做一些理論並顯示哪一個最好。

我有一張充滿頂點和邊緣（街道）的地圖，我想知道如何以一種方式比較兩種算法，我可以說明爲什麼一個比另一個好，爲什麼。

我在問這個，因爲當我運行Dijkstra時，它會得到所有頂點的路徑，所以它可能是相同的，即使我增加點之間的路徑，我想知道哪個是我認爲會好的方式測試A *。有什麼方法可以獲得類似的術語？

Answer 1

明星基本上是知道Dijkstra的變化。而明星使用廣度優先搜索來加速搜索，這將是一種貪婪的方法。

最終成本=運行成本+啓發式成本

上述方程被用於A星算法。它類似於Dijkstra的算法。所以，你可以將它與速度進行比較。不過當N增加時，使用A Star不會是最好的。因爲它在兩種情況下儘可能選擇最佳路徑：

1. 估計成本始終低於實際成本。
2. 有足夠的內存可供查找解決方案並表示它。 Dijkstra算法&阿星之間

它在另一個堆棧溢出問題解釋，差異和優勢。