8 难问题的部分分类

8.1 包装问题

包装问题主要有独立集问题和集合包装问题。
(1)独立集问题:给定图G和数k,问G包含大小至少为k的独立集吗?
(2)集合包装问题:给定 n 个元素的集合 U , U 的子集 S_1,S_2,…,S_m 以及数 k , 问在这些子集中至少含有 k 个集合两两不相交?

8.2 覆盖问题

覆盖问题主要有顶点覆盖和集合覆盖问题。
(1)顶点覆盖:给定图G和数k,G是否包含大小为k的顶点覆盖?
(2)集合覆盖:给定 n 个元素的集合U,U 的子集S_1,…,S_m 以及数 k, 问在这些子集中有一组子集,它的并等于整个 U 且至多含有 k 个子集?

8.3 划分问题

划分问主要是三维匹配问题和图着色问题。
(1)三维匹配问题:给定三个不相交的集合X、Y、Z,三个集合的大小都为n。给定一个三元组集合,集合T的大小为m。问:T中是否存在一个大小为n的子集T’,这个子集恰好包含X,Y,Z每个元素一次。
(2)图着色问题:任意给图G和界限k,问G有k-着色吗?

8.4 排序问题

排序问题主要是巡回售货员问题、哈密顿圈、哈密顿路径问题。
(1)巡回售货员问题:给定n个城市之间的距离的集合以及界限D,问有长度不超过D的路线吗?
(2)哈密顿圈:给定有向图G,问G有哈密顿圈吗?
(3)哈密顿路径:给定有向图G,问G有哈密顿路径吗?

8.5 数值问题

数值问题主要是子集和问题。
(1)子集和:给定自然数w_1,w_2,…,w_n和目标值W,问{w_1,w_2,…,w_n}有一个子集加起来恰好等于W吗?

8.6 约束满足问题

约束满足问题主要是电路可满足性问题、SAT和3-SAT。
(1)电路可满足性:给定一个电路,需要确定是否存在对输入的赋值使得输出值为1。如果存在这样的赋值,则称这个电路是可满足的。这个赋值也被称为一个满足的赋值。
(2)SAT:给定变量集 X={{x_1,x_2,…,x_n}} 上的一组子句 C_1,C_2,…,C_n ,问存在满足的真值赋值吗?
(3)3-SAT:给定变量集 X={{x_1,x_2,…,x_n}} 上的一组子句 C_1,C_2,…,C_n ,每一个子句的长度为3,问存在满足的真值赋值吗?

0
Posted in 算法设计与分析

7 数值问题

7.1 子集和问题

【子集和问题】
给定自然数w_1,w_2,…,w_n和目标值W,问{w_1,w_2,…,w_n}有一个子集加起来恰好等于W吗?
Ex: { 1, 4, 16, 64, 256, 1040, 1041, 1093, 1284, 1344 }, W = 3754.
Yes. 1 + 16 + 64 + 256 + 1040 + 1093 + 1284 = 3754.

7.2 子集和问题是NP完全的

首先证明子集和问题是NP的。给定自然数和目标W,直接求子集中元素的合,判断是否等于W。因此可以在多项式时间内验证答案是否正确。
可以通过证明三维匹配\leq_p子集和,证明子集和问题是一个NPC问题。
【三维匹配 \leq_p 子集和】
对于三维匹配的T中的每一个元素t_a=(x_i,y_j,z_k),新建一个3n(n为自然数的个数)位的d进制串(d=m+1),3n位对应X、Y、Z的3n个元素。置第i位,第n+j位,第2n+k位为1,其他位为0。用10进制表示,则w_n=d_{i-1}+d_{n+j-1}+d_{2n+k-1}。因此W={w_1,w_2,…,w_n}。取d进制是为了防止进位。
于是,可以设k=A=\sum_{i=0}^{3n-1}d_{i}
归约完成。可以证明有一个完美的三维匹配当且仅当子集和问题中子集存在。
证明:假设有一个完美三维匹配T={t_1′,t_2′,…,t_n’},T的大小为n。在T中的每一个元素t_i都在W’中对应一个元素w_{t_i}。因为在三维匹配中所有的元素只出现一次,因此W中的所有元素相加得到一个3n位全为1的串,则\sum_{w \in W’}w=A
同时,假设有一个子集W’ \subseteq W,使得\sum_{w \in W’}w=A。对于任意的元素w \in W’,转换为d进制后都有3个位为1,对应于T的某一个元素。这些元素构成集合T,T中恰好包含X、Y、Z每个元素一次,因此T是一个完美匹配。

