算法设计与分析：第10章 NP完全问题.ppt

ch10.1第第1010章章 NPNP完全问题完全问题学习要点：l确定算法和不确定算法l判定问题和最优化问题的关系l可满足性问题lP类问题和NP类问题lNP难度(NP hard)和NP完全(NP complete)问题lCook定理l典型的NP完全（或NP难度）问题的证明ch10.2l l章节内容章节内容: :10.1 10.1 基本概念基本概念10.2.1 Cook10.2.1 Cook定理定理10.3 10.3 一些典型的一些典型的NPNP完全问题完全问题ch10.310.1 10.1 基本概念基本概念l将能在多项式时间内求解的问题视为易处理问题(tractable problem)l至今尚未找到多项式时间算法求解的问题视为难处理问题(intractable problem)NP完全问题或NP难度(NP hard)问题如：指数时间算法l无论消耗多少计算机时间和空间也不能求解的称为不可判定(undecidable)的不存在任何算法求解如果任意一个NP难度问题存在一个多项式时间算法，那么所有NP完全问题都可以在多项式时间内求解一个NP完全问题可以在多项式时间内求解，当且仅当所有其他的NP完全问题都可以在多项式时间内求解。

ch10.410.1.1 10.1.1 不确定算法和不确定机不确定算法和不确定机不确定算法的抽象计算模型：l算法在抽象机上运行与计算机系统的性能无关；l算法的执行表现为执行一个基本运算序列；l基本运算的执行时间是有限常量； Choice(S)：任意选择集合S的一个元素 Failure()：发出不成功完成信号后算法终止 Success()：发出成功完成信号后算法终止ch10.5例例10-110-1 在在n n个元素的数组个元素的数组a a中查找给定元素中查找给定元素x x，如果，如果x x在其中，则确定使在其中，则确定使aj=xaj=x的下标的下标j j，否则输出，否则输出-1-1不确定搜索算法：void Search(int a,T x) int j=Choice(0,n-1);/从0,1,.,n-1中任意选取一个值 if(aj=x) coutj;Success();/不确定算法成功终止 cout-1; Failure();/不确定算法失败终止执行时间都为O(1)若算法执行中需作出一系列的Choice函数选择，当且仅当Choice的任何一组选择都不会导致成功信号时，算法在O(1)时间不成功终止。

如果一个判定问题实例的解为真，Choice函数每一次总能在O(1)时间内做出导致成功的正确选择包含不确定选择语句，并能按上述方式执行一个算法的机器称为不确定机（non deterministic machine)在不确定机上执行的算法称为不确定算法(non deterministic algorithm)ch10.6不确定机的执行方式，可理解为不受限制的并行计算： 不确定机执行不确定算法时，每当Choice函数进行选择时，就好像复制了多个程序副本，每一种可能的选择产生一个副本，所有副本同时执行一旦一个副本成功完成，将立即终止所有其他副本的计算 如果存在至少一种成功完成的选择，一台不确定机总能做出最佳选择，以最短的程序步数完成计算，并成功终止 不确定机能及时判断算法的某次执行不存在任何导致成功完成的选择，并使算法在一个单位时间内输出“不成功”信息后终止显然，这种机器是虚构的，是一种概念性计算模型！ch10.7不确定搜索算法：void Search(int a,T x) int j=Choice(0,n-1); if(aj=x) coutj;Success(); cout-1; Failure();定义10-1 （不确定算法时间复杂度）一个不确定算法所需的时间是指对任意一个输入，当存在一个选择序列导致成功完成时，达到成功完成所需的最少程序步。

在不可能成功完成的情况下，所需时间总是O(1)若元素x在数组中，Choice函数总能在O(1)时间内选中该元素下标，并成功终止否则，算法在O(1)时间失败终止因此该不确定搜索算法的时间复杂度为O(1)ch10.8例例10-210-2 将将n n个元素的序列排成有序序列个元素的序列排成有序序列不确定排序算法：void NSort(int a,int n) int bmSize,i,j; for (i=0;in;i+) bi=0; /将b初始化为0 for (i=0;in;i+) /将每个ai存放在一个空闲的bj中 j=Choice(0,n-1);/任意选择一个下标if (bj) Failure;/若bj0，则算法失败终止bj=ai;/将ai付给bj for (i=0;ibi+1) Failure();/若存在两元素逆序，则失败 Success();/Choice函数的n次正确选择，算法成功必定存在对b中下标的n次恰当选择，使得能将每个ai恰好保存在一个空闲的bj处，并且进一步确保b中元素排成有序序列，从而能顺利通过随后的有序性验证，导致成功终止因此该不确定搜索算法的时间复杂度为O(n)ch10.9判定问题和最优化问题判定问题和最优化问题一个只要求产生“0”或“1”作为输出的问题称为判定问题（decision problem）。

