即使跳过几个城市，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个城市并拢上一路）