货郎旅游问题（TravelingSalesmanProblem，TSP)

旅行商问题又叫货郎（优化）问题，是一个经典的组合优化问题。

TSP 可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。

从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的哈密顿回路。

该问题是一个 NP困难问题，可以通过由货郎判定问题 图灵归约 证明。

NP-hard 证明

设存在 TSP 优化问题求解算法 $A$， 设计 TSP 判定问题的算法如下:

对于给定 TSP 判定问题的实例 $G,d,K$，调用 $A(G, d),$ 求得城市排列: $C_{\pi_{1}}^{*} C_{\pi_{2}}^{*} \ldots C_{\pi_{m}}^{*}$

若路径长度小于等于 K，即 $\sum_{i=1}^{m} d\left(C_{\pi,}^{*}, c_{\pi_{\mu+}}^{*}\right) \leq K,$ 则回答 Yes，否则回答 $\mathrm{No}$ 。

若算法 $A$ 的时间复杂性是 $O(1)$，则上述算法能够在多项式时间解答。 所以TSP优化问题是NP-hard问题。

货郎延伸问题

已知一部分货郎旅游路径，求完整的货郎旅游路径，使得总行程小于 $K$，其形式化表述为：

实例： 城市集合 $C=\left\{c_{1}, c_{2}, \cdots, c_{m}\right\},$ 任意两城市间距离 $d\left(c_{i}, c_{j}\right) \in Z^{+},$ 界值 $B \in Z^{+},$ 以 及 $C$ 中 $k$ 个城市的部分旅游

$\Theta=\left\langle c_{\pi(1)}, c_{\pi(2)}, \cdots, c_{\pi(k)}\right\rangle, 1 \leqslant k \leqslant m_{0}$

询问： 能否将 $\Theta$ 延伸为一个全长不超过 $B$ 的全程旅游回路 $\left\langle c_{\pi(1)}, c_{\pi(2)}, \cdots, c_{\pi(k)}\right.$ $\left.c_{\pi(k+1)}, \cdots, c_{\pi(m)}, c_{\pi(1)}\right\rangle$ ？

现在证明货郎优化问题可以图灵归约到该问题，以及货郎判定问题可以图灵归约到该问题。

NP-hard 证明（货郎优化问题图灵归约）

设存在一个货郎延伸问题求解算法 $S(C, d, \Theta, B)$，注意到该问题是一个判定算法（输出 YES/NO）。而优化问题是寻找回路的最短路径长度。

因此该问题的解决方法为确认回路路径的区间，随后通过二分法依次判断区间内的数值即可。

城市间每条边的长度最短为 1，最大长度可以通过遍历取得，表示为 $d_{max}$，设城市个数为 m，因为货郎问题是一个回路，回路有 m 个点就有 m 条边，因此其上下限即为 $[m, m*d_{max}]$。

最后是二分法每次在该区间内取一个长度调用货郎延伸问题算法 $S(C, d, \Theta, B)$ 判定，直至最终求解完成的过程，不再叙述。

二分法的复杂度是 $O(logB)$，在多项式时间内。

NP-hard 证明（货郎判定问题图灵归约）

货郎判定问题实际上可以看做是 $|\Theta|=1$ 情况下的货郎延伸问题实例，因此 货郎判定问题 可以多项式归约到货郎延伸问题。

货郎判定问题

货郎优化问题可以转变描述，变为一个判定问题：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。是否存在一个行进路线，使得其行程小于 $K$ ？

该问题是一个 NPC 类问题，可以通过 哈密顿回路问题 归约证明。

该问题同时也可以通过货郎优化问题 图灵归约证明 NP-hard。

证明方法为先证明货郎优化问题可以图灵归约到货郎延伸问题，再证明货郎延伸问题可以图灵归约到货郎判定问题，从而可以根据归约的传递性证明货郎优化问题可以图灵归约到货郎判定问题。

NPC 证明

以哈密顿回路问题实例 $G=(V,E)$ 构造判定问题实例，令所有边权值为1，$K=|V|$，之后易得。

货郎判定问题的实质就是在一个带权完全无向图中，找一个权值最小的哈密顿回路。

NP-hard 证明

暂略，参考 P146 页证明。