complexity-theory - 具有特殊指标的旅行商

Question

已知欧几里得 TSP 是 NP 完全的。

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

• 从 A 到 B = max(A 的 x 坐标，B 的 y 坐标);
• 从 B 到 A = max(B 的 x 坐标，A 的 y 坐标)。

这仍然是 NP 完全的吗？

Answer 1

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

您的配方与“标准”TSP 的区别在于成本 根据您旅行的方向而有所不同。即成本(i，j)!=成本(j，i)。 成本通常表示为便于查找的矩阵，并且对称性使您可以将成本矩阵的大小减半。您的公式要求矩阵完全填充。成本矩阵的生成仍然只有 O(n^2)。

要获得准确的答案，您仍然需要暴力破解您的答案(可能性的数量 == “城市”O(n!) 的排列数量)或使用像 SAT 求解器这样的奇特算法。