算法设计与NP完全性理论与近似算法

1、第9章 NP完全性理论关于NP完全性理论： 一般性理解非确定性图灵机的概念 理解P类与NP类问题(语言/算法)的概念 理解NP完全问题、NP难问题的概念 掌握证明一个问题是NP类问题的方法 掌握证明一个问题是NPC问题的方法是不是什么问题都是单计算机可解的？是不是什么问题都是单计算机可解的？例一：求图G的最小顶点覆盖问题：问题描述：无向图G=(V,E)的顶点覆盖是它的顶点集V的一个子集V V，使得若(u,v)是G的一条边，则vV或uV。顶点覆盖V的大小是它所包含的顶点个数|V|。算法：/给定图G =,其中|V| =n，|E| =m第一步：枚举出V中所有的子集： 子集总数= (n1) + (n2

2、) +(n3) + (nn) =2n第二步：判断每个子集是否是图G的顶点覆盖：for i =1 to m do算法时间复杂性：O(2n*m) 可计算否？例:假设 n=56, 在一台运行速度为 亿次级每秒的计算机里用枚举法求解VC问题，须花时多少？计算：我们假设该机器每秒钟可判断一亿种的方案是否正确！则有：256种方案/1亿种每秒/60/60/24/365=22.85(年)！结论：对于O(2n)的算法，当n足够大时，全世界现有的计算机都无法在可接受的时间内求解。是不是什么问题都是并行计算机可解的？是不是什么问题都是并行计算机可解的？并行计算阿姆达尔定律：Acc_Speed =1/(f+(1-f)

3、/p)其中，f为求解某个问题的计算存在的必须串行执行的操作占整个计算的百分比；p为处理器的数目；Acc_Speed为并行计算机系统最大的加速能力。设f = 1%, p =，则Acc_Speed =100结论：一个问题的求解若有1%的串行度，则无论有多少台计算机并行计算，其计算速度至多是单台计算机计算同一个问题的100倍！易解易解/ /难解难解/ /不可解问题不可解问题从时间复杂性分析来说，许多问题的算法时间复杂性是O(nc)的，其中n是问题的规模，c是常量。易解的问题！有些问题至今只设计出算法时间复杂性为O(2n)的算法，其中n是问题的规模。难解的问题！比如：SAT, VC, CLIQUE,

4、IS, TSP, 不可解的问题！即：任何计算机不论耗费多少时间也不能解的问题。图灵停机问题图灵停机问题(The Halting Problem)(The Halting Problem)问题：能不能设计一个程序P，判断出任意一个程序X是否会在输入Y的情况下陷入死循环？设P(X,Y)表示P判断程序X在输入为Y时的结果。如果X存在死循环，那么P(X,Y)就输出一个yes。如果X不存在死循环，那么P(X,Y)就输出一个no。这样的P(X,Y)存在么？某个程序X在输入Y上停机，就是说X不存在着死循环；如果不停机就是存在着死循环。 图灵停机问题图灵停机问题(The Halting Problem)(Th

5、e Halting Problem)。那么我们可以根据。那么我们可以根据P设计一个新的程序设计一个新的程序Q如下，其中如下，其中X是任何一段程序的编码：是任何一段程序的编码： Program Q(X) m=P(X,X) do while (m=no) /m=no意味着意味着X不存在死循环。不存在死循环。 enddo if m=yes then return; /m=yes意味着意味着X不存在死循环。不存在死循环。 输入任何一段程序输入任何一段程序X，调用函数，调用函数P(X,X)并得到返回值并得到返回值m，如，如果果m=no，意味着，意味着P判断出程序判断出程序X作用到作用到X自身不存在死循环

6、。自身不存在死循环。那么那么Q就不停的做就不停的做do while和和enddo之间的语句。如果之间的语句。如果m=yes，表示表示P判断出程序判断出程序X在以在以X为输入时存在死循环，此时，函数为输入时存在死循环，此时，函数Q运行结束。运行结束。 图灵停机问题图灵停机问题(The Halting Problem)(The Halting Problem)问问Q这个程序作用到这个程序作用到Q自身的编码上也就是自身的编码上也就是Q(Q)会不会死循环呢？会不会死循环呢？ 假设假设Q(Q)会发生死循环，那么会发生死循环，那么P(Q,Q)就会返回就会返回yes。也就是。也就是m=yes，因此，因此Q函

