問題定義

輸入：

完全無向帶權圖G=（V,E）

|V|=n, |E|=m

對于E中的某條邊e，其長度為c(e)

輸出：

最短哈密頓回路（經過每個節點一次且僅一次的回路）

ps.這是一個NP問題，沒有有效的算法求出它的最優解，但是利用回溯法我們可以得到近似最優解。

舉例詳解

無向帶權圖如下：

構造解空間樹：

按深度優先遍歷這棵樹，每遍歷到一個葉子，就記錄小當前的代價，例如，我們進行1-2-3-4-1的路徑，其代價為30+5+20+4=59，再回溯到1,2節點處，進行1-2-3-4-1的路徑，其代價30+10+20+6=66,66>59，不保留，保留最短路徑，以此類推，最后得出最佳答案。

這里因為沒有路徑的具體約束，因此剪枝算法中只包含限界函數，而沒有約束函數。

總結

以上是生活随笔為你收集整理的回溯法之旅行商问题解题思路详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。