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

5 排序问题

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

5.1 巡回售货员问题

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

5.2 哈密顿圈问题

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

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

证明哈密顿圈问题是NPC的,可以通过证明3-SAT\leq_p哈密顿圈来得到。
【3-SAT\leq_p哈密顿圈】
构造方法如下:
(1)对于每一个变量x_i,创建3m+3个顶点。命名为v_{i,1},…,v_{i,3m+3},并且对相邻的顶点,添加边(v_{i,j},v_{i,j+1})和(v_{i,j+1},v_{i,j})。如图中7中红色的点和绿色的边。如果x_i为1,则路径P_i从左到右。反之,如果x_i为0,则路径P_i从右到左。
(2)对于每一个变量,添加边(v_{i,1},v_{i+1,1}),(v_{i,1},v_{i+1,3m+3}),(v_{i,3m+3},v_{i+1,1}),(v_{i,3m+3},v_{i+1,3m+3})
(3)添加两个节点s,t。添加边(s,v_{1,1}),(s,v_{1,3m+3}),(v_{3m+3,1},t),(v_{3m+3,3m+3},t)
(4)添加边(t,s)
构造后的图如图7所示。
在这里插入图片描述
图7 3-SAT到哈密顿圈的归约,第1部分
在图7中,可以看到有哈密顿回路:从t出发到达s,s再经过P_{i},最后到达t,记为A。
之后对子句进行约束。
(5)对于每个子句C_a,假设子句为C_1=x_1 \vee \overline x_2 \vee x_3,则这个子句表示哈密顿圈首先由左到右通过P_1,然后由右向左通过P_2,最后由左向右通过P_3。如图8所示,添加点和边。
在这里插入图片描述
图8 3-SAT到哈密顿圈的归约,第2部分
可以看到,图中有哈密顿圈当且仅当3-SAT实例有满足的赋值。
证明:假设3-SAT实例有满足的赋值,则给出的哈密顿圈中,如果在满足的赋值中x_i为1,则由左到右通过P_{i},反之由右到左通过P_{i}。对于每一个子句,因为其是被满足的,所以至少有一条路径是按照与该项相关的“正确”的方向通过的。从而添加的子句顶点在哈密顿圈中能够被通过。反之,假设图G中有一个哈密顿圈,则所有添加的子句顶点(图8添加的点)都会被通过。即所有的子句都被满足。
因此,可以得到3-SAT实例是可满足的当且仅当G有哈密顿圈。证明了3-SAT\leq_p哈密顿圈。因此哈密顿圈问题是NPC的。

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

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

5.5 哈密顿路径问题

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

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

证明哈密顿路径是NP完全,可以通过3-SAT归约到哈密顿路径。这与3-SAT归约到哈密顿问题是很相似的(只是没有t到s的边)。

0

Leave a Reply

Your email address will not be published.