7、数会马上结束，也就是程序函数会马上结束，也就是程序Q(Q)没有发生没有发生死循环。死循环。假设假设Q(Q)不发生死循环，那么不发生死循环，那么P(Q,Q)应该返回应该返回no，也就是，也就是m=no，这样程序就会进入，这样程序就会进入do while循环，而这个循环显然是循环，而这个循环显然是一个死循环。因而一个死循环。因而Q(Q)发生了死循环！发生了死循环！无论无论Q(Q)会不会发生死循环，都会产生矛盾！会不会发生死循环，都会产生矛盾！假设假设P(X,Y)能够判断任意程序能够判断任意程序X在输入在输入Y的时候是否死循环是的时候是否死循环是错误的！也就是说这样的错误的！也就是说这样的！ P P

8、类与类与NPNP类问题类问题P类问题：已找到在确定性图灵机（DTM）上可在O(nc)时间求解的确定性算法的问题，c为常数；P类和NP类的严谨定义：P=L|L是一个能在多项式时间内多项式时间内被一台DTM所接受的语言 NP=L|L是一个能在多项式时间多项式时间内被一台NDTM所接受的语言NP类问题：在非确定性图灵机(NDTM)上O(nc)时间内可验证的。对对NPNP类问题的理解之一类问题的理解之一 P P=？NPDTM:每一步只有一种选择。NDTM:每一步可以有多种选择。 1P类问题 is in NP类问题？ P NP 即: P类问题一定也是NP类问题；2. NP类问题 is in P类问题？

9、NP P 我们假设： NP类问题 is not in P类问题！即PNP正因为这一假设，构建起NP完全理论！是的！不知道！对对NPNP类问题的理解之二类问题的理解之二如果一个问题Q不属于P，则Q必属于NP。此话对否？也就是说，有一台NDTM（即会猜的机器），猜出问题Q的一个解S。难道我们还设计不出一个多项式时间的算法，从而正确判断出S猜对了还是猜错了？答：Q可能是“O(nc)时间内无法验证正确与否的问题”！如：求图G的最小顶点覆盖问题！对对NPNP类问题的理解之三类问题的理解之三证明证明Q NPQ NP1. 掌握证明一个问题是否是NP类问题的方法。即：任意给你一个问题Q的实例 I，要你证明该问

10、题是NP类问题。证明思路分三步走：第一步要有一台会猜的计算机非确定性图灵机(NDTM);第二步设计一个算法，验证该机所猜的答案是否是对的。若是，则算法输出YES；若不是，则算法输出NO；第三步分析以上算法的时间复杂性。若Time = O(nc) ，则我们说，该问题Q是NP类的问题。以上就是证明一个问题Q属于NP类问题的方法和步骤。NPNP类问题证明举例类问题证明举例KVC问题：给定无向图G=(V,E)，及整数k，G是否有k个顶点的顶点覆盖？证明： KVC问题是NP类问题。Algorithm A: K_VC_NP(G,k) 1. input G=(V,E) and Y=x1,x2,.,xk V;

11、/给定一个实例和Y 2. for any edge ei= E do if u or v in Y then loop; else print “Y IS NOT A VETEX COVER OF G.”;EXIT 3. print “Y IS A VEREX COVER OF G.”;算法A的时间复杂性：O(|E|) O(n2) NPNP类问题证明举例类问题证明举例K-CLIQUE问题：给定无向图G=(V,E)，及整数k，G是否有k个顶点的团？团：是图G的一个子图G G, G 是一个完全无向图。证明： K-CLIQUE问题是NP类问题。Algorithm A: K_CLIQUE_NP(G,k

12、) 1. input G=(V,E) and G G; 2. if |G|=k and G is a Complete Undigragh then print “G IS A K-CLIQUE OF G.”; 3. else print “G IS NOT A K-CLIQUE OF G.”;算法A的时间复杂性：O(|E|) O(n2) NPNP类问题类问题8-178-17证明NP中任何语言(问题)均可由一个计算时间为2O(nk)的算法判定,其中k为一常数。设L NP，A是判定L的非确定性多项式时间算法在NDTM中，算法A可在cnk时间内判定L是YES还是NO。算法DA的时间复杂性：cnkd

