完全问题一些典型的例子课件.pptx

NP-完全问题(NP Complete Problem)Thinking about Algorithms Abstractlyxxx天津大学计算机科学与技术学院1感谢你的观看2019年5月19日主要内容nNP-完全问题：一些典型的例子nNP-完全问题：相关定义n近似算法n两种新的计算模型2感谢你的观看2019年5月19日NP-Complete: 涵义nN-NondeterministicqDeterministic algorithm: Given a particular input, it will always produce the same correct outputqNon-deterministic algorithm: with one or more choice points where multiple different continuations are possible, without any specification of which one will be takennP-Polynomial (time)qComputableqPolynomial time is assumed the lowest complexity nCompleteqReducible输入/输出算法复杂性变换/封闭性3感谢你的观看2019年5月19日NP-C:典型的问题（1）n问题1 图着色问题q判定问题：是否存在不超过k种颜色的着色方案?q优化问题：求图的最小着色数和着色方案n问题2 作业调度问题q判定问题：是否存在罚款额不超过k的作业调度?q优化问题：求最小罚款额调度4感谢你的观看2019年5月19日NP-C:典型的问题（2）n问题3 Bin packing问题：假设有n种物品，它们的尺寸分别为s1,sn，01使得n= jk?即n 是否为一合数? factor=0; for (j=2;jCq对应调度问题实例 pi=ti=si ,di=C, k=S-Cnif部分:子集和数有解则调度问题有解nonly if:假定上述调度问题有罚款额k的解q该可行调度的执行时间ti之和C(可行性)q又因ti=pi=si,所以该可行调度对应罚款额=S-pi =S-tiS-C=kq所以其罚款额k，而且被调度的作业的时间之和C21感谢你的观看2019年5月19日NP-难度和NP-完全问题n问题Q是NP-难度问题，如果：每个NP问题都可多项式地约化为问题 Q.n问题 Q 是 NP-完全问题. 如果:q它是NP问题, 同时它还是NP-难度问题.nNP-完全问题的性质q所有NP-完全问题,相对于多项式约化关系,是自反,对称,传递的,即构成一个闭类. q如果能找到一个NP完全问题的多项式算法则P=NPq有NP-难度问题但不知它是否在NP类内(第kth重子集问题)22感谢你的观看2019年5月19日Problems-unknown in NPnKth重子集问题:任给定n+2 个正整数 c1,cn, k, L; 是否存在1,2,n 的k 个不同子集S1,Sk 使得对所有i=1,k 有n部分称为子集的重量, 重量排序第k的子集. n当k=2n-1时,表示可行解的字符串的长度有指数的长度.我们不知道该问题是否在NP中.n图G的最大集团的节点数是否=k? 上述问题是否在NP?也是未知的! (验证最大集团,不能在多项式时间内做到)23感谢你的观看2019年5月19日CNF-satisfiablity问题是NP-完全问题n定理13.5 CNF-satisfiablity问题是NP-完全问题n这是著名的Cook定理nCook 定理的推论:如果CNF-可满足问题有多项式界的算法，则P=NP.24感谢你的观看2019年5月19日NP-完全问题证明n证明问题Q是NP-完全问题的步骤： (1)选择一已知的NP-完全问题P。

2)证明P可多项式的约化为 Qn背包问题属于NP子集和数属于NPn子集和数问题属于NP调度问题属于NPn不计其数的这种推导.25感谢你的观看2019年5月19日Lists of NP-Complete problems nBoolean satisfiability problem (SAT) nN-puzzle nKnapsack problem nHamiltonian path problem nTraveling salesman problem nSubgraph isomorphism problem nSubset sum problem nClique problem nVertex cover problem nIndependent set problem nGraph coloring problem 26感谢你的观看2019年5月19日What makes a problem hard(1)n限定问题的一般性（问题的附加限制）q实际应用中有特殊性, 有可能找到多项式算法n例：Hamiltonian回路顶点度=2时，Hamiltonian回路问题有多项式算法q工程中有灵活性,以某种方式优化是NP-难度问题;但以另一方式提出问题可能不是(优化标准)n了解“难问题”的特点27感谢你的观看2019年5月19日What makes a problem hard(2)n3-满足问题仍为NP-完全问题,但2-满足问题有多项式算法n集团问题,当顶点度=常数d时属于类Pn平面图集团问题属于类P，因为平面图至多有4-集团n实际有意义的做法是提出合理的限制条件和求近似解, 研究启发式算法.28感谢你的观看2019年5月19日优化问题和判定问题n3种问题q判定问题q求优化值问题q求优化解问题n优化问题至少与判定问题一样“难”q优化值问题有多项式算法，则判定问题有多项式算法q多数情况下，如果能在多项式时间内求解决策问题，那么也能在多项式时间内获得最优值（图着色问题）；有时则不能（TSP）29感谢你的观看2019年5月19日近似算法（1）n返回次优解的算法。

