如何將TSP轉化爲最小哈密爾頓路徑？

Question

我正試圖解決這個問題http://coj.uci.cu/24h/problem.xhtml?abb=1368。

經過大量研究和花費大量時間後，我能夠實現TSP的分支和綁定算法，該算法獲取路徑通過所有點並返回開始。

我的想法是從通道中取出最長邊我會得到答案，只是當我完成了我的算法，我發現這是不是在所有情況下都是這樣，看完了這個問題：Minimal Distance Hamiltonian Path Javascript

我找到了一些答案，說在每個其他點上添加一個距離爲零的虛擬點，然後移除它就可以解決問題，但我不知道具體的細節。我已經添加了這個虛擬點，現在取而代之的是26.01，現在它是16.23的答案。我還沒有刪除虛擬點，因爲我不明白「添加虛擬點的全部要點」。

你能指導我解決這個問題嗎？還是採用另一種方法而不是TSP更好？

Answer 1

虛擬點允許您在任意大的距離處在兩端之間建立連接。在TSP中，兩端也必須彼此非常靠近以使總距離最小化。在你的路徑問題中，這個要求不存在，所以TSP最優是主觀的約束，對於你的問題是無效的，因此對你的路徑問題可能不是最佳的。

如果您引入一個虛擬點（或將它想象成一個快捷方式，一個蟲洞），您的端點可能相距很遠，而不會影響距離。