algorithm - 对于给定的旅行商问题的特殊情况，下列哪项陈述是正确的？

Question

我正在学习算法：设计与分析 II课程，其中一个问题是：

下面哪个描述是正确的？

• 考虑一个 TSP 实例，其中每个边的成本都是 1 或 2。然后可以在多项式时间内计算出最优路径。
• 考虑一个 TSP 实例，其中每个边缘成本都是负数。视频讲座中介绍的动态规划算法可能无法正确计算此实例的最优（即边长的最小总和）行程。
• 考虑一个 TSP 实例，其中每个边缘成本都是负数。删除一个顶点及其所有的入射边不会增加最优（即边长的最小总和）游览的成本。
• 考虑一个 TSP 实例，其中每个边成本都是该位置两点之间的欧几里得距离（就像在编程作业 #5 中一样）。删除一个顶点及其所有的入射边不会增加最优（即边长的最小总和）游览的成本。

我论证如下：

DP算法不对边缘成本做任何假设，所以选项2是不正确的。

如果所有边权重都是负数，那么删除一个顶点及其所有关联边肯定会增加最小总和，因为实际上，该边权重现在已添加到先前的最小值。因此，选项 3 不正确。

在原始实例中进行最佳游览。现在，不要访问已删除的顶点 v，而是直接从 v 的前任跳到其继任者。因为欧几里得距离满足“三角不等式”，所以这条捷径只会减少总行驶距离。最好的旅行当然只能更好。因此，选项 4 是正确的。

但是，我无法找到单位边缘成本的 TSP 问题的任何意义。选项 1 仅仅是一个技巧，还是还有更多？

标签： algorithmgraph-theorytraveling-salesmannpnp-complete

Answer 1

在这里操作：

Papadimitriou 和 Yannakakis表明，可以在多项式时间内以 7/6 的精度逼近 TSP 问题 1。Bläser 和 Shankar Ram将这一保证进一步提高到 65/56。然而，无论这些结果有多好，这些仍然是近似值，而不是最佳解决方案。因此，选项 1 是不正确的。