《NP完全问题.pptVIP

13章 NP-完全问题 13. NP-完全问题 N-Nondeterministic(算法) P-Polynomial (时间) Complete(封闭的类) 13.1 某些NP完全问题的例子 问题1 图着色问题 判定问题：是否存在不超过k种颜色的着色方案? 优化问题：求图的最小着色数和着色方案 问题2 作业调度问题 判定问题：是否存在罚款额不超过k的作业调度? 优化问题：求最小罚款额调度 问题3 Bin packing问题 假设有n种物品，它们的尺寸分别为s1,…,sn，0si≤1另有任意多个箱子(Bins)，箱子的容量为1， 优化问题：求使用最小箱数的装箱方法 判定问题：任意给定k，是否存在一种装箱方法使用的箱子数≤k？ 问题4 背包问题 判定问题：是否存在效益值至少为k的可行子集? 优化问题 问题5 子集和数问题s1,s2,┅,sn,C 判定问题：是否存在和数等于C的子集? 优化问题：求≤C的最大子集和数. 可归约为背包问题: pi=wi. 问题6 CNF(合取范式)-可满足问题 判定问题：是否存在真假赋值使得该CNF为真.合取范式例: 问题7 Hamiltonian 回路 判定问题 问题8 TSP(旅行商)问题 判定问题：任意给定一整数k，是否存在一长度不超过k的Hamiltonian回路？ 优化问题 13.2 类P与类NP 类P 类P 算法输入为问题实例的二进制编码. 定义该0/1字符串的长度为输入长度. 例如n个节点和m条边的图的长度为Θ(mlogn)(见图13.1). 多项式界(定义13.2) 如一算法的最坏情形时间复杂度T(n)=O(p(n)),其中p(n)为输入长度n 的多项式, 则称该算法有多项式界. 如一个问题有多项式界的算法,则称该问题有多项式界. 类P的定义 一个算法解决判定问题指: 对该判定问题的yes实例, 算法要停机并给出yes回答.对no实例算法要停机并给出no的回答. 有多项式界的判定问题组成的类称为类P. 多项式的相加,相乘及复合仍为多项式; 所以一个有多项式界的算法调用另一有多项式界的算法构成的算法仍有多项式界. 类NP 不确定的算法：对给定输入字符串w, 1. Guessing 不确定地写一个称为”certificate” (guessed 解)的字符串c . c 实际上是可行解的一种表示; 例如, 表示背包问题的n元组, 表示图的字符串或邻接矩阵. 2. checking 使用一确定的有多项式界的算法验证c是否为问题的答案. 如果是给出yes, 反之, 不回答. 多项式界指: 写c 和验证的时间为O(q(|w|)), q( )为某一多项式, w为输入长度. 不能实现的、虚构的算法 Void nondetA(String input) String s=genCertif(); boolean checkOK=verifyA(input,s) if (checkOK) Output “yes“ return checOK为false时不作反应. “不确定” 指:对同一输入w, 算法使用任意多个不同的c ,进行验证. 对不同c 的这些计算,可以看作是同时进行的. 一个不确定算法解决判定问题指:对输入w, 如果它有解, 不确定算法一定会写出一个c ,使得验证阶段能通过, 并返回一个yes回答. 如果一个判定问题有不确定的多项式界的算法则称它属于类NP. 例13.1图着色问题 Input: (着色数)k, (节点数)5 ,(图的边) (1,2)(1,4)...见图13.1. Guessing 指写出长度为n(节点数)的字符串,例如,RGRBG, RGRB, RBYGO, RGRBY, R%*$@等.至少有kn个“guessings”. Checking 指检查一guessed字符串是否合法及是否是一个k-着色. 如果写字符串的时间是O(p1(n)),checking时间是O(p2(n));而且p1(n), p2(n)是n的多项式(从而也是输入长度的多项式),则该不确定算法有多项式界. 如果输入的图能k着色则不确定算法停机并给出yes回答. P=NP? 类NP：有不确定的多项式界算法的判定问题构成的类称为NP类。 P=NP?是计算机科学中最大的问题之一 13.3 The size of input Problem13.9-是否存在j, k1使得n= jk?即n 是否为一合数? factor=0; for (j=2;jn;j++) if ((n mod j)==0)