使用旅行推銷員求解器來確定哈密頓路徑

這是一個項目，我被要求爲旅行推銷員優化問題以及哈密爾頓路徑或循環決策問題實施啓發式。我不需要執行本身的幫助，但對我要進入的方向有疑問。使用旅行推銷員求解器來確定哈密頓路徑

我已經有了一個基於遺傳算法的TSP啓發式：它假定一個完整的圖，以一組開始隨機解決方案作爲一種人口，並致力於改善人口數代。我是否也可以用它來解決哈密頓路徑或循環問題？我不想優化來獲得最短路徑，而只想檢查是否有路徑。

現在任何完整的圖形都會有哈密爾頓路徑，所以TSP啓發式將不得不擴展到任何圖形。如果兩個城市之間沒有路徑，則可以通過將邊設置爲某個無窮大值來完成此操作，並返回第一條有效哈密爾頓路徑。

這是正確的方法嗎？或者我應該使用哈密頓路徑的不同啓發式嗎？我主要關心的是這是否是一種可行的方法，因爲我可以確定TSP優化是有效的（因爲你從解決方案開始並改進它們），但如果哈密爾頓路徑決策者在固定數量的代中找到任何路徑則不會。

我認爲最好的方法是自己測試一下，但是我受到時間的限制，以爲在走下這條路線之前我會問這個問題......（我可以找到哈密頓路徑的另一種啓發式方法）

來源

2009-06-04 Firas Assaad

不是一個答案，但下面的漫畫可能會提升你的精神： http://xkcd.com/399/ – samoz 2009-06-04 15:47:48

我會在項目演示中使用它。：D – 2009-06-04 15:49:02

不知道如果你得到一個答案。簡單的技巧是添加一個距離爲零的虛擬點到所有其他點。解決TSP並擺脫虛擬點 - 剩下的是哈密頓路徑。簡單！

來源

2010-01-28 16:04:58 Grembo

兩者都是NP完全問題，所以從定義可以轉換輸入，並使用相同的算法;-)

但基本思路應該工作。當然，您可能需要更改新路徑的生成和成功標準。

編輯： BTW：有一個隨機算法建議： http://en.wikipedia.org/wiki/Hamiltonian_path_problem

來源

2009-06-04 15:52:32

謝謝。即使它起作用了，我可以保證它會嗎？或者它只是一種「大部分時間」起作用的啓發式方法？我也嘗試在Ruby中快速實現隨機算法，但描述不是很清楚。特別是，我不確定這是什麼意思通過pivoting（和簡單地刪除然後添加一個邊緣給出錯誤的結果）。 – 2009-06-04 15:57:50

確保在np問題上找到最佳解決方案的唯一方法是嘗試所有可能的組合。在這裏和那裏有一些小的捷徑，但在大多數情況下，你必須嘗試一切。您的解決方案只是一個近似值，取決於您在運行期間的決策有多好。你可能會得到理想的解決方案，但你也可能陷入局部最優，這不是最好的解決方案。 – 2009-06-05 06:55:59

使用旅行推銷員求解器來確定哈密頓路徑

回答

相關問題