公制旅行推銷員，強求解決方案的優勢

正常情況下，TSP解決方案是使得邊緣總成本最小的解決方案。公制旅行推銷員，強求解決方案的優勢

但是在我的情況下，我需要解決方案上的特定優勢，無論它的解決方案是否不再優化都無所謂。

然而，包含該邊的所有哈密爾頓週期中獲得的解是最優的，這確實很重要。或者至少有界。

更正式的問題是：給定一個完整的度量圖和一個特定的邊，什麼是哈密爾頓圈，其成本是最小的通過該特定的邊？

編輯：轉換圖可能是一個好主意。但請記住，生成的圖必須仍然是公制和完整的。在這種情況下，非完整圖形相當於非度量圖形，只是認爲缺少的邊緣實際上是過於昂貴的邊緣。這很重要，因爲對於一般距離不能使用polinomial-time算法。如果你很好奇，這個事實的證明是在S. Sahni和T. Gonzalez（1976）的「P完全近似問題」中。

來源

2014-02-12 Paolo.Bolzoni

難道你不能通過將問題分成兩部分來做到這一點嗎？如果必須包含的邊是A-B，則從開始到A的最短路徑，然後從B到最短路徑結束。然後結合這兩條路徑。 – Krease

我的不好，我的意思是循環不是路徑。我編輯過。但是，您如何結合這兩種解決方案？短切？ –

用另一個頂點打破邊緣。 –

如何使邊緣的成本足夠低，使得包含它的哈密爾頓循環不會比不包含哈密頓循環更昂貴？

設S是圖中所有距離的總和。除了固定的邊以外，每邊增加2 * S。這樣，每個包含固定邊的哈密爾頓循環最多會有（N-1）* 2 * S + S的成本，並且每個不包含它的循環的成本至少爲N * 2 * S。由於每個三角形（x，y，z）變爲（x + 2 * S，y + 2 * S，z + 2 * S）或（x，y + 2 * S），所以三角不等式也被保留下來。 S，z + 2 * S）。

來源

2014-02-12 18:32:52 Anton

足夠低可能是一個好主意，但如果不失去三角形不平等，你不能太低。 –

@ Paolo.Bolzoni我編輯了答案，添加了一個保持圖形度量的示例。 – Anton

一個近似算法不能保證找到最短路徑，只有一個足夠接近（比如，最優不超過1 +ε因子）。如果你在解決方案中增加了一個巨大數字的距離，*每條*路徑可能會落在最佳值的1 +ε以內。所以只有你能找到確切的解決方案纔是好事。 –

如果X-Y是邊，則可以引入一個新的頂點Z，使得Z僅連接到X和Y，並去除X-Y。距離（X，Z）+距離（Z，Y）=距離（X，Y）。

來源

2014-02-12 20:26:57 ElKamina

公制旅行推銷員，強求解決方案的優勢

回答

相關問題