檢查最佳路徑

我試圖找出我寫的算法是否返回訪問圖中每個節點的最優路徑。我試圖穿過這個圖表，就像你會用草坪割草或者用吸塵器清理你的房子一樣，或者耕田。我找回了一條路，但是有辦法檢查它是否是最優的。是否有我可以用來檢查它的API或在線服務？檢查最佳路徑

我看了Dijkstra和A *算法以及BFS和DFS，但我不知道如何驗證我得到的路徑是最有效的。

給出一個圖表，我如何找到訪問所有節點的最快和最有效的路徑？

感謝

很不幸，這被稱爲旅行商問題的NP困難的問題。

因此沒有已知的多項式時間解。遍歷整個解空間將需要！N次迭代（其中N是節點的數量）。然而，有幾種解決方案可以給你很好的解決方案，如果不是最好的。

我會研究模擬退火作爲一種方法來獲得所有節點之間的短路徑。

2013-08-24 22:00:08

模擬退火是很多樂趣。 –

如果我想要做一些事情，比如尋找真空吸塵器穿過房子或修剪草坪的最佳路徑，該怎麼辦？ – user2643346

退火方法對於冶金學來說似乎最好，並且在山脈中找到最高點，但似乎不太適合從A點到B點訪問所有節點 – user2643346

回答