Dijkstra算法VS A *對於權圖

Question

我試圖找出用哪種算法來獲得一個目標節點從給定的起始節點的最低成本路徑。

A ----5---- B ---3--- C 
|   | 
|   /
D ----1-----E ------10------ F 

我一直在尋找到Dijkstra和A *，因爲他們都給這樣的問題提供了最優解決方案。我理解的方式是，Dijkstra只是一個啓發式爲0的A *。我已經實現了Dijkstra算法，但想知道是否可以使用A *。在如上所述的非常簡單的圖中（沒有任何其他信息），是否存在A *可以用來提供比Dijkstra更好的結果的可容許啓發，還是Dijkstra最優化的算法？

Answer 1

如果沒有適合的圖形，那麼你必須選擇Dijkstra算法的內容啓發式的知識。

A *是爲路線圖，其中用於道路距離的約束加上了直接的距離總是比通過其他節點會更短的開發。該約束不適用於一般加權圖。

如果你不知道你的圖形的內容，例如一個附加的約束/啓發式，那麼你必須使用Dijkstra算法

考慮進一步保持這一路線圖圖是如此之大，這是值得使用一個*。 如果你的圖形不是很大，那麼可能它甚至不值得考慮是否找到任何啓​​髮式。這種錯誤的啓發式甚至會讓事情變得更糟。

所以，你可以使用Dijkstra算法，並且只有當你有一個性能問題，你可以開始考慮找一個啓發。