算法分析设计10_NP完全问题

算法设计与分析张怡婷Email:[e-mail]10.2第10章NP完全问题学习要点：确定算法和不确定算法判定问题和最优化问题的关系可满足性问题P类问题和NP类问题NP难度(NPhard)和NP完全(NPcomplete)问题Cook定理典型的NP完全（或NP难度）问题的证明ch10.3章节内容:10.1基本概念10.2.1Cook定理10.3一些典型的NP完全问题ch10.410.1基本概念将能在多项式时间内求解的问题视为易处理问题(tractableproblem)。至今尚未找到多项式时间算法求解的问题视为难处理问题(intractableproblem)。——NP完全问题或NP难度(NPhard)问题——如：指数时间算法无论消耗多少计算机时间和空间也不能求解的称为不可判定(undecidable)的。——不存在任何算法求解如果任意一个NP难度问题存在一个多项式时间算法，那么所有NP完全问题都可以在多项式时间内求解。一个NP完全问题可以在多项式时间内求解，当且仅当所有其他的NP完全问题都可以在多项式时间内求解。ch10.510.1.1不确定算法和不确定机不确定算法的抽象计算模型：算法在抽象机上运行与计算机系统的性能无关；算法的执行表现为执行一个基本运算序列；基本运算的执行时间是有限常量；Choice(S)：任意选择集合S的一个元素。Failure()：发出不成功完成信号后算法终止。Success()：发出成功完成信号后算法终止。ch10.6例10-1在n个元素的数组a中查找给定元素x，如果x在其中，则确定使a[j]==x的下标j，否则输出-1。不确定搜索算法：voidSearch(inta[],Tx){intj=Choice(0,n-1);//从{0,1,...,n-1}中任意选取一个值if(a[j]==x){coutj;Success();//不确定算法成功终止}cout-1;Failure();//不确定算法失败终止}执行时间都为O(1)若算法执行中需作出一系列的Choice函数选择，当且仅当Choice的任何一组选择都不会导致成功信号时，算法在O(1)时间不成功终止。如果一个判定问题实例的解为真，Choice函数每一次总能在O(1)时间内做出导致成功的正确选择。包含不确定选择语句，并能按上述方式执行一个算法的机器称为不确定机（nondeterministicmachine)。在不确定机上执行的算法称为不确定算法(nondeterministicalgorithm)。ch10.7不确定机的执行方式，可理解为不受限制的并行计算：不确定机执行不确定算法时，每当Choice函数进行选择时，就好像复制了多个程序副本，每一种可能的选择产生一个副本，所有副本同时执行。一旦一个副本成功完成，将立即终止所有其他副本的计算。如果存在至少一种成功完成的选择，一台不确定机总能做出最佳选择，以最短的程序步数完成计算，并成功终止。不确定机能及时判断算法的某次执行不存在任何导致成功完成的选择，并使算法在一个单位时间内输出“不成功”信息后终止。显然，这种机器是虚构的，是一种概念性计算模型！ch10.8不确定搜索算法：voidSearch(inta[],Tx){intj=Choice(0,n-1);if(a[j]==x){coutj;Success();}cout-1;Failure();}定义10-1（不确定算法时间复杂度）一个不确定算法所需的时间是指对任意一个输入，当存在一个选择序列导致成功完成时，达到成功完成所需的最少程序步。在不可能成功完成的情况下，所需时间总是O(1)。若元素x在数组中，Choice函数总能在O(1)时间内选中该元素下标，并成功终止。否则，算法在O(1)时间失败终止。因此该不确定搜索算法的时间复杂度为O(1)。ch10.9例10-2将n个元素的序列排成有序序列。不确定排序算法：voidNSort(inta[],intn){intb[mSize],i,j;for(i=0;in;i++)b[i]=0;//将b初始化为0for(i=0;in;i++)//将每个a[i]存放在一个空闲的b[j]中{j=Choice(0,n-1);//任意选择一个下标if(b[j])Failure;//若b[j]≠0，则算法失败终止b[j]=a[i];//将a[i]付给b[j]}for(i=0;in-1;i++)//验证b中元素是否已经有序if(b[i]b[i+1])Failure();//若存在两元素逆序，则失败Success();//Choice函数的n次正确选择，算法成功}必定存在对b中下标的n次恰当选择，使得能将每个a[i]恰好保存在一个空闲的b[j]处，并且进一步确保b中元素排成有序序列，从而能顺利通过随后的有序性验证，导致成功终止。因此该不确定搜索算法的时间复杂度为O(n)。ch10.10判定问题和最优化问题一个只要求产生“0”或“1”作为输出的问题称为判定问题（decisionproblem）。许多最优化问题都可以得到与其相对应的判定问题，且两者往往存在计算上的相关性：一个判定问题能够在多项式时间内求解，当且仅当它相应的最优化问题可以在多项式时间内求解。如果判定问题不能在多项式时间内求解，那么它相应的最优化问题也不能在多项式时间内求解。ch10.11例10-3最大集团及其判定问题无向图G=（V,E）的一个完全子图称为该图的一个集团，集团的规模用集团的顶点数衡量。最大集团问题：确定图G的最大集团规模的问题。最大集团判定问题：判定图G是否存在一个规模至少为k的集团。（k为给定正整数）ch10.12若最大集团问题能在多项式时间O(g(n))内求解。当且仅当对应的判定问题能在多项式时间O(f(n))内求解。一方面：只需以k=1,2,...,n，最多n次调用最大集团判定算法，便可求得最大集团的大小，因此O(g(n))=O(nf(n))；另一方面：可使用求解最大集团问题的算法，求得最大集团的规模为k’。若k’≥k，则最大集团判定问题的解为“1”，否则为“0”。显然有O(f(n))=O(g(n))。许多抽象问题并不是判定问题，而是最优化问题，必须最大化或最小化某个量。然而，如我们看到的，将最优化问题转化为一个并不更难的判定问题通常是比较简单的。ch10.1310.1.2可满足性问题ix数理逻辑中，一个变量和它的非都称为文字。命题公式是由文字及逻辑运算符“与(∧)”和“或(∨)”构成的表达式。ix如果一个公式具有逻辑与形式：C1∧C2∧...∧Ck，其中每个子句Ci都是逻辑或形式li1∨li2∨...∨lip，每个lij是文字，则将这种形式的公式称为合取范式(conjunctivenormalform，CNF)。如果一个公式具有逻辑或形式：C1∨C2∨...∨Ck，其中每个子句Ci都是逻辑与形式li1∧li2∧...∧liq，每个lij是文字，则将这种形式的公式称为析取范式(disjunctivenormalform，DNF)。ch10.14例10-4可满足性问题（satisfiabilityproblem)是一个判定问题，确定对于一个给定的命题公式，是否存在布尔变量的一种赋值（也称真值指派）使该公式为真。例如：公式是可满足的。只需令x1=1，x2=0，x3=0。1231231212()()()()xxxxxxxxxx公式是不可满足的。121323121323()()()()()()xxxxxxxxxxxxch10.15程序10-4可满足性问题的不确定算法voidEval(CNFE,intn){intx[mSize];for(inti=1;i=n;i++)//O(n)x[i]=Choice(0,1);//为变量x[i]赋0或1值if(E(x,n))Success();//O(e)，计算公式E(x,n)的值//若为真，成功终止elseFailure();}因为：对n个布尔变量赋值需要O(n)时间，计算公式E(x,n)的时间为O(e)，e是公式长度。所以，可满足性问题的不确定算法时间为O(n+e)。ch10.1610.1.3P类和NP类问题P类问题：可在多项式时间内用确定算法求解的判定问题。NP类问题：可在多项式时间内用不确定算法求解的判定问题。（多项式时间内可验证问题的解。）确定算法是不确定算法当Choice函数只有一种选择时的特例，所以有：但至今无法断定：是否P=NP或者P≠NP。PNPch10.17定义10-3多项式约化令Q1和Q2是两个问题，如果存在一个确定算法A求解Q1，而算法A以多项式时间调用另一个求解Q2的确定算法B。若不计B的工作量，算法A是多项式时间的，则称Q1约化(reducedto)为Q2，记作Q1∝Q2。即：求解Q1的确定算法是通过调用求解Q2的确定算法完成的，对Q2算法实施的调用过程所需的时间是多项式时间的。那么：只要对问题Q2存在多项式时间求解算法，问题Q1就能在多项式时间内得以求解。ch10.18约化存在以下性质：性质10-1若Q1∈P，Q2∝Q1，则有Q2∈P。性质10-2（传递性）若Q1∝Q2，Q2∝Q3，则Q1∝Q3。ch10.1910.1.4NP难度和NP完全问题性质10-4NP难度（NPhard）对任意问题Q1∈NP都有Q1∝Q，则称问题Q是NP难度（NPhard）的。只要对任何一个NP难度问题Q找到了它的多项式时间算法，那么，可以断定所有NP类问题都能在多项式时间内求解，因为所有NP类问题都能约化到问题Q。（然而目前尚无任何一个NP难度问题具有多项式时间算法。）ch10.20性质10-5NP完全（NPcomplete）对于问题Q∈NP且Q是NP难度的，则称Q是NP完全（NPcomplete，NPC）的。所有NP完全问题都是NP难度的，反之不然，NP难度问题不一定是NP完全的（若不是NP类问题，则不是NP完全的）。ch10.21现实意义：若一个问题被证明是NP难度（NPhard）的，则很难找到一个多项式时间的有效算法。若问题的实例规模较大，则应选择采用启发式算法、随机算法或近似算法等其他算法策略求解。如何确定某个问题是否是NP难度的？ch10.22证明某个问题Q是NP难度（NPhard）的证明策略：(1)选择一个已经证明是NP难度问题Q1;(2)求证Q1∝Q。则问题Q是NP难度的。•由于Q1是NP难度的，因此所有NP类问题都可约化到Q1。•根据约化的传递性，任何NP类问题都可约化到Q。•所以，Q是NP难度的。在此基础上，若进一步表明Q本身是NP类的，则问题Q是NP完全的。ch10.2310.2Cook定理和证明10.2.1Cook定理斯蒂芬•库克（StevenCook）于1971年证明了第一个NP完全问题，称为Cook定理，表明可满足性问题是NP完全的。至今至少已有300多个问题被证明是NP难度问题，但尚未证明其中任何一个是属于P的。ch10.2410.3一些典型的NP完全问题证明(一个猜想可能是NP难度的)问题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完全的。ch10.2510.3.1最大集团最大集团判定问题是NP类问题。“集团”是无向图中的完全子图，任意一对顶点间有边相连。P231程序10-3是求解该问题的多项式时间不确定算法。或：对给定的图G=(V,E)，检查顶点集V’V中每一对顶点u,v间是否存在边(u,v)∈E，即可在多项式时间内完成对V’是否是集团的检查。ch10.26最大集团判定问题是N