《算法分析与设计课件：NP问题简介》由会员分享，可在线阅读，更多相关《算法分析与设计课件：NP问题简介（27页珍藏版）》请在金锄头文库上搜索。
1、NP问题简介 lP类问题和NP类问题有一个独立的学科：计算复杂性，专门研究各种问题的计算难度P类问题：多项式（ploynomial）时间NP类问题：非多项式（non ploynomial）时间NP类问题：非确定的多项式时间（nondeterministic ploynomial-time）9/19/20242P类问题：在确定性图灵机（现代计算机模型）上可以多项式时间求解的问题NP类问题：在非确定性图灵机（尚未实现的计算机模型）上可以多项式时间内求解的问题9/19/20243lP类问题是NP类问题的一个子集合尚无法证明： P=NP还是P是NP的真子集？NP完全问题：除非P=NP，否则不可能找到多
2、项式时间的确定性算法的一类问题9/19/20244l尽管理论上没有证明，但大量研究表明，P似乎不等于NP，所以，一旦一个问题被证明是NP完全的，则基本可以断定，它不可能在多项式时间内求解 NPPNP完全9/19/20245l确定型图灵机（确定型图灵机（deterministic deterministic Turing machine)Turing machine)确定型单带图灵机（确定型单带图灵机（Deterministic Turing Deterministic Turing MachineMachine，缩写成缩写成DTMDTM）它由有限状态控制器它由有限状态控制器(FSC)(FSC)
3、，读写头和一读写头和一条带组成，这条带由无穷个方格构成。条带组成，这条带由无穷个方格构成。9/19/20246 有限状态有限状态控制器控制器带带 读写头读写头 确定型单带图灵机确定型单带图灵机 （DTMDTM）的示意图）的示意图9/19/20247一个一个DTMDTM程序详细规定了下述信息：程序详细规定了下述信息：（1 1）有限字符集）有限字符集A, , 一般的一般的A0,1,b,其中其中b为为空白符空白符；（2 2）有穷的状态集合有穷的状态集合Q，包括一个特殊的初始包括一个特殊的初始状态状态q0 和两个特殊的停机状态和两个特殊的停机状态qY和和qN；（3 3）转移函数转移函数:（Q- qY，
4、qN）A QAr ，l , h。9/19/20248:（Q- qY，qN）A QAr ，l , h程程序序从从状状态态Q Q开开始始运运行行，这这时时读读写写头头扫扫描描方方格格，然然后后计计算算一一步步一一步步地地进进行行。如如果果当当前前状状态态q q是是q qY Y或或q qN N，那那末末计计算算结结束束，并并且且当当q=q=q qY Y时时答答案案是是“是是”，当当q=q=q qN N时时答答案案是是“否否”，否否则则当当前前状状态态q q属属于于Q-Q-q qY Y，q qN N，同同时时在在被被扫扫描描的的带带方方格格中中有有一一个个符符号号s s，sA, sA, 假假设设(q,
5、s)= (q,s)= (q(q,s,s,),)，那那末末读读写写头头擦擦去去s,s,并并在在这这个个方方格格里里写写入入s s, ,然然后后移移动动一一格格。当当=l 时时, ,向向左左移移动动一一格格，当当=r=r时时, ,向向右右移移动动一一格格。与与此此同同时时，有有限限状状态态控控制制器器从从状状态态q q变变成成q q。这这就就完完成成了了一一步步计计算算，并为下一步计算做好了准备。并为下一步计算做好了准备。9/19/20249lQ=q0,q1,qY,qN A=0,1,b转移函数q01bq0(q1,0,r)(q0,1,r)(qY,b,h)q1(q0,0,r)(q1,1,r)(qN,b
6、,h)l输入 010100 b01010b 0q09/19/202410lQ=q0,q1, q2,q3, qY,qN A=0,1,Bl输入 00110011q0 B0011B 9/19/202411l一般地，称输入字母表为一般地，称输入字母表为A A的的DTMDTM程序接受程序接受xAxA当且仅当输入当且仅当输入x x时时M M停机在状态停机在状态q qY Y。实际实际上，对于输入上，对于输入xx，M M在在x x上的计算还可能上的计算还可能停机在状态停机在状态q qN N ，也可能不停地进行下去。但也可能不停地进行下去。但是，对于对应于算法概念的是，对于对应于算法概念的DTMDTM程序，它必
7、程序，它必须对输入字母表上所有可能的字符串都停机，须对输入字母表上所有可能的字符串都停机，在这个意义上，上图的在这个意义上，上图的DTMDTM程序是一个算法，程序是一个算法，因为它对因为它对x0x0，11中的任何输入字符串都中的任何输入字符串都停止。停止。9/19/202412对于问题对于问题R R，如果如果DTMDTM程序程序M M在编码方案在编码方案e e下的输入字下的输入字符串停机，那末我们称符串停机，那末我们称M M在编码方案在编码方案e e下解判定问题下解判定问题R R。一个一个DTMDTM程序程序M M对输入对输入x x的计算所用的时间，是到的计算所用的时间，是到进入停机状态时为止
8、在这个计算中出现的步数。对进入停机状态时为止在这个计算中出现的步数。对于对所有输入于对所有输入xAxA都停机的都停机的DTMDTM程序，它的时间复程序，它的时间复杂性函数杂性函数T TM M(n(n）: : T TM M(n(n）=maxm=maxm：对应一个对应一个xAxA，|x|=n,|x|=n,使得使得M M对对输入输入x x的计算需要时间的计算需要时间m m 如果存在多项式如果存在多项式p(n)p(n)使得使得对于所有的对于所有的n,Tn,TM M(n)p(n)(n)p(n)，那末这样的程序那末这样的程序M M叫做叫做多项式时间的多项式时间的DTMDTM程序。程序。9/19/20241
9、3多带的多带的TuringTuring机机 k k条双向带条双向带, k, k个读写头个读写头, , 其中其中k k为大于为大于1 1的常数的常数. . 初始将输入写在第一条带的方格初始将输入写在第一条带的方格1 1到到n n内内. . 其它带为空其它带为空. . 每个读写头扫描一条带每个读写头扫描一条带, ,可以可以改写被扫描方格的字符改写被扫描方格的字符, , 读写头然后向左或向右移读写头然后向左或向右移动一个方格动一个方格. . 读写头的动作由读写头的动作由FSCFSC的状态及的状态及 k k条带条带所扫描的所扫描的k k个字符来决定个字符来决定. .9/19/202414非确定型的非确
10、定型的TuringTuring机机(NDTM)(NDTM) 一个有限状态控制器一个有限状态控制器FSC, FSC, 猜想模块猜想模块GM, GM, 读写读写头头, , 只写头只写头, , 双向无限带双向无限带. . 初始初始FSCFSC处于处于q q0 0状态状态, , 带方格的带方格的1 1到到n n写上输入写上输入x, x, 其它方格为空白字符其它方格为空白字符B. B. 读写头指在方格读写头指在方格1, 1, 只写头只写头指在方格指在方格-1.-1. 计算分为猜想阶段和检查阶段计算分为猜想阶段和检查阶段. . 9/19/202415猜想阶段猜想阶段 FSCFSC处于处于q q0 0状态下
11、的待用状态状态下的待用状态. . 猜想模块猜想模块GMGM指挥只写头指挥只写头, ,每次一步在所扫描的方每次一步在所扫描的方格内写下格内写下A A中的某个字符中的某个字符, , 然后左移一个方格或不动然后左移一个方格或不动. . 到某个时刻到某个时刻, , 猜想模块进入待用状态猜想模块进入待用状态, , 这时有限这时有限状态控制器进入状态控制器进入q q0 0状态下的活跃状态状态下的活跃状态. . 从此刻起从此刻起, , 计计算进入检查阶段，而猜想模块是否继续动作算进入检查阶段，而猜想模块是否继续动作, , 或怎样或怎样动作动作, , 完全是任意的完全是任意的. . 检查阶段检查阶段 与确定型
12、的与确定型的TuringTuring机完全一样机完全一样. . 如果如果FSCFSC进入接受状态进入接受状态, , 则计算停止则计算停止, , 接受接受x. x. 如果进入拒如果进入拒绝状态绝状态, , 则计算停止则计算停止, , 不接受不接受x.x. 9/19/202416计算复杂性理论基础nP P类问题和类问题和NPNP难问题难问题nNP完全问题举例nSAT问题（Boolean Satisfiability Problem）n旅行商问题（Traveling Salesman Problem）n0-1背包问题（ 0-1 Knapsack Problem）n最大团问题（Maximum Cliq
13、ue Problem） n顶点覆盖问题（Vertex Cover Problem）n子集和问题（Sum of Subset Problem） n哈密顿回路问题（Hamiltonian Cycle Problem）9/19/202417计算复杂性理论基础nP类问题和类问题和NP难问题难问题n大规模NP完全问题解决方法n近似算法，随机算法n量子计算机，DNA计算机9/19/202418一、顶点覆盖集设有图一、顶点覆盖集设有图G=,VG=,V是是V V的子集，若的子集，若G G中任意一条边都至少有一个中任意一条边都至少有一个顶点在顶点在V V 中，则称中，则称V V 是是G G的一个顶点覆盖的一个顶
14、点覆盖集即：任给图集即：任给图G=G=及正整数及正整数k|Vk|V|,|,是否存在是否存在k k个顶点的顶点覆盖集。个顶点的顶点覆盖集。12436579/19/202419l二、二、作业安排：设有作业安排：设有q q个完全相同的处理器：个完全相同的处理器：m m1 1,m,m2 2,m,mq q, ,处理处理n n个彼此无关的作业：个彼此无关的作业：j j1 1,j,j2 2,j,jn n, ,所需时间分别为：所需时间分别为： t t1 1,t,t2 2,t,tn n, ,要求最后全部结束的时间最要求最后全部结束的时间最短。短。探索算法探索算法A1:对时间序列进行排序，假定对时间序列进行排序，
15、假定t1 t2 tn 此顺序也就是处理的先后顺序。此顺序也就是处理的先后顺序。即当某个处理器空闲时，立即处理剩下需要处即当某个处理器空闲时，立即处理剩下需要处理的时间最长的作业。理的时间最长的作业。9/19/202420l例：设例：设q=3 ,n=6 ,tq=3 ,n=6 ,t1 1=10 ,t=10 ,t2 2=9 =9 ,t,t3 3=8=8t t4 4=7 ,t=7 ,t5 5=6 ,t=6 ,t6 6=5=5m1m2m31098151515处理顺序：处理顺序：Q=( j1,j2, j3, j4, j5, j6) 9/19/202421l 例：设例：设q=2 ,n=5 ,tq=2 ,n=
16、5 ,t1 1=3 ,t=3 ,t2 2=3 ,t=3 ,t3 3=2=2t t4 4=2 ,t=2 ,t5 5=2 =2 m1m253753m1m262643即即T1=7 ,处理顺序：处理顺序：Q1= ( j1,j2, j3, j4 , j5 )T2=6 ,处理顺序：处理顺序：Q2= ( j1,j3, j4, j2 , j5 )用探索法不一定能得到最优解。用探索法不一定能得到最优解。9/19/202422用探索法与最优方案相比，完成作业的最后时用探索法与最优方案相比，完成作业的最后时间推迟了一个单位时间，如果认为探索法的绝间推迟了一个单位时间，如果认为探索法的绝对偏差对偏差=1，则相对偏差则
17、相对偏差=1/6用用Tn表示利用递减次序的探索法完成全部作表示利用递减次序的探索法完成全部作业所需的时间，用业所需的时间，用T*n表示利用最优方案完成表示利用最优方案完成全部作业所需的时间，则绝对偏差全部作业所需的时间，则绝对偏差 = Tn-T*n，相对偏差相对偏差 = (Tn-T*n)/ T*n= / T*n可以证明作业安排问题的探索法的相对可以证明作业安排问题的探索法的相对偏差偏差满足满足 1/3-1/3q9/19/202423l本算法首先对本算法首先对t1 ,t2, tn 进行排序，其时间进行排序，其时间复杂性为复杂性为O(nlogn),然后在调度过程中，每调入然后在调度过程中，每调入一
18、个作业，只需比较有限次，故工作量为一个作业，只需比较有限次，故工作量为O(n)，所以本算法总的时间复杂性为所以本算法总的时间复杂性为O(nlogn) 改进算法改进算法A2:假定已经排序的假定已经排序的t1 t2 tn ,确定整数确定整数k,先对前先对前k个作业求最优安排，然后对后个作业求最优安排，然后对后n-k个个作业应用算法作业应用算法A19/19/202424l 二、装箱问题二、装箱问题有容积均为有容积均为T的相同箱子的相同箱子Bj个个,另有体积为另有体积为ti的的n个物品个物品,i=1,2,n。要求把所有要求把所有的物品放进数目尽可能少的箱子中去。装箱的物品放进数目尽可能少的箱子中去。装
19、箱时，每个时，每个物品不能分割，每个箱子所装物品的体积物品不能分割，每个箱子所装物品的体积之和不能超过之和不能超过T。L是某个给定的物品序列。是某个给定的物品序列。1)首次适宜的算法首次适宜的算法firstfit (FF算法算法)物品的顺序任意，每个物品依次放在它第物品的顺序任意，每个物品依次放在它第一次放得进去的箱子中。一次放得进去的箱子中。9/19/2024252)首次适宜降序算法首次适宜降序算法firstfitdesc (FFD算法算法)将将FF算法中物品顺序按尺寸递减排序算法中物品顺序按尺寸递减排序3)最适宜算法最适宜算法bsetfit(BF算法算法)物品的顺序任意，下一个物品要放入到能造物品的顺序任意，下一个物品要放入到能造成最小剩余空间的那个箱子中去。成最小剩余空间的那个箱子中去。4)最适宜降序算法最适宜降序算法bsetfitdesc(BFD算法算法)将将BFD算法中物品顺序按尺寸递减排序算法中物品顺序按尺寸递减排序9/19/202426例：例：L=(7,9,7,1,6,2,4,3) 箱子尺寸为箱子尺寸为1379712346练习：画出练习：画出BF,FFD,BFD的图示，的图示，并写出近似最优解成立的条件并写出近似最优解成立的条件9/19/202427
