在完全無向加權圖中查找哈密爾頓路徑與哈密爾頓電路

Question

我有一個完整的帶有權重的圖形（調整矩陣）。我已經建立了一個解決方案，用於在此圖（旅行推銷員問題）中使用分支和界限來查找最小哈密頓電路。我現在堅持要找到具有給定開始和結束節點的最佳哈密爾頓路徑。沒有給定的開始和結束節點，最好的解決方案將是哈密爾頓電路 - 電路中最長的邊緣。

我想不出一個解決方案，而不是簡單的暴力強制找到最佳哈密爾頓路徑與給定的開始和結束節點。請提供一些關於如何解決這個問題的指示。

Answer 1

給定的起始節點和結束節點相當於約束條件，即端節點和起始節點之間的有向邊必須是TSP巡迴的一部分。

所以，你可以簡單地改變你的鄰接矩陣：

• 組從所期望的最終節點，以無限的重量都外出邊緣，除了邊緣到起始節點
• 設置所有傳入邊緣到所需的開始節點到無限重量，除了來自末端節點的邊緣
• 將起始節點到末端節點的邊緣設置爲無限重量（以確保您不會得到相反的解決方案，如果您的鄰接關係可能會有所不同矩陣不對稱）

這與您的實現使用的分支方法非常相似。

Answer 2

在給定的起始節點和結束節點之間除了應該設置爲零的節點之外的每個邊的權重中添加一個大的常量。該常數可以選擇爲N*maxweight其中N是頂點的數量並且maxweight是最大邊緣權重。這保證了給定的邊緣將被包含在電路中。