1、NP-完全问题(NP Complete Problem)Thinking about Algorithms Abstractlyxxx天津大学计算机科学与技术学院谢谢你的关注2019-10-18主要内容 NP-完全问题：一些典型的例子 NP-完全问题：相关定义 近似算法 两种新的计算模型2谢谢你的关注2019-10-18NP-Complete:涵义 N-Nondeterministic Deterministic algorithm:Given a particular input,it will always produce the same correct output Non-deter
2、ministic algorithm:with one or more choice points where multiple different continuations are possible,without any specification of which one will be taken P-Polynomial(time)Computable Polynomial time is assumed the lowest complexity Complete Reducible输入/输出算法复杂性变换/封闭性3谢谢你的关注2019-10-18NP-C:典型的问题（1）问题1
3、 图着色问题 判定问题：是否存在不超过k种颜色的着色方案?优化问题：求图的最小着色数和着色方案 问题2 作业调度问题 判定问题：是否存在罚款额不超过k的作业调度?优化问题：求最小罚款额调度4谢谢你的关注2019-10-18NP-C:典型的问题（2）问题3 Bin packing问题：假设有n种物品，它们的尺寸分别为s1,sn，01使得n=jk?即n 是否为一合数?factor=0;for(j=2;jC 对应调度问题实例 pi=ti=si,di=C,k=S-C if部分:子集和数有解则调度问题有解 only if:假定上述调度问题有罚款额k的解 该可行调度的执行时间ti之和C(可行性)又因ti=
4、pi=si,所以该可行调度对应罚款额=S-pi=S-tiS-C=k 所以其罚款额k，而且被调度的作业的时间之和C21谢谢你的关注2019-10-18NP-难度和NP-完全问题 问题Q是NP-难度问题，如果：每个NP问题都可多项式地约化为问题 Q.问题 Q 是 NP-完全问题.如果:它是NP问题,同时它还是NP-难度问题.NP-完全问题的性质 所有NP-完全问题,相对于多项式约化关系,是自反,对称,传递的,即构成一个闭类.如果能找到一个NP完全问题的多项式算法则P=NP 有NP-难度问题但不知它是否在NP类内(第kth重子集问题)22谢谢你的关注2019-10-18Problems-unknow
5、n in NPKth重子集问题:任给定n+2 个正整数 c1,cn,k,L;是否存在1,2,n 的k 个不同子集S1,Sk 使得对所有i=1,k 有部分称为子集的重量,重量排序第k的子集.当k=2n-1时,表示可行解的字符串的长度有指数的长度.我们不知道该问题是否在NP中.图G的最大集团的节点数是否=k?上述问题是否在NP?也是未知的!(验证最大集团,不能在多项式时间内做到)LciSjj23谢谢你的关注2019-10-18CNF-satisfiablity问题是NP-完全问题 定理13.5 CNF-satisfiablity问题是NP-完全问题 这是著名的Cook定理 Cook 定理的推论:如
6、果CNF-可满足问题有多项式界的算法，则P=NP.24谢谢你的关注2019-10-18NP-完全问题证明 证明问题Q是NP-完全问题的步骤：(1)选择一已知的NP-完全问题P。(2)证明P可多项式的约化为 Q 背包问题属于NP子集和数属于NP 子集和数问题属于NP调度问题属于NP 不计其数的这种推导.25谢谢你的关注2019-10-18Lists of NP-Complete problems Boolean satisfiability problem(SAT)N-puzzle Knapsack problem Hamiltonian path problem Traveling sales
7、man problem Subgraph isomorphism problem Subset sum problem Clique problem Vertex cover problem Independent set problem Graph coloring problem 26谢谢你的关注2019-10-18What makes a problem hard(1)限定问题的一般性（问题的附加限制）实际应用中有特殊性,有可能找到多项式算法 例：Hamiltonian回路顶点度=2时，Hamiltonian回路问题有多项式算法 工程中有灵活性,以某种方式优化是NP-难度问题;但以另一方
8、式提出问题可能不是(优化标准)了解“难问题”的特点27谢谢你的关注2019-10-18What makes a problem hard(2)3-满足问题仍为NP-完全问题,但2-满足问题有多项式算法 集团问题,当顶点度=常数d时属于类P 平面图集团问题属于类P，因为平面图至多有4-集团 实际有意义的做法是提出合理的限制条件和求近似解,研究启发式算法.28谢谢你的关注2019-10-18优化问题和判定问题 3种问题 判定问题 求优化值问题 求优化解问题 优化问题至少与判定问题一样“难”优化值问题有多项式算法，则判定问题有多项式算法 多数情况下，如果能在多项式时间内求解决策问题，那么也能在多项式
9、时间内获得最优值（图着色问题）；有时则不能（TSP）29谢谢你的关注2019-10-18近似算法（1）返回次优解的算法。这种算法经常可以通过启发式方法得到，例如：贪心法。近似算法必须是多项式时间算法。为量度近似解对优化解的近似程度定义以下术语 FS(I)是输入I的可行解集。Val(I,x):实例I的可行解x的目标函数值 opt(I):实例I的优化解的值30谢谢你的关注2019-10-18近似算法（2）设A为一近似算法,令A(I)为输入I时该算法输出的可行解极小化和极大化问题度量近似性能的指标rA(I)极小化3.131)()(,()(IoptIAIvalIrA极大化4.131)(,()()(IA
10、IvalIoptIrA31谢谢你的关注2019-10-18续)5.13()(|)(max)(mIoptIrmRAA)6.13()(|)(max)(nIsizeIrnSAA式(13.5)定义的RA(m)为最坏情形rA(I)的值,是与输入I无关的指标:在固定优化值m下求最坏情形的比值式(13.6)定义的SA(n)也是一与输入独立的指标32谢谢你的关注2019-10-18Bin-Packing的近似算法 怎么装不同大小、不同形状的货物才能使占用的箱子数最少。该问题形式化如下：装箱问题 设S=(s1,sn)0 si=1，1=i=n 将 s1,sn 装入尽可能少的箱子里。假定每个箱子都有容量1。装箱问题
11、是NP-难度问题 搜索算法有指数的复杂度：须试所有可能的S的分划。33谢谢你的关注2019-10-18装箱问题：FFD算法（贪心法）将物品按尺寸递减排序，箱子从左到右排列并尽可能放在前面的箱子里。算法的时间复杂度t(n)=(n2)34谢谢你的关注2019-10-18算法：装箱问题 输入: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
12、-10-18近似分析 引理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-18近似分析 FFD算法没把物品k+1,i-1放在前k个箱子内(放不下),这些物品的数目为2(opt-k)尽管优化解的装箱情况和FFD不同,但前k个物品在优化解中也必须分放在k个箱子里:前k个物品中任2个都不能放在一个箱子内.优化解中物品k+
13、1,i-1,放在其余的opt-k个箱子内.因为这些物品的尺寸均1/3.所以这些箱子中每个箱子都要放2个,尽管放法和FFD不一定相同.因此 si 在优化解中无法安排,矛盾.38谢谢你的关注2019-10-18近似分析引理13.10:FFD在前opt(S)箱子装不下的物品数量至多为opt(S)-1 反证法:如有opt(S)个物品放在多用的箱内,则有:但 其中bi为装在第i个箱子内物品的总量;ti为前opt箱子装不下的物品的重量;按FFD算法后者不能装入第i个箱子.所有bi+ti1.定理13.11 RFFD(m)=(4/3)+(1/3m);SFFD(n)=3/2)()()(1)(1)(11Soptt
14、btbsiSoptiiSoptiisoptiinii)(1Soptsnii39谢谢你的关注2019-10-18近似分析FFD至多有m-1个物品放在extra箱子内,放的物品size1.41谢谢你的关注2019-10-18背包和子集和数问题 当所有pi=si时，背包问题转化为子集和 数的优化问题 算法13.2为上述简化的背包问题的近似算法sKnapk，类似k优化的背包问题的贪心算法。定理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)r(I)=m/
15、Val(k+1)/k=1+1/k 43谢谢你的关注2019-10-18图着色 算法13.3 for(i=1;in;i+)for(c=1;cn;c+)如没有与vi 相邻的顶点有着色c,对 vi 着色c 并break;Fig.13.11 如按先a类顶点后b类顶点着色算法13.3只需2种颜色;如交叉进行则需k种颜色 RSC(2)=;SSC(n)n/4(k=n/2,opt=2)44谢谢你的关注2019-10-18旅行商问题 给定一个带权重的完全图 找具有最小权重的周游路线（通过所有顶点的环）。45谢谢你的关注2019-10-18旅行商问题的近似算法 最近邻居策略NearestTSP(V,E,W)选择任
16、一顶点s作为周游路线C的起点 v=s;While 有顶点不再C中:选择有最小权重的边vw，其中 w 不在C中.将边vw加入C中;v=w;将边vs加入C.return C;时间复杂度t(n)=O(n2)n 是顶点的数量46谢谢你的关注2019-10-18续 最短链路策略:与C中边不构成环路且不构成与v或w伴随的第3条边(无向图)最小权值边(v,w)上述两个算法都不保证产生优化解，而且对其近似程度也不能给出界 定理13.22 设A是TSP问题的近似算法，如对任何输入I有rA(I)=c，则PNP 从该定理可看出TSP的难度47谢谢你的关注2019-10-18DNA ComputerOrigin fr
17、om similarity with Turing-computing Codes:(0,1)(A,T,G,C)Operator:(and,or,not)(copy,cut,paste)Initiated by Leonard Adleman for solving Hamiltonian path problem in 1994.Increasing performance(faster,tiny),but not reducing the computational complexity Capability Highly parallel Huge Volume of storageMa
18、in bottleneck Materials-Shapiro E,Benenson Y(2006)Bringing DNA Computers to Life.Scientific American,TURING MACHINEDNA MACHINE48谢谢你的关注2019-10-1849谢谢你的关注2019-10-18Quantum ComputerMotivation Moores Law:We hit the quantum level 20102020.Quantum computation is more powerful than classical computation.Mo
19、re can be computed in less timethe complexity classes are different!A computation model based on quantum principles of physics(The physical universe is irreducibly random)Storage capability Conventional bits hold flat binary data(0 or 1)Quantum Bits(Qubits)hold probabilities of values(superposition)Power of Quantum Parallelism A single operation applies to all superpositions at once All possible results of an operation are retrieved Shors Algorithm-quantum computing algorithm to actually factor large numbers in polynomial time.50谢谢你的关注2019-10-1851谢谢你的关注2019-10-18