13、(cnk) = 2O(nk) 判定字符串长度为cnk ，字符集设为，令d=|，则长度为cnk的字符串最多有d(cnk)猜测至多有d(cnk)种！设计一个确定性算法DA，枚举出任一种可能的猜测，然后在cnk时间内判定该猜测是否正确。 PNP。 直观上看，P类问题是确定性计算模型下的易解问题类，而NP类问题是非确定性计算模型下的易验证问题类。 大多数的计算机科学家认为NP类中包含了不属于P类的语言，即PNP。 NP完全问题有一种令人惊奇的性质，即如果一个NP完全问题能在多项式时间内得到解决，那么NP中的每一个问题都可以在多项式时间内求解，即P=NP。 目前还没有一个NP完全问题找到了多项式时间的算

14、法。NP完全问题 设，是2个语言。所谓语言能在多项式时间内变换为语言(简记为p )是指存在映射f: ，且f满足： (1)有一个计算f的多项式时间确定性图灵机； (2)对于所有实例x，当且仅当f(x)。 *11L*22L1L2L1L2L*2*11L2L多项式时间变换定义：定义：语言L是的当且仅当(1)LNP；(2)对于所有LNP有L p L。如果有一个语言L满足上述性质(2)，但不一定满足性质(1)，则称该语言是的。所有NP完全语言构成的语言类称为NP完完全语言类全语言类，记为NPC。 定理定理9-29-2：设L是NP完全的，则 (1)LP当且仅当PNP； (2)若Lp，且NP，则是NP完全的。

15、 1L1L1L定理的定理的(2)(2)可用来证明问可用来证明问题的题的NPNP完全性。但前提是：完全性。但前提是：! !多项式时间变换Cook定理 布尔表达式的可满足性问题布尔表达式的可满足性问题SATSAT是是NPNP完全的。完全的。 SAT的一个实例是k个布尔变量 ， 的m个布尔表达式 ， 若存在各布尔变量 (1ik)的0，1赋值，使每个布尔表达式 (1im)都取值1，则称布尔表达式 是可满足的。 1xkx1AmAix1A2AmAiA SATNP是很明显的。对于任给的布尔变量 ， 的0，1赋值，容易在多项式时间内验证相应的 的取值是否为1。因此，SATNP。 现在只要证明对任意的LNP有L

16、pSAT即可。1xkx1A2AmA一些典型的NP完全问题部分NP完全问题树合取范式的可满足性问题合取范式的可满足性问题CNF-SATCNF-SAT 要证明CNF-SATNPC，只要证明在Cook定理中定义的布尔表达式A，G或者已是合取范式，或者有的虽然不是合取范式，但可以用布尔代数中的变换方法将它们化成合取范式，而且合取范式的长度与原表达式的长度只差一个常数因子。 问题描述：问题描述：给定一个合取范式，判定它是否可满足。 如果一个布尔表达式是一些因子和之积，则称之为合取范式，简称CNF(Conjunctive Normal Form)。这里的因子是变量 或 。例如： 就是一个合取范式，而 就不

