0
我試圖找出我寫的算法是否返回訪問圖中每個節點的最優路徑。我試圖穿過這個圖表,就像你會用草坪割草或者用吸塵器清理你的房子一樣,或者耕田。我找回了一條路,但是有辦法檢查它是否是最優的。是否有我可以用來檢查它的API或在線服務?檢查最佳路徑
我看了Dijkstra和A *算法以及BFS和DFS,但我不知道如何驗證我得到的路徑是最有效的。
給出一個圖表,我如何找到訪問所有節點的最快和最有效的路徑?
感謝
我試圖找出我寫的算法是否返回訪問圖中每個節點的最優路徑。我試圖穿過這個圖表,就像你會用草坪割草或者用吸塵器清理你的房子一樣,或者耕田。我找回了一條路,但是有辦法檢查它是否是最優的。是否有我可以用來檢查它的API或在線服務?檢查最佳路徑
我看了Dijkstra和A *算法以及BFS和DFS,但我不知道如何驗證我得到的路徑是最有效的。
給出一個圖表,我如何找到訪問所有節點的最快和最有效的路徑?
感謝
很不幸,這被稱爲旅行商問題的NP困難的問題。
因此沒有已知的多項式時間解。遍歷整個解空間將需要!N次迭代(其中N是節點的數量)。然而,有幾種解決方案可以給你很好的解決方案,如果不是最好的。
我會研究模擬退火作爲一種方法來獲得所有節點之間的短路徑。
模擬退火是很多樂趣。 –
如果我想要做一些事情,比如尋找真空吸塵器穿過房子或修剪草坪的最佳路徑,該怎麼辦? – user2643346
退火方法對於冶金學來說似乎最好,並且在山脈中找到最高點,但似乎不太適合從A點到B點訪問所有節點 – user2643346