如果我缩短最佳TSP解决方案,仍然是最佳的？

Question

让我们有一个包含k个节点的完整无向度量图; 度量图是满足三角不等式的图,因此对于所有节点a,b,c,权重函数w(a,c)小于或等于w(a,b)+ w(公元前).

Wlog让我们说循环:<1,2,3,...,k,1>是该图的最佳TSP解决方案.

我的问题是:如果我从图中删除一个节点(例如第n个)并且我快速跳过循环,那么结果循环仍然是最佳的TSP解决方案吗？

nb,循环将变为<1,2,...,n-1,n + 1,...,k,1>

Answer 1

不，这不成立。下面给出了一个相当手足无措的反例。我相信您可以添加数字，进行数学计算，并正式验证这一点（我使用此在线求解器来验证我的主张）。

考虑以下几点：

顶部的点显然很远，所以它必须连接到最近的点。然后是其他链接，如下所示：

如果我们排除顶部点，那么让两个顶部点连接到中心点是更优化的，如下所示。所以仅仅走捷径并不是最佳选择：