1、NP-完全问题(NP Complete Problem)Thinking about Algorithms Abstractlyxxx天津大学计算机科学与技术学院1谢谢你的阅读2019年10月19主要内容nNP-完全问题：一些典型的例子nNP-完全问题：相关定义n近似算法n两种新的计算模型2谢谢你的阅读2019年10月19NP-Complete:涵义nN-NondeterministicqDeterministic algorithm:Given a particular input,it will always produce the same correct outputqNon-dete
2、rministic 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年10月19NP-C:典型的问题（1）
3、n问题1 图着色问题q判定问题：是否存在不超过k种颜色的着色方案?q优化问题：求图的最小着色数和着色方案n问题2 作业调度问题q判定问题：是否存在罚款额不超过k的作业调度?q优化问题：求最小罚款额调度4谢谢你的阅读2019年10月19NP-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(可行
4、性)q又因ti=pi=si,所以该可行调度对应罚款额=S-pi=S-tiS-C=kq所以其罚款额k，而且被调度的作业的时间之和C21谢谢你的阅读2019年10月19NP-难度和NP-完全问题n问题Q是NP-难度问题，如果：每个NP问题都可多项式地约化为问题 Q.n问题 Q 是 NP-完全问题.如果:q它是NP问题,同时它还是NP-难度问题.nNP-完全问题的性质q所有NP-完全问题,相对于多项式约化关系,是自反,对称,传递的,即构成一个闭类.q如果能找到一个NP完全问题的多项式算法则P=NPq有NP-难度问题但不知它是否在NP类内(第kth重子集问题)22谢谢你的阅读2019年10月19Pro
5、blems-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?也是未知的!(验证最大集团,不能在多项式时间内做到)LciSjj23谢谢你的阅读2019年10月19CNF-satisfiablity问题是NP-完全问题n定理13.5 CNF-satisfiablity问题是NP-完全问题n这是著名的Coo
6、k定理nCook 定理的推论:如果CNF-可满足问题有多项式界的算法，则P=NP.24谢谢你的阅读2019年10月19NP-完全问题证明n证明问题Q是NP-完全问题的步骤：(1)选择一已知的NP-完全问题P。(2)证明P可多项式的约化为 Qn背包问题属于NP子集和数属于NPn子集和数问题属于NP调度问题属于NPn不计其数的这种推导.25谢谢你的阅读2019年10月19Lists of NP-Complete problems nBoolean satisfiability problem(SAT)nN-puzzle nKnapsack problem nHamiltonian path pro
7、blem nTraveling salesman problem nSubgraph isomorphism problem nSubset sum problem nClique problem nVertex cover problem nIndependent set problem nGraph coloring problem 26谢谢你的阅读2019年10月19What makes a problem hard(1)n限定问题的一般性（问题的附加限制）q实际应用中有特殊性,有可能找到多项式算法n例：Hamiltonian回路顶点度=2时，Hamiltonian回路问题有多项式算法q
8、工程中有灵活性,以某种方式优化是NP-难度问题;但以另一方式提出问题可能不是(优化标准)n了解“难问题”的特点27谢谢你的阅读2019年10月19What makes a problem hard(2)n3-满足问题仍为NP-完全问题,但2-满足问题有多项式算法n集团问题,当顶点度=常数d时属于类Pn平面图集团问题属于类P，因为平面图至多有4-集团n实际有意义的做法是提出合理的限制条件和求近似解,研究启发式算法.28谢谢你的阅读2019年10月19优化问题和判定问题n3种问题q判定问题q求优化值问题q求优化解问题n优化问题至少与判定问题一样“难”q优化值问题有多项式算法，则判定问题有多项式算法
9、q多数情况下，如果能在多项式时间内求解决策问题，那么也能在多项式时间内获得最优值（图着色问题）；有时则不能（TSP）29谢谢你的阅读2019年10月19近似算法（1）n返回次优解的算法。这种算法经常可以通过启发式方法得到，例如：贪心法。n近似算法必须是多项式时间算法。n为量度近似解对优化解的近似程度定义以下术语qFS(I)是输入I的可行解集。qVal(I,x):实例I的可行解x的目标函数值qopt(I):实例I的优化解的值30谢谢你的阅读2019年10月19近似算法（2）n设A为一近似算法,令A(I)为输入I时该算法输出的可行解n极小化和极大化问题度量近似性能的指标rA(I)极小化3.131)
10、()(,()(IoptIAIvalIrA极大化4.131)(,()()(IAIvalIoptIrA31谢谢你的阅读2019年10月19续)5.13()(|)(max)(mIoptIrmRAA)6.13()(|)(max)(nIsizeIrnSAA式(13.5)定义的RA(m)为最坏情形rA(I)的值,是与输入I无关的指标:在固定优化值m下求最坏情形的比值式(13.6)定义的SA(n)也是一与输入独立的指标32谢谢你的阅读2019年10月19Bin-Packing的近似算法n怎么装不同大小、不同形状的货物才能使占用的箱子数最少。该问题形式化如下：n装箱问题q设S=(s1,sn)n 0 si=1，
11、1=i=nq将 s1,sn 装入尽可能少的箱子里。假定每个箱子都有容量1。n装箱问题是NP-难度问题q搜索算法有指数的复杂度：须试所有可能的S的分划。33谢谢你的阅读2019年10月19装箱问题：FFD算法（贪心法）n将物品按尺寸递减排序，箱子从左到右排列并尽可能放在前面的箱子里。n算法的时间复杂度t(n)=(n2)34谢谢你的阅读2019年10月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+
12、=si;break;/装完退出循环j,装下一个箱子，继续循环i.36谢谢你的阅读2019年10月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年10月19近似分析nFFD算法没把物品k+1,i-1放在前k个箱子内(放不下),这些物品的数目为2(opt-k)n尽管优化解的装箱情况和FFD不同,但前k个物品
13、在优化解中也必须分放在k个箱子里:前k个物品中任2个都不能放在一个箱子内.n优化解中物品k+1,i-1,放在其余的opt-k个箱子内.因为这些物品的尺寸均1/3.所以这些箱子中每个箱子都要放2个,尽管放法和FFD不一定相同.n因此 si 在优化解中无法安排,矛盾.38谢谢你的阅读2019年10月19近似分析n引理13.10:FFD在前opt(S)箱子装不下的物品数量至多为opt(S)-1 反证法:如有opt(S)个物品放在多用的箱内,则有:但 其中bi为装在第i个箱子内物品的总量;ti为前opt箱子装不下的物品的重量;按FFD算法后者不能装入第i个箱子.所有bi+ti1.n定理13.11 RF
14、FD(m)=(4/3)+(1/3m);SFFD(n)=3/2)()()(1)(1)(11SopttbtbsiSoptiiSoptiisoptiinii)(1Soptsnii39谢谢你的阅读2019年10月19近似分析nFFD至多有m-1个物品放在extra箱子内,放的物品size1.41谢谢你的阅读2019年10月19背包和子集和数问题n当所有pi=si时，背包问题转化为子集和 数的优化问题n算法13.2为上述简化的背包问题的近似算法sKnapk，类似k优化的背包问题的贪心算法。n定理13.13 RsKnapk(m)和SsKnapk(n)均=k个最重的重量之和+Sj=(k+1)Sj,所以Sj
15、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年10月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年10月19旅行商问题q给定一个带权重的完全图q找具有最小权重的周游路线（通过所有顶点的环）。45
16、谢谢你的阅读2019年10月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年10月19续n最短链路策略:与C中边不构成环路且不构成与v或w伴随的第3条边(无向图)最小权值边(v,w)n上述两个算法都不保证产生优化解，而且对其近似程度也不能给出界n定理13.22 设A是TSP问题的近似算法，如对任何输入I有rA(I)=c，则
17、PNPn从该定理可看出TSP的难度47谢谢你的阅读2019年10月19DNA 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),but not reducing the computational co
18、mplexity nCapabilityqHighly parallel qHuge Volume of storagenMain bottleneck qMaterials-Shapiro E,Benenson Y(2006)Bringing DNA Computers to Life.Scientific American,TURING MACHINEDNA MACHINE48谢谢你的阅读2019年10月1949谢谢你的阅读2019年10月19Quantum ComputernMotivationq Moores Law:We hit the quantum level 20102020.
19、q Quantum computation is more powerful than classical computation.q More can be computed in less timethe complexity classes are different!nA computation model based on quantum principles of physics(The physical universe is irreducibly random)nStorage capabilityqConventional bits hold flat binary dat
20、a(0 or 1)qQuantum Bits(Qubits)hold probabilities of values(superposition)nPower of Quantum ParallelismqA single operation applies to all superpositions at onceqAll possible results of an operation are retrievedqShors Algorithm-quantum computing algorithm to actually factor large numbers in polynomial time.50谢谢你的阅读2019年10月1951谢谢你的阅读2019年10月19