17、是合取范式。 xx)()(3213221xxxxxxx321xxx合取范式的可满足性问题CNF-3SAT证明思路：证明思路： 3-SATNP是显而易见的。为了证明3-SATNPC，只要证明CNF-SATp 3-SAT，即合取范式的可满足性问题可在多项式时间内变换为3-SAT。问题描述：问题描述：给定一个3元合取范式，判定它是否可满足。 团问题CLIQUE 证明思路：证明思路： 已经知道CLIQUENP。通过3-SATpCLIQUE证明团问题是NP完全的。MOTIF FINDING 问题描述：问题描述：给定一个无向图G=(V，E)和一个正整数k，判定图G是否包含一个k团，即是否存在，VV，|V|

18、=k，且对任意u，wV有(u，w)E。 顶点覆盖问题 证明思路：证明思路： 首先，VERTEX-COVERNP。 其次，通过CLIQUEpVERTEX-COVER来证明顶点覆盖问题是NPC的。 问题描述：问题描述：给定一个无向图G=(V，E)和一个正整数k，判定是否存在VV，|V|=k，使得对于任意(u，v)E有uV或vV。如果存在这样的V，就称V为图G的一个大小为k顶点覆盖。 第九章 NP完全问题的近似算法迄今为止，所有的NP完全问题都还没有多项式时间算法。对于这类问题，通常可采取以下几种解题策略： (1)只对问题的特殊实例求解 (2)用动态规划法或分支限界法求解(比穷举法好) (3)用概率

19、算法求解 (4)只 (5)用启发式方法求解若一个最优化问题的最优值为c*，求解该问题的一个近似算法求得的近似最优解相应的目标函数值为c，则将该近似算法的性能比定义为在通常情况下，该性能比是问题输入规模n的一个函数(n)，即该近似算法的相对误差定义为若对问题的输入规模n，有一函数(n)使得则称(n)为该近似算法的相对误差界。近似算法的性能比(n)与相对误差界(n)之间显然有如下关系：(n)(n)-1。 ncccc*,*max*ccc nccc*9.4.1 近似算法的性能cccc*,*max 问题描述：无向图G=(V,E)的顶点覆盖是它的顶点集V的一个子集VV，使得若(u,v)是G的一条边，则vV

20、或uV。顶点覆盖V的大小是它所包含的顶点个数|V|。 算法描述：VertexSet approxVertexCover ( Graph g )cset= ；e1=g.e；while (e1 != )从e1中任取一条边(u,v)；cset=csetu,v；从e1中删去与u和v相关联的所有边；return cset;9.4.2 顶点覆盖问题的近似算法cset用来存储顶点覆用来存储顶点覆盖中的各顶点。初始盖中的各顶点。初始为空，不断从边集为空，不断从边集e1中选取一边中选取一边(u,v)，将将边的端点加入边的端点加入cset中，中，并将并将e1中已被中已被u和和v覆覆盖的边删去，直至盖的边删去，直至

21、cset已覆盖所有边。已覆盖所有边。即即e1为空。为空。图图(a)(e)说明了说明了算法的运行过程算法的运行过程及结果。及结果。(e)表示表示算法产生的近似算法产生的近似最优顶点覆盖最优顶点覆盖cset，它由顶点它由顶点b,c,d,e,f,g所组成。所组成。(f)是图是图G的一个的一个最小顶点覆盖，最小顶点覆盖，它只含有它只含有3个顶点：个顶点：b,d和和e。顶点覆盖近似算法示例算法approxVertexCover的性能比为2。算法选取出的边的集合用A表示，则A中任何两条边没有公共端点。故有：|cset|=2|A|另外，图G的最小顶点覆盖|cset*|=|A|，因为A中的边没有公共端点。|c

22、set|/| cset*|=2算法approxVertexCover的性能比为2。算法approxVertexCover的性能比问题描述：给定一个完全无向图G=(V,E)，其每一边(u,v)E有一非负整数费用c(u,v)。要找出G的最小费用哈密顿回路。旅行售货员问题的一些特殊性质： 比如，费用函数c往往具有，即对任意的3个顶点u,v,wV，有：c(u,w)c(u,v)+c(v,w)。当图G中的顶点就是平面上的点，任意2顶点间的费用就是这2点间的欧氏距离时，费用函数c就具有三角不等式性质。旅行售货员问题近似算法1.满足三角不等式的旅行售货员问题对于给定的无向图G，可以利用找图G的最小生成树的算法

23、设计找近似最优的旅行售货员回路的算法。void approxTSP (Graph g)1) 选择g的任一顶点r；2) 用Prim算法找出带权图g的一棵以r为根的最小生成树T；3) 前序遍历树T得到的顶点表L；4) 将r加到表L的末尾，按表L中顶点次序组成回路H，作为计算结果返回；Prim算法回顾算法回顾Prim算法用于求无向图的最小生成树算法用于求无向图的最小生成树 设图设图G =（V，E），其生成树的顶点集合为），其生成树的顶点集合为U。 、把、把v0放入放入U。 、在所有、在所有uU，vV-U的边的边(u，v)E中找一中找一条最小权值的边，加入生成树。条最小权值的边，加入生成树。 、把、把