0
Posted in 算法设计与分析

6 划分问题

讨论两个划分问题,一个是三维匹配问题,另一个是图着色问题。对于三维匹配问题,要求搜索把对象集合分成子集的方式。对于图着色问题,要求划分图中的结点。

6.1 三维匹配问题

【三维匹配问题】
给定三个不相交的集合X、Y、Z,三个集合的大小都为n。给定一个三元组集合T \subseteq X \times Y \times Z,集合T的大小为m。
问:T中是否存在一个大小为n的子集T’,这个子集恰好包含X,Y,Z每个元素一次。
三维匹配问题其实是集合覆盖和集合包装问题的特例。

6.2 三维匹配问题是NP完全的

首先,很容易证明三维匹配问题是NP问题。只需要判断集合T’的大小是否为n,且包含X,Y,Z中每个元素一次。证明三维匹配问题是NPC的,可以通过3-SAT\leq_p三维匹配证明。
【3-SAT\leq_p三维匹配证明】
考虑任意的一个3-SAT实例,有n个变量x_1,x_2,…,x_n和k个子句C_1,C_2,…,C_n。构造3DM实例X,Y,Z,T。
对于每一个变量,都有一个零件相对应。如图9所示。每个零件有Core(核心)元素、Tip(边梢)元素、Triple元组。每一个零件大大小为2k。k为子句的大小。
则,对于每一个变量x_i,建立:
A_i={a_{i,1},a_{i,2},…,a_{i,2k}}
B_i={b_{i,1},b_{i,2},…,b_{i,2k}}
t_{i,j}={(a_{i,j},a_{i,j+1},b_{i,j})}
构造的零件如图9所示。
在这里插入图片描述
图9 三维匹配的零件
对于每一个子句C_t加入两个元素P_t,P_t’,如果C_{t}包含x_{j},则加入三元组P=(P_t,P_t’,b_{j,2t}),显然一个C_i有三个三元组。
如果包含\overline x_j,则加入P=(P_t,P_t’,b_{j,2t-1});所以每个子句的三元组所包含的tip元组是不冲突的。即C_iC_j的三元组中没有相同的b元素。如图10所示。
在这里插入图片描述
图10 从3-SAT到三维匹配的归约,第一部分
定义,如果t_{ij}中的j为偶数,则称t_{ij}为偶三元组,如果j为奇数,则t_{ij}为奇三元组。
如果b_{i,j}中的j为偶数,则称b_{i,j}为偶tip,如果j为奇数,则称b_{i,j}为奇tip。
可以看到,要想core元素都被包含,且不被重复包含,则必须要么选择全部的偶三元组,要么选择全部的奇三元组。定义如果选择了全部的偶三元组,则x_{i}=0,否则,x_i=1
因此,可以看到,如果一个子句为1,则必然有一项的值为1,即选择该变量的所有奇三元组或所有偶三元组中。如果3-SAT是可满足的,则每个C_t的3个三元组中,至少有一个能够被选择。
对于每个没有被选择的tip元素,添加cleanup零件:Q={q_i,q_i’}。即有(n-1)k个tip等待覆盖。并且添加三元组(b_{i,j},q_i,q_i’)
如图11完成了3-SAT到三维匹配的归约。
在这里插入图片描述
图11 从3-SAT到三维匹配的归约,第二部分
此时,我们令:
X={a_{i,j}(j是偶数)} \vee{p_j} \vee {q_j} 。
Y={a_{i,j}(j是奇数)} \vee{p_j’} \vee {q_j’} 。
Z={b_{i,j}} 。
T={所有构造出来的三元组}。
可以看到,X,Y,Z三个集合的大小是相等的。
【对于每一个3-SAT实例】
假设有一个真值赋值,则如果x_i=1,则选择x_i对应的变量零件的所有奇三元组。若果c_j包含x_i,则c_j为1,则选择(p_j,p_j’,b_{t,2j}),因为b_{t,2j}为偶tip,因此没有被覆盖。如果x_i=0,则选择x_i对应的变量零件的所有偶三元组。若果c_j包含\overline x_i,则c_j为1,则选择(p_j,p_j’,b_{t,2j-1}),因为b_{t,2j-1}为奇tip,因此没有被覆盖。剩余没有被选中的tip元组被cleanup零件覆盖。
因此最终所有的元素都只被覆盖一次。
因此一个完美的三维匹配为:
T={变量中选择的三元组}\vee{子句中选择的三元组}\vee{cleanup中的三元组}
【对于一个三维匹配实例】
如果有一个完美三维匹配,则每个子句零件中的3个元组必须有一个被选择,则c_j为1。如果被选择的子句三元组中有偶tip,则说明该项的值为1,否则,该项的值为0。即存在一个可满足的真值赋值。此时,已经完成了3-SAT到三维匹配的证明。因此,三维匹配问题是一个NPC问题。

6.3 图着色问题

【图着色问题】
在图着色问题中,试图给图G中的每一个结点分配颜色,使得如果(u,v)是一条边,则边的两个结点的颜色不同。目标是使用很少的几种颜色做到这一点。使用的颜色数量为k。图着色问题可以阐述为:任意给图G和界限k,问G有k-着色吗?

6.4 三着色问题是NP完全的

有一个图G是二可着色的当且仅当它是二部图(这里不对齐进行证明)。对于3种颜色的情况,已经比较复杂了。三着色问题其实是一个NP完全问题。首先很容易证明其是一个NP问题。这里通过证明3-SAT\leq_p三着色,来证明三着色问题是NPC的。
【3-SAT\leq_p三着色】
首先对于每一个变量,添加结点v_i\overline v_i。添加结点T(真结点)、F(假结点)、B(基点)。用边连接每一对结点v_i\overline v_i。再连接这些结点与基点。也将真结点、假结点、基点连接起来。如图12所示。
在这里插入图片描述
图12 三着色问题的归约的开始部分
于是,在G的任何三着色中,结点v_i\overline v_i必须着不同的颜色,并且都必须与基点的颜色不同。
在G的任何三着色中,真结点、假结点和基点一定以某种顺序得到全部的3种颜色。可以根据什么结点得到什么颜色原则,使得这3个结点分别得到真色、假色和基色。因此v_i\overline v_i中只有一个得到真色,另一个得到假色。
考虑子句x_1 \vee \overline x_2 \vee x_3,即这个x_1, \overline x_2, x_3三个结点中至少有一个着真色。现在插入一个小子图,使得任何能扩展到该小子图的三着色必须至少给x_1, \overline x_2, x_3着一个真色。
这样的子图如图13所示。
在这里插入图片描述
图13 附加的子图
则,必须至少给x_1, \overline x_2, x_3着一个真色,才能使得子图实现三着色(否则会出现颜色冲突)。如图14为子图的三着色实例。
在这里插入图片描述
图14 子图的三着色方案
可以论证3-SAT实例时可满足的当且仅当子图有三着色方案。即3-SAT\leq_p三着色,因此三着色问题是NPC的。

0
Posted in 算法设计与分析

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
Posted in 算法设计与分析

4 NPC问题(NP完全问题)

在是否P=NP的问题没有进展的情况下,人们转向一个相对的,更加好处理的问题:哪些是NP中最难的问题?

4.1 NPC(NP-Complete)问题

若一个问题X是NP问题,且对于所有的 Y \in NP,Y \leq_p X 。即NP中的每一个问题都可以归约到X,则称问题X是NP完全问题。
✿于是,可以得到,如果NP中有一个问题不是多项式时间内可以解决的,则所有的NP完全问题都不是多项式时间内可以解决的。
并且,如果 Y 是一个 NP 完全问题, X 属于 NP ,且 Y \leq_p X,则 XNP 完全的。

4.2 电路可满足性问题是NPC问题

【电路可满足性问题】
电路可满足性问题(Circuit satisfiability problem)描述为:给定一个电路,需要确定是否存在对输入的赋值使得输出值为1。如果存在这样的赋值,则称这个电路是可满足的。这个赋值也被称为一个满足的赋值。如图5为电路可满足性问题的一个实例。
在这里插入图片描述
图5 电路可满足性问题
图中的左边,从上到下依次是或门、非门。图中的右边是与门。当1和2输入都为1,3输入为0的时候,输出为1。即这个电路是满足的。
定理6.电路可满足性问题是NPC问题。
电路可满足性问题是NPC。这个定理是Cook和Levin于1971年提出的。
证明电路可满足性问题是NPC的,根据NPC定义,需要证明以下两点:
(1)电路可满足性问题是NP问题。
(2)所有的NP问题都可以归约到电路可满足性问题。
证明:
(1)对于电路的每一个输入,只需要验证其结果是否是1即可。因此能够在多项式时间内验证答案是否正确。即电路可满足性问题是NP问题。
(2)对于一个问题,可以将输入的实例s和证书t,构造一个输入长度为(|s|+|t|)的电路。即有(|s|+|t|)个源结点(输入结点)。很容易看到,一定有办法设计电路,使得电路的输出为1。即电路是可满足的。表明所有的NP问题都可以归约为电路可满足性问题。
因此,电路可满足性问题是NPC问题。

4.3 三元可满足性问题是NPC问题

定理7.如果 Y 是一个 NP 完全问题, X 属于 NP ,且 Y \leq_p X,则 XNP 完全的。
之前已经证明3-SAT是一个NP问题,可以通过证明电路可满足性 \leq_P 3-SAT,来证明它是NP完全的。
【电路可满足性 \leq_P 3-SAT】
对于一个电路K,对于电路的每一个结点v,关联一个变量x_v , x_v表示在该结点的真值。电路K的门计算有3种:与、或、非。
如果某个结点v是非门,则它的唯一进入边来自于结点u,那么必须要有x_v= \overline x_u,可以通过添加两个子句(x_v \vee x_u)或(\overline x_v \vee \overline x_u)来保证这一点。
如果某个结点v是或门,则它的2个边分别来自于结点u和w,那么必须要有x_v= x_u \vee x_w,可以通过添加三个子句(x_v \vee \overline x_u)、(x_v \vee \overline x_w)或(\overline x_v \vee x_u \vee x_w)来保证这一点。
如果某个结点v是与门,则它的2个边分别来自于结点u和w,那么必须要有x_v= x_u \wedge x_w,可以通过添加三个子句(\overline x_v \vee x_u)、(\overline x_v \vee x_w)或(x_v \vee \overline x_u \vee \overline x_w)来保证这一点。
对于源结点,保证其等于规定的值,可以对每个源结点v添加一个只含有一个项x_v\overline x_v的子句,强迫其取规定的值。对于输出结点,添加一个单变量子句,让其取1。于是完成了构造。
可以证明构造的SAT实例是等价于与给定的电路可满足性实例的。
由于我们要证明电路可满足性 \leq_P 3-SAT,因此还需要将子句转换为恰好有3个变量的实例。
对于只有一个项t的子句,可以将子句替换成(t \vee z_1 \vee z_2);
对于有2个项的子句(t \vee t’),可以替换成(t \vee t’ \vee z_1)。
显然,为了保证新构造的子句等价于原来的子句,需要保证z_1=z_2=0
为了保证z_1=z_2=0,对于i=1和2,可以添加子句(\overline z_i \vee z_3 \vee z_4),(\overline z_i \vee \overline z_3 \vee z_4),(\overline z_i \vee z_3 \vee \overline z_4),(\overline z_i \vee \overline z_3 \vee \overline z_4),保证z_1=z_2=0
从而完成了电路K到3-SAT的构造。因此电路可满足性 \leq_P 3-SAT。证毕。
因此,根据3-SAT \leq_p 独立集 \leq_p 顶点覆盖 \leq_p 集合覆盖,可以得到独立集、顶点覆盖、集合包装、集合覆盖问题都是NPC问题。

4.4 证明NPC问题的通用策略

给定一个基本的问题X,证明其是NPC的基本策略是:
(1)证明X是一个NP问题。
(2)选择一个已知的NPC问题Y。
(3)证明Y \leq_p X

0
Posted in 算法设计与分析