即使跳過幾個城市，TSP的最佳解決方案是否仍然保持最佳狀態？

Question

假設我知道100城市標準旅行推銷員問題的全局最優解。現在，讓我們說推銷員想跳過5個城市。 TSP是否需要重新解決？通過從以前的最佳解決方案中簡單地刪除這些城市而獲得的城市序列是否將成爲新的95城市TSP的全局最優？

Answer 1

更新：用歐幾里德實例取代反例。

偉大的問題。

不，如果你刪除了一些城市，原始城市序列確實是而不是保持最佳狀態。這是一個反例：

節點座標爲：

0 0 
4 0 
4 2 
2.6 3 
10 3 
4 4 
4 6 
0 6 

這裏是最佳之旅：

現在假設我們並不需要訪問節點5.如果我們只是「關閉」原來的巡演，結果巡演的費用爲21.94：

但最佳旅遊有21.44費用：

（如果你想刪除5個城市，而不是1，只是把所有的5個城市併攏上一路）