《《算法设计与分析》第10章.ppt》由会员分享，可在线阅读，更多相关《《算法设计与分析》第10章.ppt（43页珍藏版）》请在三一办公上搜索。
1、第10章 NP完全问题,10.1 基本概念 10.2 Cook定理和证明 10.3 一些典型的NP完全问题,10.1 基本概念,将能在多项式时间求解的问题看作易处理问题(tractable problem)，而将至今尚未找到多项式时间算法求解的问题视为难处理问题(intractable problem)。,10.1.1 不确定算法和不确定机,为便于研究，先假定一种运行不确定算法的抽象计算模型，该抽象机除了包含第节的抽象机模型的基本运算外，最根本的区别在于它新增了下面一个新函数和两个新语句：（1）Choice(S)：任意选择集合S的一个元素；（2）Failure：发出不成功完成信号后算法终止；（
2、3）Success：发出成功完成信号后算法终止。,例101 在n个元素的数组a中查找给定元素x，如果x在其中，则确定使aj=x的下标j，否则输出-1。【程序101】不确定搜索算法 void Search(int a,T x)int j=Choice(0,n-1);if(aj=x)coutj;Success();cout-1;Failure();,包含Choice函数的算法能按如下既定方式执行：当算法执行中需作出一系列的Choice函数选择时，当且仅当对于Choice的任何一组选择都不会导致成功信号时，此算法在O(1)时间不成功终止；否则，只要存在一组选择能够导致成功时，算法总能采取该组选择使得
3、算法成功终止。包含不确定选择语句，并能按上述方式执行一个算法的机器称为不确定机（non deterministic machine）。在不确定机上执行的算法称为不确定算法（non deterministic algorithm）。,例10-2 将n个元素的序列排成有序序列。【程序10-2】不确定排序算法void NSort(int a,int n)int bmSize,i,j;for(i=0;in;i+)bi=0;for(i=0;in;i+)j=Choice(0,n-1);if(bj)Failure();bj=ai;,for(i=0;ibi+1)Failure();for(i=0;in;i+)
4、coutbi;coutendl;Success();,定义10-1（不确定算法时间复杂度）一个不确定算法所需的时间是指对任意一个输入，当存在一个选择序列导致成功完成时，达到成功完成所需的最少程序步。在不可能成功完成的情况下，所需时间总是O(1)。,例10-3（最大集团及其判定问题）无向图G=(V,E)的一个完全子图称为该图的一个集团（clique）。集团的规模用集团的顶点数衡量。最大集团问题是确定图G的最大集团规模的问题。最大集团判定问题（G,k）是对给定正整数k，判定图G是否存在一个规模至少为k的集团。,【程序10-3】最大集团判定问题不确定算法void Clique（int gmSize,
5、int n,int k）S=;for(int i=0;i k;i+)int t=Choice(0,n-1);if(tS)Failure();S=St;for(对所有(i,j)，iS，jS且ij)if(i,j)E)Failure();Success();,10.1.2 可满足性问题,例10-4 可满足性问题（satisfiability problem）是一个判定问题，它确定对于一个给定的命题公式，是否存在布尔变量的一种赋值（也称真值指派）使该公式为真。CNF可满足性是指判定一个CNF公式的可满足性。,【程序10-4】可满足性问题的不确定算法 void Eval(CNF E,int n)int
6、xmSize;for(int i=1;i=n;i+)xi=Choice(0,1);if(E(x,n)Success();else Failure();,P类和NP类问题,定义10-2（P类和NP类）P是所有可在多项式时间内用确定算法求解的判定问题的集合。NP是所有可在多项式时间内用不确定算法求解的判定问题的集合。定义10-3（多项式约化）令Q1和Q2是两个问题，如果存在一个确定算法A求解Q1，而算法A以多项式时间调用另一个求解Q2的确定算法B。若不计B的工作量，算法A是多项式时间的，则称Q1约化（reduced to）为Q2，记做Q1Q2。,性质10-1 若Q1P，Q2Q1，则有Q2P。性质1
7、0-2 若Q1Q2，Q2Q3，则Q1Q3。,10.1.4 NP难度和NP完全问题,定义10-4（NP难度）对于问题Q以及任意问题Q1NP，都有Q1Q，则称Q是NP难度（NP hard）的。定义10-5（NP完全）对于问题QNP，Q是NP难度的，则称Q是NP完全（NP complete）的。,如何确定某个问题Q是否是NP难度的？一般的证明策略由以下两步组成：（1）选择一个已经证明是NP难度问题Q1；（2）求证Q1Q。由于Q1是NP难度的，因此所有NP类问题都可约化到Q1，根据约化的传递性，任何NP类问题都可约化到Q，所以Q是NP难度的。如果进一步表明Q本身是NP类的，则问题Q是NP完全的。,10
8、.2 Cook定理和证明,10.2.1 Cook定理,斯蒂芬库克（Steven Cook）于1971年证明了第一个NP完全问题，称为Cook定理。Cook定理表明可满足性问题是NP完全的。CNF可满足性问题也被证明是NP完全的。自从Cook证明了可满足性问题是NP完全的之后，迄今为止至少有300多个问题被证明是NP难度问题，但尚未证明其中任何一个是属于P的。定理10-1（Cook定理）可满足性问题在P中，当且仅当P=NP。定理10-2 CNF可满足性问题是NP完全的。,10.3 一些典型的NP完全问题,证明一个问题Q是NP难度（或NP完全）问题的具体步骤如下：（1）选择一个已知其具有NP难度的
9、问题Q1；（2）证明能够从Q1的一个实例I1，在多项式时间内构造Q的一个实例I；（3）证明能够在多项式时间内从I的解确定I1的解。（4）从（2）和（3）可知，Q1Q；（5）由（1）和（4）及约化的传递性得出所有NP类问题均可约化到Q，所以Q是NP难度的；（6）如果Q是NP类问题，则Q是NP完全的。,最大集团,定理10-3 CNF可满足性最大集团判定问题。证明 分两步证明这一定理：首先寻找一种方法，它能在多项式时间内，从任意给定的CNF公式F构造一个无向图G=(V,E)；然后证明，F是可满足的，当且仅当G有一个规模至少为k的集团。,第一步：以任意给定的CNF公式F为输入，构造一个相应的无向图G，
10、并且这种构造能够在多项式时间内完成。令是一个CNF形式的命题公式，xi，1in，是F中的变量。由F生成一个无向图G=(V,E)的方法为：V=|是子句Ci的一个文字，E=(,)|ij且。,第二步：如果能够证明F可满足，当且仅当G有一个规模至少为k的集团，那么，便证明了CNF可满足性问题可以约化到最大集团判定问题。分两方面证明此结论:一方面，若F是可满足的，则必定存在对n个布尔变量的一种赋值，使得每个子句Ci中至少有一个文字为真。另一方面，若G有一个规模至少为k的集团G（S，E），设S=,是集团的顶点集合，则必有i，ij，若不然，则顶点和之间没有边，S不是集团。,例10-5 设有命题公式F，,图G
11、(V.E)有大小为2的集团，F是可满足的（可令x1true，x2false）,10.3.2 顶点覆盖,例106（顶点覆盖判定问题）对于无向图G(V,E)，集合SV，如果E中所有边都至少有一个顶点在S中，则称S是图G的一个顶点覆盖。覆盖的规模是S中顶点的数目|S|。顶点覆盖（vertex cover）问题是指求图G的最小规模的顶点覆盖，而顶点覆盖判定问题是确定图G是否存在规模至多为k的顶点覆盖。,对于图中所示的无向图G，S1=1，3和S2=0，2，4分别是图G的顶点覆盖，S1是最小覆盖，其规模为2。,定理104 最大集团判定问题顶点覆盖判定问题。证明：分两步证明这一结论。第一步：以最大集团判定问
12、题的任一实例(G，k)，G=(V，E)，k为正整数，来构造一个顶点覆盖判定问题的实例(G，n-k)，G=(V，)，n=|V|，=(u,v)|uV,vV且（u,v）E。,第二步：分两方面证明“图G有一个规模至少为k的集团，当且仅当图G有一个规模至多为nk的结点覆盖。”一方面，先证明：若图G有一个规模至少为k的集团S，则图G有一个规模至多为nk的结点覆盖S，SVS。反证法：若G不能被S中的顶点所覆盖，则必定存在边(u,v)，顶点u和v均不在S 中，而在S中。这与S是图G的一个集团相矛盾。所以，S必定是图G的顶点覆盖。并且若|S|k，则|S|nk。,另一方面，需证明：若G有一个规模至多为nk的结点覆
13、盖S，则G有一个规模至少为k的集团S，S=VS。反证法：若S不是完全图，则S中至少有一对顶点uS，vS之间缺少边，该边（u,v）应属于，即S未覆盖此边。这与S是G的顶点覆盖相矛盾。因此，S必为完全图。若|S|nk，则|S|k。,3元CNF可满足性,例107（3SAT）3元CNF可满足性问题是指一个CNF公式F中，每个子句包含恰好3个文字时的可满足性问题。,可满足性的若干结果 是可满足的，当且仅当公式 f=(y1y2)(y2)(y1)()是可满足的。其中，是公式，y1和y2是变量。由于y1，y2，y1y2，y2,y1 和 不同时为真。所以，是可满足的，当且仅当公式f是可满足的。,12是可满足的，
14、当且仅当公式 f=(12y)(12)是可满足的。由于y，两者之一为假。所以，12是可满足的，当且仅当公式f是可满足的。,f1f2是可满足的，当且仅当公式 f=(f1y)(f2)是可满足的，f1和f2是公式，y是变量，并且不出现在f1和f2中。若f1f2是可满足的，则必有f1或f2为真。若f1为真，可令y为假，则f 可满足；否则，若f2为真，可令y为真，则f可满足。若f是可满足的，因为y，若y为真，则必有f2为真，若y为假，则必有f1为真。即无论y为何值，只有f1f2为真时，f 才为真。,定理105 CNF可满足性3元CNF可满足性。证明：使用上述结论，可将任意一个CNF公式在多项式时间内转换成
15、一个3元CNF公式，且这种转换能够维持可满足性不变。因此，CNF可满足性3元CNF可满足性，故3元CNF可满足性问题是NP完全的。,图的着色数,例108（图着色数判定问题）对给定的无向图G着色，是指对图中任何两个相邻顶点都分配不同颜色。图的着色问题是求对给定无向图着色所必需的最少颜色种类，而图着色判定问题是确定能否使用k种颜色对一个给定的无向图着色的问题。,定理106 3元CNF可满足性着色数判定问题。证明：仍然分两步证明这一结论。第一步：以3元CNF可满足性问题的任意一个实例公式F为输入，构造一个着色数判定问题的实例(G，k)，其中G=(V,E)为无向图，k为正整数。第二步：从两方面证明“3元CNF公式F是可满足的，当且仅当图G是n+1可着色的。”,总共3n+k个顶点,证明：3元CNF公式F是可满足的，当且仅当图G是n+1可着色的。若F是可满足的，则图G是n+1可着色的若图G是n+1可着色的，则F是可满足的,综上所述，可在多项式时间内从3元CNF可满足性问题的任意一个实例公式F，构造一个图着色数问题的实例无向图G=(V,E)，并且3元CNF公式F是可满足的，当且仅当图G是n+1可着色的，所以，3元CNF可满足性着色数判定问题，着色数判定问题是NP完全的。,
