algorithm - 如果我简化了一个最优的 TSP 解决方案，它仍然是最优的吗？

Question

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

Wlog 假设循环:<1, 2, 3, ..., k, 1> 是该图的最佳 TSP 解决方案。

我的问题是:如果我从图中删除一个节点(例如第 n 个节点)并缩短循环，只是跳过 n，生成的循环仍然是最佳 TSP 解决方案吗？

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

Answer 1

不，这不成立。下面给出了一个相当麻烦的反例。我相信您可以添加数字、计算并正式验证这一点(我使用 this online solver 来验证我的声明)。

考虑以下几点:

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

如果我们排除顶点，让两个顶点连接到中心点是更优化的，如下所示。所以只是走捷径不是最优的: