《np-完全问题（npcompleteproblem）thinkingabout》由会员分享，可在线阅读，更多相关《np-完全问题（npcompleteproblem）thinkingabout（48页珍藏版）》请在金锄头文库上搜索。
1、NP-完全问题(NP Complete Problem) Thinking about Algorithms Abstractly,宫秀军 天津大学计算机科学与技术学院 ,主要内容,NP-完全问题：一些典型的例子 NP-完全问题：相关定义 近似算法 两种新的计算模型,NP-Complete: 涵义,N-Nondeterministic Deterministic algorithm: Given a particular input, it will always produce the same correct output Non-deterministic algorithm: with
2、 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,输入/输出,算法复杂性,变换/封闭性,NP-C:典型的问题（1）,问题1 图着色问题 判定问题：是否存在不超过k种颜色的着色方案? 优化
3、问题：求图的最小着色数和着色方案 问题2 作业调度问题 判定问题：是否存在罚款额不超过k的作业调度? 优化问题：求最小罚款额调度,NP-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=pi=si,所以该可行调度对应罚款额=S-pi =S-tiS-C=k 所以其罚款额
4、k，而且被调度的作业的时间之和C,NP-难度和NP-完全问题,问题Q是NP-难度问题，如果： 每个NP问题都可多项式地约化为问题 Q. 问题 Q 是 NP-完全问题. 如果: 它是NP问题, 同时它还是NP-难度问题. NP-完全问题的性质 所有NP-完全问题,相对于多项式约化关系,是自反,对称,传递的,即构成一个闭类. 如果能找到一个NP完全问题的多项式算法则P=NP 有NP-难度问题但不知它是否在NP类内(第kth重子集问题),Problems-unknown in NP,Kth重子集问题:任给定n+2 个正整数 c1,cn, k, L; 是否存在1,2,n 的k 个不同子集S1,Sk 使
5、得对所有i=1,k 有部分称为子集的重量, 重量排序第k的子集. 当k=2n-1时,表示可行解的字符串的长度有指数的长度.我们不知道该问题是否在NP中. 图G的最大集团的节点数是否=k? 上述问题是否在NP?也是未知的! (验证最大集团,不能在多项式时间内做到),CNF-satisfiablity问题是NP-完全问题,定理13.5 CNF-satisfiablity问题是NP-完全问题 这是著名的Cook定理 Cook 定理的推论:如果CNF-可满足问题有多项式界的算法，则P=NP.,NP-完全问题证明,证明问题Q是NP-完全问题的步骤：(1)选择一已知的NP-完全问题P。 (2)证明P可多项
6、式的约化为 Q 背包问题属于NP子集和数属于NP 子集和数问题属于NP调度问题属于NP 不计其数的这种推导.,What makes a problem hard(1),限定问题的一般性（问题的附加限制） 实际应用中有特殊性, 有可能找到多项式算法 例：Hamiltonian回路顶点度=2时，Hamiltonian回路问题有多项式算法 工程中有灵活性,以某种方式优化是NP-难度问题;但以另一方式提出问题可能不是(优化标准) 了解“难问题”的特点,What makes a problem hard(2),3-满足问题仍为NP-完全问题,但2-满足问题有多项式算法 集团问题,当顶点度=常数d时属于类
7、P 平面图集团问题属于类P，因为平面图至多有4-集团 实际有意义的做法是提出合理的限制条件和求近似解, 研究启发式算法.,优化问题和判定问题,3种问题 判定问题 求优化值问题 求优化解问题 优化问题至少与判定问题一样“难” 优化值问题有多项式算法，则判定问题有多项式算法 多数情况下，如果能在多项式时间内求解决策问题，那么也能在多项式时间内获得最优值（图着色问题）；有时则不能（TSP）,近似算法（1）,返回次优解的算法。这种算法经常可以通过启发式方法得到，例如：贪心法。 近似算法必须是多项式时间算法。 为量度近似解对优化解的近似程度定义以下术语 FS(I) 是输入I的可行解集。 Val(I,x):实例I的可行解x的目标函数值 opt(I):实例I的优化解的值,近似算法（2）,设A为一近似算法,令A(I)为输入I时该算法输出的可行解 极小化和极大化问题度量近似性能的指标rA(I),续,式(13.5)定义的RA(m)为最坏情形rA(I)的值,是与输入I无关的指标: 在固定优化值m下求最坏情形的比值,
