排序问题：巡回售货员问题、哈密顿圈问题

所有内容：NP与计算的难解性

5 排序问题

主要介绍哈密顿圈、巡回售货员问题这两个排序问题。

5.1 巡回售货员问题

【巡回售货员问题】
有一位巡回售货员，他必须访问n个城市，分别记作$v_1,v_2,v_3,...,v_n$v1​,v2​,v3​,...,vn​，售货员从他所居住的城市$v_1$v1​出发，想找一条旅行路径，访问所有的其他城市最后回到家的顺序。目标是整个旅行路径的距离尽可能的小。
对于每一对城市($v_i,v_j$vi​,vj​)，城市的距离为$d(v_i,v_j)$d(vi​,vj​)。并且，距离不是对称的，即$d(v_i,v_j) \neq d(v_j,v_i)$d(vi​,vj​)​=d(vj​,vi​)。也不要求距离之间满足三角不等式。因此巡回售货员问题的目标是使得总距离$\sum_{j=1}^{n-1}d(v_{i_j},v_{i_{j+1}})+d(v_{i_n},v_{i_1})$∑j=1n−1​d(vij​​,vij+1​​)+d(vin​​,vi1​​)最小。
巡回售货员问题的判定形式为：给定n个城市之间的距离的集合以及界限D，问有长度不超过D的路线吗？

5.2 哈密顿圈问题

【哈密顿圈问题】
对于一个有向图G=(V,E),如果G中的圈C恰好经过每一个顶点一次，则称圈C是一个哈密顿圈。即，哈密顿圈构成一条经过所有的顶点，没有重复的“路线”。如图6是一个含有哈密顿圈的图。

图6 一个含有哈密顿圈的有向图

5.3 哈密顿圈问题是NP完全的

证明哈密顿圈问题是NPC的，可以通过证明3-SAT$\leq_p$≤p​哈密顿圈来得到。
【3-SAT$\leq_p$≤p​哈密顿圈】
构造方法如下:
(1)对于每一个变量$x_i$xi​,创建3m+3个顶点。命名为$v_{i,1},...,v_{i,3m+3}$vi,1​,...,vi,3m+3​，并且对相邻的顶点，添加边($v_{i,j},v_{i,j+1}$vi,j​,vi,j+1​)和($v_{i,j+1},v_{i,j}$vi,j+1​,vi,j​)。如图中7中红色的点和绿色的边。如果$x_i$xi​为1，则路径$P_i$Pi​从左到右。反之，如果$x_i$xi​为0，则路径$P_i$Pi​从右到左。
（2）对于每一个变量，添加边$(v_{i,1},v_{i+1,1})$(vi,1​,vi+1,1​),$(v_{i,1},v_{i+1,3m+3})$(vi,1​,vi+1,3m+3​),$(v_{i,3m+3},v_{i+1,1})$(vi,3m+3​,vi+1,1​),$(v_{i,3m+3},v_{i+1,3m+3})$(vi,3m+3​,vi+1,3m+3​)。
（3）添加两个节点s,t。添加边$(s,v_{1,1})$(s,v1,1​),$(s,v_{1,3m+3})$(s,v1,3m+3​),$(v_{3m+3,1},t)$(v3m+3,1​,t),$(v_{3m+3,3m+3},t)$(v3m+3,3m+3​,t)。
（4）添加边$(t,s)$(t,s)。
构造后的图如图7所示。

图7 3-SAT到哈密顿圈的归约，第1部分
在图7中，可以看到有哈密顿回路：从t出发到达s，s再经过$P_{i}$Pi​，最后到达t，记为A。
之后对子句进行约束。
（5）对于每个子句$C_a$Ca​，假设子句为$C_1=x_1 \vee \overline x_2 \vee x_3$C1​=x1​∨x2​∨x3​，则这个子句表示哈密顿圈首先由左到右通过$P_1$P1​，然后由右向左通过$P_2$P2​，最后由左向右通过$P_3$P3​。如图8所示，添加点和边。

图8 3-SAT到哈密顿圈的归约，第2部分
可以看到，图中有哈密顿圈当且仅当3-SAT实例有满足的赋值。
证明：假设3-SAT实例有满足的赋值，则给出的哈密顿圈中，如果在满足的赋值中$x_i$xi​为1，则由左到右通过$P_{i}$Pi​，反之由右到左通过$P_{i}$Pi​。对于每一个子句，因为其是被满足的，所以至少有一条路径是按照与该项相关的“正确”的方向通过的。从而添加的子句顶点在哈密顿圈中能够被通过。反之，假设图G中有一个哈密顿圈，则所有添加的子句顶点（图8添加的点）都会被通过。即所有的子句都被满足。
因此，可以得到3-SAT实例是可满足的当且仅当G有哈密顿圈。证明了3-SAT$\leq_p$≤p​哈密顿圈。因此哈密顿圈问题是NPC的。

5.4 巡回售货员问题是NP完全的

首先，很容易证明巡回售货员问题是一个NP问题，其验证程序可以多项式时间内验证对应的路线的长度是否超过了给定的界限。
可以通过证明哈密顿圈$\leq_p$≤p​巡回售货员，证明巡回售货员问题是NP完全的。
【哈密顿圈$\leq_p$≤p​巡回售货员】
对于一个有向图$G=(V,E)$G=(V,E),规定下述巡回售货员问题实例：对于图中的每一个点$v_i$vi​，有一个城市$v_{i}’$vi​’。如果在G中有边，则$d(v_i',v_j')=1$d(vi′​,vj′​)=1，否则$d(v_i',v_j')=2$d(vi′​,vj′​)=2。
则，G中有哈密顿圈当且仅当这个巡回售货员问题中有长度不超过n的巡回路线。
因此，哈密顿圈$\leq_p$≤p​巡回售货员，巡回售货员问题是NPC的。

5.5 哈密顿路径问题

【哈密顿路径问题】
哈密顿路径问题是哈密顿圈问题的变种。如果有向图G中的路径P恰好包含每一个顶点一次，则称为是一条哈密顿路径。

5.6 哈密顿路径问题是NP完全的

证明哈密顿路径是NP完全，可以通过3-SAT归约到哈密顿路径。这与3-SAT归约到哈密顿问题是很相似的（只是没有t到s的边）。
,.♥,.,.♥,.,.♥,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥♥,.,.♥,.,.♥,.,.♥,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥
广告时间：
本宝宝开通了一个公众号，记录日常的深度学习和强化学习笔记。希望大家可以共同进步，嘻嘻嘻！求关注，爱你呦！