特殊度量下的旅行推销员问题

Question

欧几里得TSP问题被认为是NP完全问题。

在我的特殊度量中，A和B之间的距离定义为：

• 从A到B = A的x坐标和B的y坐标的最大值；
• 从B到A = B的x坐标和A的y坐标的最大值。

这个问题仍然是NP完全问题吗？

- Cong

---

不，只是一个有趣的问题。 - Cong

Answer 1

是的。成本函数的计算并不是使TSP成为NP完全问题的原因。

你的公式与“标准”TSP的区别在于，成本取决于你行进的方向。也就是说，cost(i,j) != cost(j,i)。成本通常表示为矩阵以便于查找，并且对称性使您可以将成本矩阵的大小减半。您的公式需要完全填充矩阵。成本矩阵的生成仍然只有O(n^2)。

对于精确答案，您仍然需要用暴力方法来解决问题（可能性的数量等于“城市”排列组合的数量O(n!)），或者使用像SAT求解器这样的高级算法。

- LogicG8

---

谢谢！但是，为了证明它的 NP 完备性，我们需要从另一个 NP 完备问题进行约简。我认为“成本因方向不同而异”并不是唯一的区别。 - Cong

假设您有一个解决非对称TSP的算法。首先，观察它属于NP问题。显然，它也可以解决任何欧几里得TSP实例。由于欧几里得TSP是NP完全问题（因此是NP难问题），非对称TSP也是NP难问题。因此，非对称TSP是NP完全问题。 - Reinhard

您是否有关于使用SAT求解器解决度量TSP问题的更多信息？ - Inuart