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

南京邮电大学计算机学院 2008年3月,算法设计与分析,DeSign and Analysis of AlgorithmsIn C++,,,“十一五”国家级规划教材,陈慧南 编著,电子工业出版社,南京邮电大学计算机学院 2008年3月,第3部分 求解困难问题,,南京邮电大学计算机学院 2008年3月,第10章 NP完全问题,,南京邮电大学计算机学院 2008年3月,10.1 基本概念 10.2 Cook定理和证明 10.3 一些典型的NP完全问题,南京邮电大学计算机学院 2008年3月,10.1   基本概念,,,,南京邮电大学计算机学院 2008年3月,将能在多项式时间求解的问题看作易处理问题(tractable problem)，而将至今尚未找到多项式时间算法求解的问题视为难处理问题(intractable problem)南京邮电大学计算机学院 2008年3月,10.1.1 不确定算法和不确定机,,,为便于研究，先假定一种运行不确定算法的抽象计算模型，该抽象机除了包含第2.1.3节的抽象机模型的基本运算外，最根本的区别在于它新增了下面一个新函数和两个新语句：（1）Choice(S)：任意选择集合S的一个元素；  （2）Failure：发出不成功完成信号后算法终止；（3）Success：发出成功完成信号后算法终止。

南京邮电大学计算机学院 2008年3月,例10－1 在n个元素的数组a中查找给定元素x，如果x在其中，则确定使a[j]==x的下标j，否则输出-1 【程序10－1】不确定搜索算法 void Search(int a[],T x) { int j=Choice(0,n-1); if(a[j]==x) { cout<

南京邮电大学计算机学院 2008年3月,例10-2 将n个元素的序列排成有序序列程序10-2】 不确定排序算法void NSort(int a[],int n){ int b[mSize],i,j; for (i=0;ib[i+1]) Failure(); for (i=0;i

在不可能成功完成的情况下，所需时间总是O(1)南京邮电大学计算机学院 2008年3月,例10-3 （最大集团及其判定问题）无向图G=(V, E)的一个完全子图称为该图的一个集团（clique）集团的规模用集团的顶点数衡量最大集团问题是确定图G的最大集团规模的问题最大集团判定问题（G, k）是对给定正整数k，判定图G是否存在一个规模至少为k的集团南京邮电大学计算机学院 2008年3月,【程序10-3】 最大集团判定问题不确定算法void Clique（int g[][mSize],int n,int k）{ S=; for(int i=0;i< k;i++){ int t=Choice(0,n-1); if (tS) Failure(); S=S∪{t}; } for ( 对所有(i,j)，iS，jS且ij) if((i,j)E) Failure(); Success();},南京邮电大学计算机学院 2008年3月,10.1.2 可满足性问题,例10-4 可满足性问题（satisfiability problem）是一个判定问题，它确定对于一个给定的命题公式，是否存在布尔变量的一种赋值（也称真值指派）使该公式为真。

CNF可满足性是指判定一个CNF公式的可满足性南京邮电大学计算机学院 2008年3月,【程序10-4】可满足性问题的不确定算法 void Eval(CNF E,int n) { int x[mSize]; for(int i=1;i<=n;i++) x[i]=Choice(0,1); if(E(x,n)) Success(); else Failure(); },南京邮电大学计算机学院 2008年3月,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，记做Q1∝Q2南京邮电大学计算机学院 2008年3月,性质10-1 若Q1P，Q2∝Q1，则有Q2P性质10-2 若Q1∝Q2，Q2∝Q3，则Q1∝Q3。

南京邮电大学计算机学院 2008年3月,10.1.4 NP难度和NP完全问题,定义10-4 （NP难度）对于问题Q以及任意问题Q1NP，都有Q1∝Q，则称Q是NP难度（NP hard）的定义10-5 （NP完全）对于问题QNP，Q是NP难度的，则称Q是NP完全（NP complete）的南京邮电大学计算机学院 2008年3月,如何确定某个问题Q是否是NP难度的？一般的证明策略由以下两步组成：（1）选择一个已经证明是NP难度问题Q1；（2）求证Q1∝Q由于Q1是NP难度的，因此所有NP类问题都可约化到Q1，根据约化的传递性，任何NP类问题都可约化到Q，所以Q是NP难度的如果进一步表明Q本身是NP类的，则问题Q是NP完全的南京邮电大学计算机学院 2008年3月,10.2 Cook定理和证明,,,,南京邮电大学计算机学院 2008年3月,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完全的南京邮电大学计算机学院 2008年3月,10.3 一些典型的NP完全问题,,,,南京邮电大学计算机学院 2008年3月,证明一个问题Q是NP难度（或NP完全）问题的具体步骤如下：（1）选择一个已知其具有NP难度的问题Q1；（2）证明能够从Q1的一个实例I1，在多项式时间内构造Q的一个实例I；（3）证明能够在多项式时间内从I的解确定I1的解4）从（2）和（3）可知，Q1∝Q；（5）由（1）和（4）及约化的传递性得出所有NP类问题均可约化到Q，所以Q是NP难度的；（6）如果Q是NP类问题，则Q是NP完全的南京邮电大学计算机学院 2008年3月,10.3.1 最大集团,定理10-3 CNF可满足性∝最大集团判定问题证明 分两步证明这一定理：首先寻找一种方法，它能在多项式时间内，从任意给定的CNF公式F构造一个无向图G=(V, E)；然后证明，F是可满足的，当且仅当G有一个规模至少为k的集团南京邮电大学计算机学院 2008年3月,第一步：以任意给定的CNF公式F为输入，构造一个相应的无向图G，并且这种构造能够在多项式时间内完成。

令是一个CNF形式的命题公式，xi，1in，是F中的变量由F生成一个无向图G=(V,E)的方法为：V={<,i>|是子句Ci的一个文字}，E={(<,i>,<,j>)|ij且  }南京邮电大学计算机学院 2008年3月,南京邮电大学计算机学院 2008年3月,第二步：如果能够证明F可满足，当且仅当G有一个规模至少为k的集团，那么，便证明了CNF可满足性问题可以约化到最大集团判定问题分两方面证明此结论: 一方面，若F是可满足的，则必定存在对n个布尔变量的一种赋值，使得每个子句Ci中至少有一个文字为真 另一方面，若G有一个规模至少为k的集团G’＝（S，E’）， 设S={<1,1>,<2,2>,, <k,k>}是集团的顶点集合，则必有i ，ij，若不然，则顶点<i，i>和<j，j>之间没有边，S不是集团南京邮电大学计算机学院 2008年3月,例10-5 设有命题公式F，,,,图G(V.E) 有大小为2的集团，F是可满足的（可令x1＝true，x2＝false）,南京邮电大学计算机学院 2008年3月,10.3.2 顶点覆盖,例10－6 （顶点覆盖判定问题）对于无向图G＝(V,E)，集合SV，如果E中所有边都至少有一个顶点在S中，则称S是图G的一个顶点覆盖。

覆盖的规模是S中顶点的数目|S|顶点覆盖（vertex cover）问题是指求图G的最小规模的顶点覆盖，而顶点覆盖判定问题是确定图G是否存在规模至多为k的顶点覆盖南京邮电大学计算机学院 2008年3月,对于图中所示的无向图G，S1={1，3}和S2={0，2，4}分别是图G的顶点覆盖，S1是最小覆盖，其规模为2南京邮电大学计算机学院 2008年3月,定理10－4 最大集团判定问题∝顶点覆盖判定问题证明：分两步证明这一结论第一步：以最大集团判定问题的任一实例(G，k)，G=(V，E)，k为正整数，来构造一个顶点覆盖判定问题的实例(G’，n-k)，G’=(V， )，n=|V|， ={(u,v)|uV,vV且（u,v）E}南京邮电大学计算机学院 2008年3月,第二步：分两方面证明“图G有一个规模至少为k的集团，当且仅当图G’有一个规模至多为nk的结点覆盖一方面，先证明：若图G有一个规模至少为k的集团S，则图G’有一个规模至多为nk的结点覆盖S’，S’＝VS反证法：若G’不能被S’中的顶点所覆盖，则必定存在边(u,v) ，顶点u和v均不在S’ 中，而在S中。

这与S是图G的一个集团相矛盾所以，S’必定是图G’的顶点覆盖并且若|S|k，则|S’| nk。