这种算法经常可以通过启发式方法得到，例如：贪心法n近似算法必须是多项式时间算法n为量度近似解对优化解的近似程度定义以下术语qFS(I) 是输入I的可行解集qVal(I,x):实例I的可行解x的目标函数值qopt(I):实例I的优化解的值30感谢你的观看2019年5月19日近似算法（2）n设A为一近似算法,令A(I)为输入I时该算法输出的可行解n极小化和极大化问题度量近似性能的指标rA(I)31感谢你的观看2019年5月19日续式(13.5)定义的RA(m)为最坏情形rA(I)的值,是与输入I无关的指标: 在固定优化值m下求最坏情形的比值式(13.6)定义的SA(n)也是一与输入独立的指标32感谢你的观看2019年5月19日Bin-Packing的近似算法n怎么装不同大小、不同形状的货物才能使占用的箱子数最少该问题形式化如下：n装箱问题q设S = (s1, , sn)n 0 si = 1 ， 1 = i = nq将 s1, , sn 装入尽可能少的箱子里假定每个箱子都有容量1n装箱问题是NP-难度问题q搜索算法有指数的复杂度：须试所有可能的S的分划33感谢你的观看2019年5月19日装箱问题：FFD算法（贪心法）n将物品按尺寸递减排序，箱子从左到右排列并尽可能放在前面的箱子里。

n算法的时间复杂度t(n)=(n2)34感谢你的观看2019年5月19日算法：装箱问题n输入: S=(s1,.,sn) ，0=S2=Sn. for(i=1;i=n;i+) /寻找能装下 si 的箱子. for(j=1;j=n;j+) if(usedj+si+1.0) /+1.0， 每个箱子的容量都是1.0 bini=j; usedj += si; break; /装完退出循环j,装下一个箱子，继续循环i. 36感谢你的观看2019年5月19日近似分析n引理13.9 :设S为算法的输入.令opt(S)为优化的装箱数.令i为第一个被FFD算法装入第opt(S)+1号箱子的物品,则si1/3, 则FFD算法在装到si 时, 前面的箱子的不会如图13.7的情形. 产生的装箱情况如图13.8.(k0): k个箱子只放一个物品; opt-k个箱子放2个size1/3的物品. 37感谢你的观看2019年5月19日近似分析nFFD算法没把物品k+1,i -1放在前k个箱子内(放不下), 这些物品的数目为2(opt-k)n尽管优化解的装箱情况和FFD不同, 但前k个物品在优化解中也必须分放在k个箱子里: 前k个物品中任2个都不能放在一个箱子内.n优化解中物品k+1,i-1,放在其余的opt-k个箱子内. 因为这些物品的尺寸均1/3. 所以这些箱子中每个箱子都要放2个, 尽管放法和FFD不一定相同.n因此 si 在优化解中无法安排,矛盾.38感谢你的观看2019年5月19日近似分析n引理13.10 :FFD在前opt(S)箱子装不下的物品数量至多为opt(S)-1 反证法:如有opt(S)个物品放在多用的箱内,则有: 但 其中bi为装在第i个箱子内物品的总量;ti为前opt箱子装不下的物品的重量;按FFD算法后者不能装入第i个箱子.所有bi+ti1.n定理13.11 RFFD(m)=(4/3)+(1/3m); SFFD(n)=3/239感谢你的观看2019年5月19日近似分析nFFD至多有m-1个物品放在extra箱子内,放的物品size1. 41感谢你的观看2019年5月19日背包和子集和数问题n当所有pi=si时，背包问题转化为子集和 数的优化问题n算法13.2为上述简化的背包问题的近似算法sKnapk，类似k优化的背包问题的贪心算法。

n定理13.13 RsKnapk (m)和SsKnapk(n)均=k个最重的重量之和+Sj=(k+1)Sj ,所以Sj C=m ,所以 Val(sKnapk(I)m-Sj=m-(m/(k+1) =mk/(k+1) nr(I)=m/Val(k+1)/k=1+1/k 43感谢你的观看2019年5月19日图着色n算法13.3 for (i=1;in;i+) for (c=1;cn;c+) 如没有与vi 相邻的顶点有着色c ,对 vi 着色c 并break;nFig.13.11 如按先a类顶点后b类顶点着色算法13.3只需2种颜色;如交叉进行则需k种颜色nRSC(2)=;SSC(n)n/4 (k=n/2,opt=2)44感谢你的观看2019年5月19日旅行商问题q给定一个带权重的完全图q找具有最小权重的周游路线（通过所有顶点的环）45感谢你的观看2019年5月19日旅行商问题的近似算法n最近邻居策略NearestTSP(V, E, W) 选择任一顶点s作为周游路线C的起点 v = s; While 有顶点不再C中: 选择有最小权重的边vw，其中 w 不在C中. 将边vw加入C中; v = w; 将边vs加入C. return C;n时间复杂度t(n) = O(n2)nn 是顶点的数量46感谢你的观看2019年5月19日续n最短链路策略:与C中边不构成环路且不构成与v或w伴随的第3条边(无向图)最小权值边(v,w)n上述两个算法都不保证产生优化解，而且对其近似程度也不能给出界n定理13.22 设A是TSP问题的近似算法，如对任何输入I有rA(I)=c，则PNPn从该定理可看出TSP的难度47感谢你的观看2019年5月19日DNA ComputernOrigin from similarity with Turing-computingqCodes: (0,1)(A,T,G,C)qOperator: (and,or, not)(copy, cut, paste)qInitiated by Leonard Adleman for solving Hamiltonian path problem in 1994.qIncreasing performance (faster, tiny), 。