24、找到的边的找到的边的v加入加入U集合。如果集合。如果U集合已集合已有有n个元素，则结束，否则继续执行个元素，则结束，否则继续执行。 其算法的时间复杂度为其算法的时间复杂度为O(n2)(b)表示找到的最小生成树T；(c)表示对T作前序遍历的次序；(d)表示L产生的哈密顿回路H；(e)是G的一个最小费用旅行售货员回路。示例算法approxTSP 性能分析用H*记图G的最小费用旅行售货员回路，用H记算法approxTSP计算出的近似最优的旅行售货员回路，则：c(H)=2c(H*)。分析：设approxTSP找到的最小生成树为T；从H*中任意删去一条边后，也得到图G的一棵生成树。故：c(T) =c(H

25、*)。对T进行先序遍历得：W=abcbhbadefegeda，其路径总和c(W)=2c(T) =2c(H*)H =abchdefga，根据三角不等式，得：c(H)=c(W) 1，不存在性能比为的解旅行售货员问题的多项式时间近似算法。问题描述：集合覆盖问题是一个最优化问题，其原型是多资源选择问题。集合覆盖问题可以看作是图的顶点覆盖问题的推广，它也是一个NP难问题。集合覆盖问题的一个实例X,F由一个有限集X及X的一个子集族F组成。子集族F覆盖了有限集X。也就是说X中每一元素至少属于F中的一个子集，即X=对于F中的一个子集CF，若C中的X的子集覆盖了X，即X=则称C覆盖了X。集合覆盖问题就是要找出F

26、中覆盖X的最小子集C*，使得|C*|=min|C|CF且C覆盖XCSS集合覆盖问题的近似算法FSS用12个黑点表示集合X。F=S1,S2,S3,S4,S5,S6，如图所示。容易看出，对于这个例子，最小集合覆盖为：C=S3,S4,S5,。 示例算法的循环体最多执行min|X|，|F|次。而循环体内的计算显然可在O(|X|F|)时间内完成。因此，算法的计算时间为O(|X|F|min|X|，|F|)。由此即知，该算法是一个多项式时间算法。 贪心算法set greedySetCover (X,F)U=X；C=；while (U !=)选择F中使|SU|最大的子集S；U=U-S；C=CS；return

27、C；问题描述：设子集和问题的一个实例为S,t。其中，S=x1，x2，xn是一个正整数的集合，t是一个正整数。子集和问题判定是否存在S的一个子集S1，使得txSx19.4.5 子集和问题的近似算法算法以集合S=x1，x2，xn和目标值t作为输入。算法中用到将2个有序表L1和L2合并成为一个新的有序表的算法mergeLists(L1,L2)。1.子集和问题的指数时间算法 int exactSubsetSum (S,t) int n=|S|； L0=0； for (int i=1；i=n；i+) Li=mergeLists(Li-1,Li-1+Si)； 删去Li中超过t的元素； return max

28、(Ln)； 基于算法exactSubsetSum，通过对表Li作适当的修整建立一个子集和问题的完全多项式时间近似格式。 在对表Li进行修整时，用到一个修整参数，01。用参数修整一个表L是指从L中删去尽可能多的元素，使得每一个从L中删去的元素y，都有一个修整后的表L1中的元素z满足(1-)yzy。可以将z看作是被删去元素y在修整后的新表L1中的代表。 举例：若=0.1，且L=10,11,12,15,20,21,22,23,24,29，则用对L进行修整后得到L1=10，12，15，20，23，29。其中被删去的数11由10来代表，21和22由20来代表，24由23来代表。2.子集和问题的完全多项式时间近似格式 对有序表L修整算法：List trim(L,)int m=|L|；L1=L1；int last=L1；for (int i=2；i=m；i+)if (last(1-)*Li)将Li加入表L1的尾部；l