第10章NP完全问题.ppt

1,第10章 NP完全问题,2,10.1 引言10.2 P类10.3 NP类10.4 NP完全问题10.5 co-NP类(略)10.6 NPI类(略)10.7 四种类之间的关系(略)10.x 近似算法初步,3,10.1 引言 在前面的各章中，我们对一些算法的设计和分析进行了讨论，这些算法的运行时间可用低次多项式来表示。在这一章，我们将注意力集中在这样一类问题，这些问题至今没有找到有效算法，而且今后也有可能证明它们不存在有效算法。设是任意问题，如果对该问题存在一个算法，它的时间复杂性是O(nk)，其中n是输入大小、k是非负整数，我们说问题存在多项式时间算法。现实世界的许多问题并不属于这个范畴，因为求解这些问题耗费的时间需用指数函数或阶乘函数来表示。,4,易求解问题 存在多项式时间算法。难解问题 到目前为止不存在多项式时间算法。本章将研究难解问题的一个子类，通常称为NP完全问题(NPC问题)。这一类问题目前约有3000多个，其中还包括数百个著名问题。它们有一个共同特性，如果它们中的一个是多项式可解的话，那么所有其它问题也是多项式可解的。现存的求解这些问题算法的运行时间，对于中等大小的输入也要用几百或几千年的时间。,5,判定问题 为了研究问题的复杂性，我们必须将问题抽象。为了简化问题，我们只考虑一类简单的问题，称为“判定性问题”。也就是说提出一个问题，只需要回答Yes或者No。任何一般的最优化问题都可以转化为一系列判定性问题。例如，求图中从结点A到结点B的最短路径。该问题可以转化成如下形式：从A到B是否有长度为1的最短路径？No从A到B是否有长度为2的最短路径？No？No从A到B是否有长度为k-1的最短路径？No从A到B是否有长度为k的最短路径？Yes 如果问到了k的时候，回答了Yes，则停止发问。我们可以说，从结点A到结点B的最短路径长度为k。,6,10.2 P类确定性算法定义10.1(Page 176)设A是求解问题的一个算法。如果在展示问题的一个实例时，在整个执行过程中每一步都只有一种选择，则称A是确定性算法。因此对于同样的输入，实例一遍又一遍地执行，它的输出从不改变。在前面各章所讨论的所有算法都是确定性的。给出一个无向图G=(V,E)，它有哈密顿回路吗？即在图中是否存在一条恰好访问每个结点一次的回路。可以用穷举法来求解，一条回路一条回路检查下去，最终便能得到结果。但是穷举法的算法时间复杂性是指数级的，计算时间随问题规模成指数型增长，问题很快就变得不可计算了，所以确定性算法对此类问题无效。,7,P类定义定义10.2(Page 176)判定问题的P类由这样的判定问题组成，它们的Yes/No解可以用确定性算法在运行多项式步数内，例如在O(nk)步内得到，其中k是某个非负整数，n是输入大小。例1：给出一个有n个整数的表，它们是否按降序排列？答：只要检查表中相邻二个数即可，运行时间为O(n)。例2：给出二个整数集合，它们的交集是否为空？答：先将所有整数排序，然后检查相邻二数是否相等，显然运行时间为 O(nlog2n)。,8,10.3 NP类 有些计算问题是确定性的，例如“加减乘除”，你只要按照公式推导，按部就班一步步进行，就可以得到结果。但是，有些问题无法按部就班直接进行计算的。例如“找大质数”问题，已知目前最大质数，那么下一个大质数应该是多少呢？有没有一个公式可以一步步推算出来，显然这样的公式是没有的。这种问题的答案，是无法直接计算得到的，只能通过“猜算”来得到结果，这就是非确定性问题。这些问题通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，称为非确定性算法。假如“猜算”可以在多项式时间内得到，那么该问题称作“多项式非确定性问题”。,9,非确定性算法 对于输入x，一个非确定性算法由猜测和验证二个阶段组成。猜测阶段 在这个阶段产生一个任意字符串y，它可能对应输入实例的一个解，也可以不对应解。事实上，它甚至可能不是所求解的合适形式，它可能在非确定算法的不同次运行中不同。它仅要求在多项式步数内产生这个串，即在O(ni)时间内，这里n=|x|，i是非负整数。对于许多问题，这一阶段可以在线性时间内完成。验证阶段 首先检查产生的解串y是否有合适的形式，如果不是，则算法停下来并回答No；如果y是合适形式，那么算法继续检查它是否是问题实例x的解。若是，则算法停下来并回答Yes；否则算法停下来并回答No。我们也要求这个阶段在多项式步数内完成，即在O(nj)时间内，这里j是一个非负整数。非确定性算法的运行时间是由猜测阶段和验证阶段二部分耗费时间组成，因此它是O(nk)=O(ni)+O(nj)，k是某个非负整数。,10,例：求大整数n的一个真因数(即1和n本身以外的一个因数，并且该因数是素数)。这是一个至今未能找到有效算法的难解问题。对于难解问题，人们除了使用传统型计算方法外，又想出了另一种类型的计算方法，该方法称为“非确定性算法”。传说从前有位年轻的国王，想求出整数190 334 261 410 902 619的一个真因素。他用2、3、5、7、11、13、这些素数逐一去试，化了九牛二虎之力也无法算出，于是他把这个问题交给了宰相。国王用的计算方法称为“穷举法”，是一种传统的计算方法，穷举法属“确定性算法”。,11,宰相猜想这个数可能是9位整数，于是宰相把全国成年百姓编成十个军，每个军有十个师，每个师有十个旅，每个旅有十个团，每个团有十个营，每个营有十个连，每个连有十个排，每个排有十个班，每个班有十个组，每个组有十个人，于是每个成年百姓都具有一个9位的番号。然后把题目发下去，让每个成年百姓用自己的番号去除“190334261410902619”这个数，若除尽了就把番号报上来。很快就有二个人报上了结果，即“436273009”与“436273291”。经国王验证，这二个整数都是素数，并且这二个整数的积就是题目所给的18位整数。,12,190 334 261 410 902 619,436 273 009*436 273 291,军 师 旅,团 营 连,排 组 人,军 师 旅,团 营 连,排 组 人,=,这个故事说明算法分析中最基本问题：求大整数的真因数不能用多项式时间求解，但是验证某数是否是大整数的真因数可以用多项式时间完成。所以，求大整数的真因数要比验证真因数要难得多；国王用得是确定性计算方法(穷举法)，所以计算很快变得无法进行下去；宰相用得是非确定性计算方法，首先猜想，然后验证。,13,NP类定义定义10.3(Page 177)NP类是由这样的判定问题组成：对于它们存在多项式时间内运行的非确定性算法。P类和NP类的区别P类是一个判定问题类，这些问题可以用一个确定性算法，在多项式时间内判定或解出；NP类是一个判定问题类，这些问题可以用一个确定性算法，在多项式时间内检查或验证它们的解。,14,10.4 NP完全问题定义10.4(Page 178)设和是二个判定问题。如果存在一个确定性算法A，它的行为如下：当给A展示问题的一个实例I，算法A可以把它变换为问题的实例I。当且仅当对I回答yes时，对I回答Yes，而且这个变换在多项式时间内完成。那么我们说可以在多项式时间内归约到，用符号poly表示。定理10.3(Page 178)设、和是三个判定问题，有poly和poly，那么poly。推论10.1(Page 179)如果和是NP中的二个问题，若有poly，并且是完全的，则是完全的。,15,如果一个NP问题的所有可能答案，都可以在多项式时间内进行正确与否验证的话，那么该问题称为“完全多项式非确定性问题”，简称NP完全问题或NPC问题。NP完全问题是NP类的一个子类。这是对“NP完全问题”的一个比较通俗的解释，对于初学者来说比较容易理解，上页则给出了“NP完全问题”的严格定义。例10.5 考虑下面二个问题(Page 179)哈密顿回路问题：给出一个无向图G=(V,E)，它有哈密顿回路吗？即在图中存在一条恰好访问每个结点一次的回路。旅行商问题：给出一个n个城市集合，且给出城市间的距离。对于一个整数k，是否存在最长为k的游程？这里，一条游程是一个回路，它恰好访问每个城市一次。众所周知，哈密顿回路问题是NPC问题。根据这一事实我们来证明旅行商问题也是NPC问题。,16,证明：旅行商问题是NP问题 使用非确定性算法，先猜测一个城市序列，然后验证这个序列是一个游程。如果是，只要判断游程的长度是否超过界k即可。证明：哈密顿回路问题在多项式时间内归约到旅行商问题 设G是哈密顿回路的任意实例。我们构建一个含权图G和一个界k，使得当且仅当G有一个总长不超过k的游程时，G有一条哈密顿回路。设G=(V,E)，G=(V,E)是结点V集合上的完全图，即E=(u,v)|u,vV 给E中的每条边的长度定义如下：,其中n=|V|，且指派k=n。从构建中可以看到，当且仅当G有一个长度恰好为n的游程时，G有一条哈密顿回路。由此可得：哈密顿回路问题poly旅行商问题,17,NPC问题可以用穷举法来求解，对于可能解一个个检查下去，最终便能得到结果。但是随着问题规模增大，计算时间成指数型增长，很快变得不可计算了。如果给出一个回路，我们很容易判断它是否是哈密顿回路。只要检查所有的结点是否都在这个回路中，并且只出现一次。检查仅需O(n2)时间。我们一般认为NPC问题是难解问题。因为到目前为止，它们还不存在一个多项式时间的算法，甚至将来也很难找到，即PNP。实际上，对于某些结点数不到100的无向图，使用现有速度最快的计算机也需要比较荒唐的时间，例如耗费几百年才能够确定它是否存在一条哈密顿回路。,18,库克在1971年找到了第一个NP完全问题，即可满足性问题(逻辑运算问题)。此后，人们又陆续发现很多NP完全问题。例如，哈密顿回路问题、旅行商问题、图的3着色问题、多处理机调度问题、。人们发现，所有的NP完全问题都可以在多项式时间内转换到可满足性问题。只要它们中的一个，如果存在“多项式时间确定性算法”的话，那么NPC问题中的所有问题，都可以用“多项式时间确定性算法”来求解。人们于是就猜想，既然NPC问题的所有可能解，都可以在多项式时间内验证，对于此类问题是否存在一个确定性算法，可以在多项式时间内直接给出解呢？这就是著名的NP=P?的猜想。这是21世纪计算机科学家向数学家提出的世界难题。,19,解决NP=P?的猜想无非两种可能。一种是找到一个这样的算法，只要针对某个特定NP完全问题找到一个算法，所有这类问题都可以迎刃而解了，因为它们可以转化为同一个问题。另外的一种可能，就是这样的算法是不存在的。那么，就要从数学理论上证明它为什么不存在。前段时间轰动世界的一个数学成果，是几个印度人提出了一个新算法。该算法可以在多项式时间内，证明某个数是或者不是质数。而在这之前，人们认为质数的证明是个非多项式问题。可见，有些看来好象是非多项式问题，其实是多项式问题，只是人们目前还不知道它的多项式解而已。,20,10.x 近似算法初步 在现实世界中，存在大量NP难解问题。这些问题在理论上是可解的，但求解这些问题的时间需要用指数函数和阶乘函数来描述。非常有趣的是，它们中的许多问题是普通的自然问题，其中还包括了数百个著名问题，例图的3着色问题、哈密顿回路问题、。到目前为止，人们还不知道它们是否存在多项式时间算法。现存的求解这些问题算法的运行时间，对于中等规模大小的输入，也要用几百年或几千年来度量。为了走出这一困境，人们一方面试图摆脱冯诺依曼计算机体系结构，研究新一代计算机体系结构；另一方面，仍在冯诺依曼计算机体系结下来寻求解决这类问题的可行办法。解决这些问题的思路是：与其耗费令人难以接受的大量时间去寻找精确解，倒不如用较少时间去寻找近似解。,21,在求解一个问题时，也许最先出现在你脑海中的策略是贪心方法。例如背包问题，可使用下面贪心策略来近似求解。设yi=vi/si(性价比=价值/容积)，将物品按y值的大小降序排列。从第一项开始装背包，然后第二项，尽可能多装，直至背包不能容纳余下的物品为止。背包问题描述如下：U=u1,u2,u3,u4S=s1,s2,s3,s4=2,3,4,5 V=v1,v2,v3,v4=3,4,5,8 Y=v4/s4,v1/s1,v2/s2,v3/s3=1.60,1.50,1.33,1.25 C=9精确解：在背包中装入物品u3和u4，总价值为最大值13。近似解：重新排列物品，使得U=u4,u1,u2,u3。按上述策略，装入物品u4和u1，总价值为11。,22,背包问题近似算法 输入：背包容量C、物品体积集合S=s1,s2,.,sn、物品价值集合V=v1,v2,.,vn。输出：装入背包中物品集合Z和总价值V，Z的总体积最多为C。1.重新排列物品U，使得y1y2yn(yi=vi/si)。2 j0；K0；V0；Z3.while(jn)and(KC)4.jj+15.if sjC-K then6.ZZuj/Z表示装入背包中物品集合7.KK+sj/K表示装入背包中物品的总体积8.VV+vj/V表示装入背包中物品所具有的价值7.end if8.end while9.output Z10.output V 上述算法主要耗费在性价比Y的排序上，所以背包问题近似解的时间复杂性可用O(nlog2n)来描述。,23,参考文献1沙特M.H.Alsuwaiyel.算法设计技巧与分析.电子工业出版社,2010.2沙特M.H.Alsuwaiyel.算法设计技巧与分析(英文版).电子工业出版社,2003.3温敬和.算法设计与分析.清华大学出版社,2011.,