许多最优化问题都可以得到与其相对应的判定问题，且两者往往存在计算上的相关性：一个判定问题能够在多项式时间内求解，当且仅当它相应的最优化问题可以在多项式时间内求解如果判定问题不能在多项式时间内求解，那么它相应的最优化问题也不能在多项式时间内求解ch10.10例10-3 最大集团及其判定问题无向图G=（V,E）的一个完全子图称为该图的一个集团，集团的规模用集团的顶点数衡量 最大集团问题：确定图G的最大集团规模的问题 最大集团判定问题：判定图G是否存在一个规模至少为k的集团k为给定正整数）ch10.11若最大集团问题能在多项式时间O(g(n)内求解当且仅当对应的判定问题能在多项式时间O(f(n)内求解一方面：只需以k=1,2,.,n，最多n次调用最大集团判定算法，便可求得最大集团的大小，因此O(g(n)=O(nf(n)；另一方面：可使用求解最大集团问题的算法，求得最大集团的规模为k若kk，则最大集团判定问题的解为“1”，否则为“0”显然有O(f(n)=O(g(n)许多抽象问题并不是判定问题，而是最优化问题，必须最大化或最小化某个量然而，如我们看到的，将最优化问题转化为一个并不更难的判定问题通常是比较简单的。

ch10.1210.1.2 10.1.2 可满足性问题可满足性问题l数理逻辑中，一个变量 和它的非 都称为文字l命题公式是由文字及逻辑运算符“与()”和“或()”构成的表达式l如果一个公式具有逻辑与形式：C1C2.Ck，其中每个子句Ci都是逻辑或形式li1li2.lip，每个lij是文字，则将这种形式的公式称为合取范式(conjunctive normal form，CNF)l如果一个公式具有逻辑或形式：C1C2.Ck，其中每个子句Ci都是逻辑与形式li1li2 . liq，每个lij是文字，则将这种形式的公式称为析取范式(disjunctive normal form，DNF)ch10.13例10-4 可满足性问题（satisfiability problem)是一个判定问题，确定对于一个给定的命题公式，是否存在布尔变量的一种赋值（也称真值指派）使该公式为真例如：公式是可满足的只需令x1=1，x2=0，x3=0公式是不可满足的ch10.14程序程序10-4 10-4 可满足性问题的不确定算法可满足性问题的不确定算法void Eval(CNF E, int n) int xmSize; for (int i=1;i=n;i+) /O(n)xi=Choice(0,1);/为变量xi赋0或1值 if (E(x,n) Success();/O(e)，计算公式E(x,n)的值/若为真，成功终止 else Failure();因为：对n个布尔变量赋值需要O(n)时间，计算公式E(x,n)的时间为O(e)，e是公式长度。

所以，可满足性问题的不确定算法时间为O(n+e)ch10.1510.1.3 P10.1.3 P类和类和NPNP类问题类问题P类问题：可在多项式时间内用确定算法求解的判定问题NP类问题：可在多项式时间内用不确定算法求解的判定问题多项式时间内可验证问题的解确定算法是不确定算法当Choice函数只有一种选择时的特例，所以有：但至今无法断定：是否P=NP或者PNPch10.16定义10-3 多项式约化令Q1和Q2是两个问题，如果存在一个确定算法A求解Q1，而算法A以多项式时间调用另一个求解Q2的确定算法B若不计B的工作量，算法A是多项式时间的，则称Q1约化(reduced to)为Q2，记作Q1Q2即： 求解Q1的确定算法是通过调用求解Q2的确定算法完成的， 对Q2算法实施的调用过程所需的时间是多项式时间的那么：只要对问题Q2存在多项式时间求解算法，问题Q1就能在多项式时间内得以求解ch10.17约化存在以下性质：性质10-1 若Q1P，Q2Q1，则有Q2 P性质10-2 （传递性）若Q1Q2，Q2Q3，则Q1Q3ch10.1810.1.4 NP10.1.4 NP难度和难度和NPNP完全问题完全问题性质10-4 NP难度（NP hard） 对任意问题Q1NP都有Q1Q，则称问题Q是NP难度（NP hard）的。

只要对任何一个NP难度问题Q找到了它的多项式时间算法，那么，可以断定所有NP类问题都能在多项式时间内求解，因为所有NP类问题都能约化到问题Q然而目前尚无任何一个NP难度问题具有多项式时间算法ch10.19性质10-5 NP完全（NP complete） 对于问题QNP且Q是NP难度的，则称Q是NP完全（NP complete，NPC）的所有NP完全问题都是NP难度的，反之不然，NP难度问题不一定是NP完全的（若不是NP类问题，则不是NP完全的）ch10.20现实意义：若一个问题被证明是NP难度（NP hard）的，则很难找到一个多项式时间的有效算法若问题的实例规模较大，则应选择采用启发式算法、随机算法或近似算法等其他算法策略求解如何确定某个问题是否是NP难度的？ch10.21证明某个问题Q是NP难度（NP hard）的证明策略：(1)选择一个已经证明是NP难度问题Q1;(2)求证Q1Q则问题Q是NP难度的由于Q1是NP难度的，因此所有NP类问题都可约化到Q1根据约化的传递性，任何NP类问题都可约化到Q所以，Q是NP难度的在此基础上，若进一步表明Q本身是NP类的，则问题Q是NP完全的ch10.2210.2 Cook10.2 Cook定理和证明定理和证明10.2.1 Cook10.2.1 Cook定理定理斯蒂芬库克（Steven Cook）于1971年证明了第一个NP完全问题，称为Cook定理，表明可满足性问题是NP完全的。

至今至少已有300多个问题被证明是NP难度问题，但尚未证明其中任何一个是属于P的ch10.2310.3 10.3 一些典型的一些典型的NPNP完全问题完全问题证明(一个猜想可能是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完全的ch10.2410.3.1 10.3.1 最大集团最大集团最大集团判定问题是NP类问题集团”是无向图中的完全子图，任意一对顶点间有边相连 P231 程序10-3是求解该问题的多项式时间不确定算法。