《算法设计与分析》第10章.ppt

第10章 NP完全问题,10.1 基本概念 10.2 Cook定理和证明 10.3 一些典型的NP完全问题,10.1 基本概念,将能在多项式时间求解的问题看作易处理问题(tractable problem)，而将至今尚未找到多项式时间算法求解的问题视为难处理问题(intractable problem)。,10.1.1 不确定算法和不确定机,为便于研究，先假定一种运行不确定算法的抽象计算模型，该抽象机除了包含第2.1.3节的抽象机模型的基本运算外，最根本的区别在于它新增了下面一个新函数和两个新语句： （1）Choice(S)：任意选择集合S的一个元素； （2）Failure：发出不成功完成信号后算法终止； （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)时间不成功终止；否则，只要存在一组选择能够导致成功时，算法总能采取该组选择使得算法成功终止。 包含不确定选择语句，并能按上述方式执行一个算法的机器称为不确定机（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+)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,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 xmSize; for(int i=1;i=n;i+) xi=Choice(0,1); if(E(x,n) Success(); else Failure(); ,10.1.3 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。 性质10-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.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难度的问题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.1 最大集团,定理10-3 CNF可满足性最大集团判定问题。 证明 分两步证明这一定理：首先寻找一种方法，它能在多项式时间内，从任意给定的CNF公式F构造一个无向图G=(V, E)；然后证明，F是可满足的，当且仅当G有一个规模至少为k的集团。,第一步：以任意给定的CNF公式F为输入，构造一个相应的无向图G，并且这种构造能够在多项式时间内完成。 令 是一个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(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 最大集团判定问题顶点覆盖判定问题。 证明：分两步证明这一结论。 第一步：以最大集团判定问题的任一实例(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的结点覆盖S，则G有一个规模至少为k的集团S，S=VS。 反证法：若S不是完全图，则S中至少有一对顶点uS，vS之间缺少边，该边（u,v）应属于 ，即S未覆盖此边。这与S是G的顶点覆盖相矛盾。因此，S必为完全图。若|S|nk，则|S|k。,10.3.3 3元CNF可满足性,例107 （3SAT）3元CNF可满足性问题是指一个CNF公式F中，每个子句包含恰好3个文字时的可满足性问题。,可满足性的若干结果 是可满足的，当且仅当公式 f = ( y1y2)( y2) (y1 )( ) 是可满足的。其中，是公式，y1和y2是变量。由于y1 ，y2 ， y1y2， y2, y1 和 不同时为真。所以，是可满足的，当且仅当公式f是可满足的。,12是可满足的，当且仅当公式 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公式在多项式时间内转换成一个3元CNF公式，且这种转换能够维持可满足性不变。 因此，CNF可满足性3元CNF可满足性，故3元CNF可满足性问题是NP完全的。,10.3.4 图的着色数,例108 （图着色数判定问题）对给定的无向图G着色，是指对图中任何两个相邻顶点都分配不同颜色。图的着色问题是求对给定无向图着色所必需的最少颜色种类，而图着色判定问题是确定能否使用k种颜色对一个给定的无向图着色的问题。,定理106 3元CNF可满足性着色数判定问题。 证明：仍然分两步证明这一结论。 第一步：以3元CNF可满足性问题的任意一个实例公式F为输入，构造一个着色数判定问题的实例(G，k)，其中G=(V,E)为无向图，k为正整数。 第二步：从两