TSP 问题

我们在之前讨论过 NP-hard 和 NP-complete 的关系，而旅行商问题(travel salesman problem, TSP)是最经典的 NP-hard 问题之一。 原题可以表述为：给定若干城市及每组城市间距离，求解访问每座城市恰好一次并回到起始城市的最短回路。

TSP 问题的表述在图论中等价于：给定一个完全加权图，求解权重之和最小的哈密顿回路。

这个题有非常多的变种，这里随便列举一些

• 判定版本（decision version)：在原条件下再给定一个长度，问是否存在比该长度更短的回路。
• 瓶颈版本(bottleneck TSP): 给定一个加权图，找到哈密顿回路使得其中的最大权重边最小。据说这个版本在物流、交通这样的现实问题中非常重要。在电路板的印制中，钻头的钻孔和移动就相当于城市之间的距离成本。
• 广义旅行商问题(generalized TSP, set TSP): 图中的节点被分为若干个不相交的子集，求解最小回路使得恰好能访问每个子集中的一个节点。显然，经典的 TSP 就是每个子集都是节点本身的一个特例。既然 TSP 是 NP-hard 的，那么 set TSP 也是 NP-hard 的。这个版本还有一个名称叫 旅行政客问题，也就是要求政客恰好能访问每个“州”中的一个“城市”。这个问题在运筹学(operations research)上还有一种应用是原料裁切问题(cutting stock problem)，比如在加工卷纸和金属板时，如何切割原料能够尽可能小的减少浪费或者减少刀片的更换次数。