两种TSP问题（旅行推销员问题）的复杂性证明

#! https://zhuanlan.zhihu.com/p/596106342 # 两种TSP问题（旅行推销员问题）的复杂性证明

我们平时说的TSP问题实际上有两种，一种是原始版本，我们称之为tour-TSP。它要求从某个点出发，经过每个点一次，然后再回到原点。另一种是变种path-TSP，它使得可以从任意点出发，并且经过每个点一次，最终不需要回到原点。实际上可以证明这两个问题有相似的复杂性。

两种TSP问题的同复杂性

我们首先来证明tour-TSP是可以线性时间reduce到path-TSP的。

对于一个tour-TSP的实例，有n个城市\(c_1,c_2 \cdots ,c_n\)。取k为n乘城市间的最大距离。d为距离函数（给出了任意两个城市间的距离）。取一个\(c_1\)的复制\(c_1'\)，然后构造如下新的距离函数\(d'\)

\[ d'(c_i,c_j) = d(c_i,c_j) \quad if \ i,j\neq 1\\ d'(c_1,c_j) = d(c_1,c_j) + 2k \quad for \ all \ j \\ d'(c_1',c_j) = d(c_1,c_j) + 2k \quad for \ all \ j \\ d'(c_1,c_1') = 3k \\ \]

注意到我们可以证明对于\(d'\)的path-TSP问题，它的最优路径端点一定是\(\{ c_1,c_1' \}\)。

反证的假设端点是\(\{ c_i,c_j \} \neq \{ c_1,c_1' \}\)。如果其中一个\(c_i,c_j\)是\(c_1\)或\(c_1'\)，那么可以证明整条路径最短长度为6k。因为作为端点的\(c_1\)或\(c_1'\)至少2k，而作为非端点的\(c_1\)或\(c_1'\)至少带来4k的长度。如果\(c_i,c_j\)都不是\(c_1\)或\(c_1'\)，那么路径长度至少为7k，因为此时\(c_1\)和\(c_1'\)都是非端点，结论是平凡的。

但是注意到端点是\(\{ c_1,c_1' \}\)的情况，路径长度不会超过5k。因此我们就证明了这个结论。那么就有总路径长度\(d'(p) = d(t) + 4k\)。解决这个path-TSP问题就解决了原tour-TSP问题。

tour-TSP的NP完全性

我们通过把哈密顿回路问题reduce到tour-TSP来证明它的NP完全性。

哈密顿回路问题是指给定一个图\(G=(V,E)\)，问G是否包含一条哈密顿回路，即一条通过且只通过每个顶点一次的回路。

对于一个哈密顿回路问题的实例，构造一个tour-TSP的实例。取城市的集合\(C=V\)，\(n=|C|\)，对于任意的两个城市\(v_i,v_j \in C\)，如果\((v_i,v_j)\in E\)，则取\(d(v_i,v_j)=1\)，否则取\(d(v_i,v_j)=2\)。

容易发现，如果TSP的结果为n，则哈密顿回路存在；如果TSP的结果大于n，则哈密顿回路不存在。这就解决了原问题。