算法10_NP完全问题

算法设计与分析,张怡婷Email:zytnjupt.edu.cn,第10章 NP完全问题,学习要点：确定算法和不确定算法判定问题和最优化问题的关系可满足性问题P类问题和NP类问题NP难度(NP hard)和NP完全(NP complete)问题Cook定理典型的NP完全（或NP难度）问题的证明,章节内容:10.1 基本概念10.2.1 Cook定理10.3 一些典型的NP完全问题,10.1 基本概念,将能在多项式时间内求解的问题视为易处理问题(tractable problem)。至今尚未找到多项式时间算法求解的问题视为难处理问题(intractable problem)。NP完全问题或NP难度(NP hard)问题如：指数时间算法无论消耗多少计算机时间和空间也不能求解的称为不可判定(undecidable)的。不存在任何算法求解,如果任意一个NP难度问题存在一个多项式时间算法，那么所有NP完全问题都可以在多项式时间内求解。一个NP完全问题可以在多项式时间内求解，当且仅当所有其他的NP完全问题都可以在多项式时间内求解。,10.1.1 不确定算法和不确定机,不确定算法的抽象计算模型：算法在抽象机上运行与计算机系统的性能无关；算法的执行表现为执行一个基本运算序列；基本运算的执行时间是有限常量；,Choice(S)：任意选择集合S的一个元素。Failure()：发出不成功完成信号后算法终止。Success()：发出成功完成信号后算法终止。,例10-1 在n个元素的数组a中查找给定元素x，如果x在其中，则确定使aj=x的下标j，否则输出-1。,不确定搜索算法：void Search(int a,T x) int j=Choice(0,n-1);/从0,1,.,n-1中任意选取一个值 if(aj=x) cout<<j;Success();/不确定算法成功终止 cout<<-1; Failure();/不确定算法失败终止,若算法执行中需作出一系列的Choice函数选择，当且仅当Choice的任何一组选择都不会导致成功信号时，算法在O(1)时间不成功终止。,如果一个判定问题实例的解为真，Choice函数每一次总能在O(1)时间内做出导致成功的正确选择。,包含不确定选择语句，并能按上述方式执行一个算法的机器称为不确定机（non deterministic machine)。,在不确定机上执行的算法称为不确定算法(non deterministic algorithm)。,不确定机的执行方式，可理解为不受限制的并行计算：不确定机执行不确定算法时，每当Choice函数进行选择时，就好像复制了多个程序副本，每一种可能的选择产生一个副本，所有副本同时执行。一旦一个副本成功完成，将立即终止所有其他副本的计算。如果存在至少一种成功完成的选择，一台不确定机总能做出最佳选择，以最短的程序步数完成计算，并成功终止。不确定机能及时判断算法的某次执行不存在任何导致成功完成的选择，并使算法在一个单位时间内输出“不成功”信息后终止。,显然，这种机器是虚构的，是一种概念性计算模型！,不确定搜索算法：void Search(int a,T x) int j=Choice(0,n-1); if(aj=x) cout<<j;Success(); cout<<-1; Failure();,定义10-1 （不确定算法时间复杂度）一个不确定算法所需的时间是指对任意一个输入，当存在一个选择序列导致成功完成时，达到成功完成所需的最少程序步。在不可能成功完成的情况下，所需时间总是O(1)。,例10-2 将n个元素的序列排成有序序列。,不确定排序算法：void NSort(int a,int n) int bmSize,i,j; for (i=0;ibi+1) Failure();/若存在两元素逆序，则失败 Success();/Choice函数的n次正确选择，算法成功,判定问题和最优化问题,一个只要求产生“0”或“1”作为输出的问题称为判定问题（decision problem）。,许多最优化问题都可以得到与其相对应的判定问题，且两者往往存在计算上的相关性：,一个判定问题能够在多项式时间内求解，当且仅当它相应的最优化问题可以在多项式时间内求解。,如果判定问题不能在多项式时间内求解，那么它相应的最优化问题也不能在多项式时间内求解。,例10-3 最大集团及其判定问题无向图G=（V,E）的一个完全子图称为该图的一个集团，集团的规模用集团的顶点数衡量。,最大集团问题：确定图G的最大集团规模的问题。,最大集团判定问题：判定图G是否存在一个规模至少为k的集团。（k为给定正整数）,若最大集团问题能在多项式时间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)。,许多抽象问题并不是判定问题，而是最优化问题，必须最大化或最小化某个量。然而，如我们看到的，将最优化问题转化为一个并不更难的判定问题通常是比较简单的。,10.1.2 可满足性问题,数理逻辑中，一个变量 和它的非 都称为文字。命题公式是由文字及逻辑运算符“与()”和“或()”构成的表达式。,如果一个公式具有逻辑与形式：C1C2.Ck，其中每个子句Ci都是逻辑或形式li1li2.lip，每个lij是文字，则将这种形式的公式称为合取范式(conjunctive normal form，CNF)。,如果一个公式具有逻辑或形式：C1C2.Ck，其中每个子句Ci都是逻辑与形式li1li2 . liq，每个lij是文字，则将这种形式的公式称为析取范式(disjunctive normal form，DNF)。,例10-4 可满足性问题（satisfiability problem)是一个判定问题，确定对于一个给定的命题公式，是否存在布尔变量的一种赋值（也称真值指派）使该公式为真。,例如：公式是可满足的。只需令x1=1，x2=0，x3=0。,公式是不可满足的。,程序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)。,10.1.3 P类和NP类问题,P类问题：可在多项式时间内用确定算法求解的判定问题。NP类问题：可在多项式时间内用不确定算法求解的判定问题。（多项式时间内可验证问题的解。）,确定算法是不确定算法当Choice函数只有一种选择时的特例，所以有：但至今无法断定：是否P=NP或者PNP。,定义10-3 多项式约化令Q1和Q2是两个问题，如果存在一个确定算法A求解Q1，而算法A以多项式时间调用另一个求解Q2的确定算法B。若不计B的工作量，算法A是多项式时间的，则称Q1约化(reduced to)为Q2，记作Q1Q2。,约化存在以下性质：,性质10-1 若Q1P，Q2Q1，则有Q2 P。,性质10-2 （传递性）若Q1Q2，Q2Q3，则Q1Q3。,10.1.4 NP难度和NP完全问题,性质10-4 NP难度（NP hard） 对任意问题Q1NP都有Q1Q，则称问题Q是NP难度（NP hard）的。,只要对任何一个NP难度问题Q找到了它的多项式时间算法，那么，可以断定所有NP类问题都能在多项式时间内求解，因为所有NP类问题都能约化到问题Q。（然而目前尚无任何一个NP难度问题具有多项式时间算法。）,性质10-5 NP完全（NP complete） 对于问题QNP且Q是NP难度的，则称Q是NP完全（NP complete，NPC）的。,所有NP完全问题都是NP难度的，反之不然，NP难度问题不一定是NP完全的（若不是NP类问题，则不是NP完全的）。,现实意义：若一个问题被证明是NP难度（NP hard）的，则很难找到一个多项式时间的有效算法。若问题的实例规模较大，则应选择采用启发式算法、随机算法或近似算法等其他算法策略求解。,如何确定某个问题是否是NP难度的？,证明某个问题Q是NP难度（NP hard）的证明策略：(1)选择一个已经证明是NP难度问题Q1;(2)求证Q1Q。则问题Q是NP难度的。,由于Q1是NP难度的，因此所有NP类问题都可约化到Q1。根据约化的传递性，任何NP类问题都可约化到Q。所以，Q是NP难度的。,在此基础上，若进一步表明Q本身是NP类的，则问题Q是NP完全的。,10.2 Cook定理和证明,10.2.1 Cook定理,斯蒂芬库克（Steven Cook）于1971年证明了第一个NP完全问题，称为Cook定理，表明可满足性问题是NP完全的。至今至少已有300多个问题被证明是NP难度问题，但尚未证明其中任何一个是属于P的。,10.3 一些典型的NP完全问题,证明(一个猜想可能是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 最大集团,最大集团判定问题是NP类问题。,“集团”是无向图中的完全子图，任意一对顶点间有边相连。,P231 程序10-3是求解该问题的多项式时间不确定算法。或：对给定的图G=(V,E)，检查顶点集V V中每一对顶点u,v间是否存在边(u,v) E，即可在多项式时间内完成对V是否是集团的检查。,最大集团判定问题是NP完全的。,下面证明：,证明思路：证明CNF可满足性最大集团判定问题，所以最大集团判定问题是NP难度的。又因为最大集团判定问题是NP类问题（前面已证）所以最大集团判定问题是NP完全的。,定理10-3 CNF可满足性最大集团判定问题,证明：1、在多项式时间内，以任意给定的CNF公式F为输入，构造一个相应的无向图G；2、证明F是可满足的，当且仅当G有一个规模至少为k的集团。,定理10-3 CNF可满足性最大集团判定问题,证明：1、在多项式时间内，以任意给定的CNF公式F为输入，构造一个相应的无向图G；令F=C1C2 . Ck是一个具有k个子句的CNF形式的布尔公式。由公式F构造无向图G的方法为：V=|是子句Ci的一个文字 E=(,)| ij 且 ,和处于不同的分句中,