complexity-theory - 具有特殊度量的旅行推销员

Question

众所周知，欧几里得 TSP 是 NP 完全的。

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

• 从 A 到 B = max(x coordinate of A , y coordinate of B);
• 从 B 到 A = max(x coordinate of B , y coordinate of A).

这仍然是NP完全的吗？

Answer 1

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

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

对于一个确切的答案，你仍然需要暴力破解你的答案（可能性的数量==“城市”O（n！）的排列数量）或使用像SAT求解器这样的奇特算法。