所有TSP算法是否會提供相同的最佳路徑？

Question

我只是想知道TSP的所有算法是否會給出相同的最佳路線？我認爲這將是這種情況，但實施分支和綁定和A *和他們都給同一輸入的結果非常不同，我只是想知道這是否正常？

Answer 1

我的路線不同，但所有最佳解決方案的成本應該是相同的。

如果您的A *解決方案更昂貴，那麼您的啓發式設計就是錯誤的。 看看wikipedia A* algorithm的證據，它總是找到一個最佳的解決方案。

Answer 2

否。如果存在多於一條最優路線，則不同的算法將無法找到相同的路徑。它取決於實現，我假設它也將取決於你如何標記圖，這樣不同的標號將使相同的算法找到不同的路由。