第九讲-NP完全问题-算法设计与分析课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《第九讲-NP完全问题-算法设计与分析课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第九 NP 完全 问题 算法 设计 分析 课件
- 资源描述:
-
1、Algorithms Design Techniques and Analysis第 10章NP完全问题Computability TheoryAlgorithms Design Techniques and Analysis本章内容本章内容Introduction of a class of problems for which no efficient algorithms have been found P类NP类NP完全问题co-NP类NPI类Algorithms Design Techniques and Analysis10.1 引言 设是任意问题,如果对问题存在一个算法,它的时间
2、复杂性是O(nk),其中是输入大小,k是非负整数,我们说存在着求解问题n的多项式时间算法。这类算法在可以接受的时间内实现问题求解,e.g.,排序、串匹配、矩阵相乘。但是,现实世界中的许多有趣问题并不属于这个范畴,因为求解这些问题所需要的时间量要用指数和超指数函数(如2n和n!)来测度。随着问题规模的增长而快速增长。在计算机科学界已达成这样的共识,认为存在多项式时间算法的问题是易求解的,而对于那些不大可能存在多项式时间算法的问题是难解的。易解问题与难解问题的主要区别 在学术界已达成这样的共识:把多项式时间复杂性作为易解问题与难解问题的分界线,主要原因有:1)多项式函数与指数函数的增长率有本质差别
3、问题规模问题规模n多项式函数多项式函数指数函数指数函数lognnnlognn2n32nn!1010.01121103.31033.2100100010243628800204.32086.4400800010483762.4E18505.650282.225001250001.0E153.0E641006.6100664.41000010000001.3E309.3E157Algorithms Design Techniques and Analysis2)计算机性能的提高对易解问题与难解问题算法的影响 假设求解同一个问题有5个算法A1A5,时间复杂度T(n)如下表,假定计算机C2的速度是计算
4、机C1的10倍。下表给出了在相同时间内不同算法能处理的问题规模情况:T(n)nn变化变化n/n10n100010000n=10n1020n5005000n=10n105nlogn2501842nn10n7.372n270223n3.162n1316n=n+log10n+311010Algorithms Design Techniques and Analysis3)多项式时间复杂性忽略了系数,不影响易解问题与难解问题的划分问题规模问题规模n多项式函数多项式函数指数函数指数函数n8108nn10001.1n20.01n53906255108510001.6111.0351010810910100
5、02.5941.0721001016101010200013780.621000102410111030002.4710411024观察结论:观察结论:n100时,(不自然的)多项式函数值大于指数时,(不自然的)多项式函数值大于指数函数值,但函数值,但n充分大时,指数函数仍然超过多项式函数充分大时,指数函数仍然超过多项式函数。Algorithms Design Techniques and AnalysisAlgorithms Design Techniques and Analysis难解问题 这一类含有许许多多问题,其中还包含了数百个著名的问题,它们有一个共同的特性,即如果它们中的一个是多
6、项式可解的,那么所有其他的问题也是多项式可解的。此外,现存的求解这些问题的算法的运行时间,对于中等大小的输入也要用几百或几千年来测度。Algorithms Design Techniques and Analysis判定问题和最优化问题判定问题:在研究NP完全性理论时,我们很容易重述一个问题使它的解只有两个结论:yes或no,在这种情况下,称问题为判定问题。最优化问题:与此相对照,最优化问题是关心某个量的最大化或最小化的问题。在前面的章节中,已经遇到过大量的最优化问题,像找出一张表中的最大或最小元素的问题,在有向图中寻找最短路径间题和计算一个无向图的最小生成树的问题。如果我们有一个求解判定问题
7、的有效算法,那么很容易把它变成求解与它相对应的最优化问题的算法。反之亦然。Algorithms Design Techniques and Analysis例子 10.1设S是一个实数序列,ELEMENT UNIQUENESS问题为,是否S中的所有的数都是不同的。判定问题:ELEMENT UNIQUENESS.输入:一个整数序列S问题:在S中存在两个相等的元素吗?最优问题:ELEMENT COUNT输入:一个整数序列S输出:一个在S中频度最高的元素。这个问题可以用显而易见的方法在最优的时间O(nlogn)解决,这意味着它是易解的。Algorithms Design Techniques and
8、 Analysis例子 10.2给出一个无向图G=(V,E),用k种颜色对G着色是这样的问题:对于V中的每一个顶点用k种颜色中的一种对它着色,使图中没有两个邻接顶点有相同的颜色。这个问题是难解的.例子 10.2 COLORING问题(图着色问题)输入:(着色数)k,(节点数)5,(图的边)(1,2)(1,4).写出长度为n(节点数)的字符串,例如,RGRBG,RGRB,RBYGO,RGRBY,R%*$等,至少有kn个不同着色情况。找到符合要求(任何两个邻接顶点颜色不同)的最小的k值31245Algorithms Design Techniques and Analysis例子 10.2(Con
9、tinue)判定问题:COLORING 输入:一个无向图G=(V,E)和一个正整数k 1。问题:G可以k着色吗?即G最少可以用k种颜色着色吗?这个问题的一个最优形式是,对一个图着色,使图中没有两个邻接的顶点有相同的颜色,所需要的最少颜色数是多少?这个数记为(G),称为G的色数。最优化问题:CHROMATIC NUMBER输入:一个无向图G=(V,E)。输出:G的色数。四色猜想 地图四色定理(Four color theorem)最先是由一位叫古德里(Francis Guthrie)的英国大学生提出来的。四色问题的内容是:“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”Alg
10、orithms Design Techniques and Analysis四色猜想1852年,刚从伦敦大学毕业的Francis Guthrie提出了四色猜想。1878年著名的英国数学家Cayley向数学界征求解答。此后数学家 Heawood 花费了毕生的精力致力于四色研究,于1890年证明了五色定理(每个平面图都是5顶点可着色的)。直到1976年6月,美国数学家 K.Appel与 W.Haken,在3台不同的电子计算机上,用了1200小时,作了100亿判断,才终于完成了“四色猜想”的计算机证明。Algorithms Design Techniques and AnalysisAlgorith
11、ms Design Techniques and Analysis例子 10.3给出一个无向图G=(V,E),对于某个正整数k,G中大小为k的团集,是指G中有k个顶点的一个完全子图。团集问题是问一个无向图是否包含一个预定大小的团集。判定问题:CLIQUE.输入:一个无向图G=(V,E)和一个正整数k。问题:G有大小为k的团集吗?最优化问题:MAX-CLIQUE.输入:一个无向图G=(V,E).输出:一个正整数k,它是G中最大团集的大小Algorithms Design Techniques and Analysis 如果我们有一个求解判定问题的有效算法,那么很容易把它变成求解与它相对应的最优化
12、问题的算法。例如,我们有一个求解图着色判定问题的算法A,则可以用二分搜索并且把算法A作为子程序来找出图G的色数。很清楚,1=x(G)=n,这里n是G中顶点数,因此仅用O(1og n)次调用算法A就可以找到G的色数。由于我们正处理多项式时间的算法,log n因子是不重要的。因为这个理由,在NP完全问题的研究中,甚至在一般意义上的计算复杂性或可计算性的研究中,把注意力限制在判定问题上会比较容易一些10.2 P类 因此,易解问题和难解问题的划分标准可基于对所谓判定问题的求解方式。事实上,实际应用中的大部分问题问题可以很容易转化为相应的判定问题,如:排序问题 给定一个实数数组,是否可以按非降序排列?图
13、着色问题:给定无向连通图G=(V,E),求最小色数k,使得任意相邻顶点具有不同的着色 给定无向连通图G=(V,E)和正整数k,是否可以用k种颜色.?Algorithms Design Techniques and AnalysisAlgorithms Design Techniques and Analysis10.2 P类 定义 10.1 设A是求解问题的一个算法,如果在展示问题的一个实例时,在整个执行过程中,每一步都只有一种选择,则称A是确定性算法。因此如果对于同样的输入,实例一遍又一遍地执行,它的输出从不改变。特点:对同一输入实例,运行算法A,所得结果是一样的。Algorithms De
14、sign Techniques and Analysis10.2 P类 定义 10.2 判定问题的P类由这样的判定问题组成,它们的yes/no解可以用确定性算法在运行多项式步数内,例如在O(nk)步内得到,其中k是某个非负整数,n是输入大小。也就是说:如果对于某个判定问题,存在一个非负整数k,对于输入规模为n的实例,能够以O(nk)的时间运行一个确定性算法,得到yes或no的答案,则称该判定问题是一个P(Polynomial)类问题。事实上,所有易解问题都是事实上,所有易解问题都是P类问题。类问题。Algorithms Design Techniques and AnalysisP类的问题排序
15、问题:给出一个n个整数的表,它们是否按非降序排列?不相交集问题:给出两个整数集合,它们的交集是否为空?最短路径问题:给出一个边上有正权的有向图G=(V,E),两个特异的顶点s,t V和一个正整数k,在s到t间是否存在一条路径,它的长度最多是k。Algorithms Design Techniques and AnalysisP类的问题2着色问题:给出一个无向图G,它是否是2可着色的?即它的顶点是否可仅用两种颜色着色,使两个邻接顶点不会分配相同的颜色?注意,当且仅当G是二分图,即当且仅当它不包含奇数长的回路时,它是2可着色的。2可满足问题:给出一个合取范式(CNF)形式的布尔表达式f,这里每个子
16、句恰好由两个文字组成,问f是可满足的吗?Algorithms Design Techniques and Analysis 如果对于任意问题C,的补也在C中,我们说问题类 C在补运算下是封闭的。例如,2着色问题的补可以陈述如下:给出一个图G,它是不2可着色的吗?我们称这个问题为NOT-2-COLOR问题。它是属于P的。定理 10.1 P类问题在补运算下是封闭的。Algorithms Design Techniques and Analysis10.3 NP类 NP类由这样的问题组成,对于这些问题存在一个确定性算法A,该算法在对的一个实例展示一个断言解时,它能在多项式时间内验证解的正确性。即如果
17、断言解导致答案是yes,就存在一种方法可以在多项式时间内验证这个解。Algorithms Design Techniques and Analysis不确定性算法 对于输入x,一个不确定性算法由下列两个阶段组成:猜测阶段 验证阶段 p177Algorithms Design Techniques and Analysis猜测阶段在这个阶段产生一个任意字符串y,它可能对应于输入实例的一个解,也可以不对应解。事实上,它甚至可能不是所求解的合适形式,它可能在不确定性算法的不同次运行中不同。它仅仅要求在多项式步数内产生这个串,即在O(ni)时间内,这里n=|x|,i是非负整数。对于许多问题,这一阶段可
18、以在线性时间内完成。Algorithms Design Techniques and Analysis验证阶段在这个阶段,一个不确定性算法验证两件事首先,它检查产生的解串y是否有合适的形式,如果不是,则算法停下并回答no;另一方面,如果y是合适形式,那么算法继续检查它是否是问题实例x的解,如果它确实是实例x的解,那么它停下并且回答yes,否则它停下并回答no。我们也要求这个阶段在多项式步数内完成,即在O(nj)时间内,这里j是一个非负整数。Algorithms Design Techniques and Analysis 设A是问题的一个不确定性算法,我们说A接受问题的实例I,当且仅当对于输入
19、I存在一个导致yes回答的猜测。换句话说,A接受I当且仅当可能在算法的某次执行上它的验证阶段将回答yes。要强调的是,如果算法回答no,那么这并不意味着A不接受它的输人,因为算法可能猜测了一个不正确解。定义(不确定性算法):设A是求解问题的一个算法,如果算法A以如下猜测+验证的方式工作,称算法A为不确定性(nondeterminism)算法:猜测阶段:对问题的输入实例产生一个任意字串y,在算法的每次运行,y可能不同,因此猜测是以不确定的形式工作。这个工作一般可以在线性时间内完成。验证阶段:在这个阶段,用一个确定性算法验证两件事:首先验证猜测的y是否是合适的形式,若不是,则算法停下并回答no;若
20、是合适形式,则继续检查它是否是问题x的解,如果确实是x的解,则停下并回答yes,否则停下并回答no。要求验证阶段在多项式时间内完成。不确定性算法与不确定性算法与NP类问题类问题Algorithms Design Techniques and Analysis注意对不确定性算法输出yes/no的理解:若输出no,并不意味着不存在一个满足要求的解,因为猜测可能不正确;若输出yes,则意味着对于该判定问题的某一输入实例,至少存在一个满足要求的解。Algorithms Design Techniques and Analysis不确定的算法:伪代码 Void nondetA(String input)
21、String s=genCertif();boolean checkOK=verifyA(input,s)if(checkOK)Output“yes“return checOK为为false时不作反应时不作反应.Algorithms Design Techniques and AnalysisNP类 至于一个(不确定性)算法的运行时间,它仅仅是两个运行时间的和:一个是猜测阶段的时间,另一个是验证阶段的时间。因此它是O(ni)+O(nj)=O(nk),k是某个非负整数。定义 10.3 判定问题类NP由这样的判定问题组成:对于它们存在着多项式时间内运行的不确定性算法。南京理工大学NP类问题类问题
22、定义(NP类问题):如果对于判定问题,存在一个非负整数k,对于输入规模为n的实例,能够以O(nk)的时间运行一个不确定性算法,得到yes/no的答案,则该判断问题是一个NP(nondeterministic polynomial)类问题。注意:NP类问题是对于判定问题定义的,事实上,可以在多项式时间内应用非确定性算法解决的所有问题都属于NP类问题。例子(图着色问题)Input:(着色数)k,(节点数)5,(图的边)(1,2)(1,4).Guessing 指写出长度为n(节点数)的字符串,例如,RGRBG,RGRB,RBYGO,RGRBY,R%*$等.至少有kn个“guessings”。Chec
23、king 指检查一guessed字符串是否合法及是否是一个k-着色。如果写字符串的时间是O(p1(n),checking时间是O(p2(n);而且p1(n),p2(n)是n的多项式(从而也是输入长度的多项式),则该不确定算法有多项式时间。如果输入的图能k着色则不确定算法停机并给出yes回答。31245Algorithms Design Techniques and Analysis例子考虑问题COLORING,我们用两种方法证明这个问题属于NP类。方法1:设I是COLORING问题的一个实例,s被宣称为I的解。容易建立一个确定性算法来验证,是否确实是I的解。从NP类的非形式定义可得COLORI
24、NG问题属于NP类。Algorithms Design Techniques and Analysis方法 2建立不确定性算法 当图G用编码表示后,一个算法A可以很容易地构建并运作如下 首先通过片顶点集合产生一个任意的颜色指派以“猜测”一个解First。接着,A验证这个指派是否是有效的指派,如果它是一个有效的指派,那么A停下并且回答yes,否则它停下并回答no。请注意,根据不确定性算法的定义,仅当对问题的实例回答是yes时,A回答yes。其次是关于需要的运行时间,A在猜测和验证两个阶段总共花费不多于多项式时间。关于关于P与与NP关系的初步思考关系的初步思考 -从字面含义从字面含义1)若问题属于
25、P类,则存在一个多项式时间的确定性算法,对它进行判定或求解;显然,也可以构造一个多项式时间的非确定性算法,来验证解的正确性,因此,问题也属NP类。因此,显然有 PNP2)若问题属于NP类,则存在一个多项式时间的非确定性算法,来猜测并验证它的解;但不一定能构造一个多项式时间的确定性算法,来对它进行求解或判定。因此,人们猜测P NP,但是否成立,至今未得到证明。P=NP?是计算机科学中最大的问题之一Algorithms Design Techniques and AnalysisAlgorithms Design Techniques and Analysis10.4 NP完全问题 术语“NP完全
展开阅读全文