算法设计与分析 NP完全性理论与近似算法讲义

1第9章NP完全性理论关于NP完全性理论：一般性理解非确定性图灵机的概念理解P类与NP类问题(语言/算法)的概念理解NP完全问题、NP难问题的概念掌握证明一个问题是NP类问题的方法掌握证明一个问题是NPC问题的方法2是不是什么问题都是单计算机可解的？例一：求图G的最小顶点覆盖问题：问题描述：无向图G=(V,E)的顶点覆盖是它的顶点集V的一个子集V’V，使得若(u,v)是G的一条边，则v∈V’或u∈V’。顶点覆盖V’的大小是它所包含的顶点个数|V’|。算法：//给定图G=V,E,其中|V|=n，|E|=m第一步：枚举出V中所有的子集：子集总数=(n1)+(n2)+(n3)+…+(nn)=2n第二步：判断每个子集是否是图G的顶点覆盖：fori=1tomdo……算法时间复杂性：O(2n*m)可计算否？3例:假设n=56,在一台运行速度为亿次级每秒的计算机里用枚举法求解VC问题，须花时多少？计算：我们假设该机器每秒钟可判断一亿种的方案是否正确！则有：2^56种方案/1亿种每秒/60/60/24/365=22.85(年)！结论：对于O(2n)的算法，当n足够大时，全世界现有的计算机都无法在可接受的时间内求解。4是不是什么问题都是并行计算机可解的？并行计算阿姆达尔定律：Acc_Speed=1/(f+(1-f)/p)其中，f为求解某个问题的计算存在的必须串行执行的操作占整个计算的百分比；p为处理器的数目；Acc_Speed为并行计算机系统最大的加速能力。设f=1%,p=∞，则Acc_Speed=100结论：一个问题的求解若有1%的串行度，则无论有多少台计算机并行计算，其计算速度至多是单台计算机计算同一个问题的100倍！5易解/难解/不可解问题从时间复杂性分析来说，许多问题的算法时间复杂性是O(nc)的，其中n是问题的规模，c是常量。易解的问题！有些问题至今只设计出算法时间复杂性为O(2n)的算法，其中n是问题的规模。难解的问题！比如：SAT,VC,CLIQUE,IS,TSP,………不可解的问题！即：任何计算机不论耗费多少时间也不能解的问题。6图灵停机问题(TheHaltingProblem)问题：能不能设计一个程序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不存在着死循环；如果不停机就是存在着死循环。7图灵停机问题(TheHaltingProblem)假设程序P存在。那么我们可以根据P设计一个新的程序Q如下，其中X是任何一段程序的编码：ProgramQ(X){m=P(X,X)dowhile(m==no)//m=no意味着X不存在死循环。……enddoifm==yesthenreturn;}//m=yes意味着X不存在死循环。输入任何一段程序X，调用函数P(X,X)并得到返回值m，如果m=no，意味着P判断出程序X作用到X自身不存在死循环。那么Q就不停的做dowhile和enddo之间的语句。如果m=yes，表示P判断出程序X在以X为输入时存在死循环，此时，函数Q运行结束。8图灵停机问题(TheHaltingProblem)问Q这个程序作用到Q自身的编码上也就是Q(Q)会不会死循环呢？假设Q(Q)会发生死循环，那么P(Q,Q)就会返回yes。也就是m=yes，因此Q函数会马上结束，也就是程序Q(Q)没有发生死循环。矛盾！假设Q(Q)不发生死循环，那么P(Q,Q)应该返回no，也就是m=no，这样程序就会进入dowhile循环，而这个循环显然是一个死循环。因而Q(Q)发生了死循环！矛盾！无论Q(Q)会不会发生死循环，都会产生矛盾！假设P(X,Y)能够判断任意程序X在输入Y的时候是否死循环是错误的！也就是说这样的程序P(X,Y)不存在！9P类与NP类问题P类问题：已找到在确定性图灵机（DTM）上可在O(nc)时间求解的确定性算法的问题，c为常数；P类和NP类的严谨定义：P={L|L是一个能在多项式时间内被一台DTM所接受的语言}NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言}NP类问题：在非确定性图灵机(NDTM)上O(nc)时间内可验证的。10对NP类问题的理解之一P=？NPDTM:每一步只有一种选择。NDTM:每一步可以有多种选择。1．P类问题isinNP类问题？PNP即:P类问题一定也是NP类问题；2.NP类问题isinP类问题？NPP我们假设：NP类问题isnotinP类问题！即P≠NP正因为这一假设，构建起NP完全理论！是的！不知道！11对NP类问题的理解之二如果一个问题Q不属于P，则Q必属于NP。此话对否？也就是说，有一台NDTM（即会猜的机器），猜出问题Q的一个解S。难道我们还设计不出一个多项式时间的算法，从而正确判断出S猜对了还是猜错了？答：Q可能是“O(nc)时间内无法验证正确与否的问题”！如：求图G的最小顶点覆盖问题！我们讨论的是DecisionProblem!即要么是YES要么是NO的问题！OPTProblem转化为DecisionProblem12对NP类问题的理解之三证明Q∈NP1.掌握证明一个问题是否是NP类问题的方法。即：任意给你一个问题Q的实例I，要你证明该问题是NP类问题。证明思路分三步走：第一步要有一台会猜的计算机非确定性图灵机(NDTM);第二步设计一个算法，验证该机所猜的答案是否是对的。若是，则算法输出YES；若不是，则算法输出NO；第三步分析以上算法的时间复杂性。若Time=O(nc)，则我们说，该问题Q是NP类的问题。以上就是证明一个问题Q属于NP类问题的方法和步骤。13NP类问题证明举例KVC问题：给定无向图G=(V,E)，及整数k，G是否有k个顶点的顶点覆盖？证明：KVC问题是NP类问题。AlgorithmA:K_VC_NP(G,k)1.inputG=(V,E)andY={x1,x2,….,xk}∈V;//给定一个实例和Y2.foranyedgeei=u,v∈EdoifuorvinYthenloop;elseprint“YISNOTAVETEXCOVEROFG.”;EXIT3.print“YISAVEREXCOVEROFG.”;算法A的时间复杂性：O(|E|)≤O(n2)14NP类问题证明举例K-CLIQUE问题：给定无向图G=(V,E)，及整数k，G是否有k个顶点的团？团：是图G的一个子图G’G,G’是一个完全无向图。证明：K-CLIQUE问题是NP类问题。AlgorithmA:K_CLIQUE_NP(G,k)1.inputG=(V,E)andG’G;2.if|G’|=kandG’isaCompleteUndigraghthenprint“G’ISAK-CLIQUEOFG.”;3.elseprint“G’ISNOTAK-CLIQUEOFG.”;算法A的时间复杂性：O(|E|)≤O(n2)15NP类问题8-17证明NP中任何语言(问题)均可由一个计算时间为2O(n^k)的算法判定,其中k为一常数。设L∈NP，A是判定L的非确定性多项式时间算法在NDTM中，算法A可在cnk时间内判定L是YES还是NO。算法DA的时间复杂性：cnkd^(cn^k)=2O(n^k)判定字符串长度为cnk，字符集设为∑，令d=|∑|，则长度为cnk的字符串最多有d^(cnk)猜测至多有d^(cnk)种！设计一个确定性算法DA，枚举出任一种可能的猜测，然后在cnk时间内判定该猜测是否正确。16PNP。直观上看，P类问题是确定性计算模型下的易解问题类，而NP类问题是非确定性计算模型下的易验证问题类。大多数的计算机科学家认为NP类中包含了不属于P类的语言，即P≠NP。NP完全问题有一种令人惊奇的性质，即如果一个NP完全问题能在多项式时间内得到解决，那么NP中的每一个问题都可以在多项式时间内求解，即P=NP。目前还没有一个NP完全问题找到了多项式时间的算法。NP完全问题17•设，是2个语言。所谓语言能在多项式时间内变换为语言(简记为∝p)是指存在映射f:，且f满足：•(1)有一个计算f的多项式时间确定性图灵机；•(2)对于所有实例x∈，当且仅当f(x)∈。*11L*22L1L2L1L2L*2*11L2L多项式时间变换定义：语言L是NP完全的当且仅当(1)L∈NP；(2)对于所有L’∈NP有L’∝pL。如果有一个语言L满足上述性质(2)，但不一定满足性质(1)，则称该语言是NP难的。所有NP完全语言构成的语言类称为NP完全语言类，记为NPC。18•定理9-2：设L是NP完全的，则•(1)L∈P当且仅当P＝NP；•(2)若L∝p，且∈NP，则是NP完全的。1L1L1L定理的(2)可用来证明问题的NP完全性。但前提是：要有第一个NP完全问题L!多项式时间变换19Cook定理Cook定理：布尔表达式的可满足性问题SAT是NP完全的。SAT的一个实例是k个布尔变量，…，的m个布尔表达式，…，若存在各布尔变量(1≤i≤k)的0，1赋值，使每个布尔表达式(1≤i≤m)都取值1，则称布尔表达式…是可满足的。1xkx1AmAix1A2AmAiASAT∈NP是很明显的。对于任给的布尔变量，…，的0，1赋值，容易在多项式时间内验证相应的…的取值是否为1。因此，SAT∈NP。现在只要证明对任意的L∈NP有L∝pSAT即可。1xkx1A2AmA20一些典型的NP完全问题部分NP完全问题树21合取范式的可满足性问题CNF-SAT要证明CNF-SAT∈NPC，只要证明在Cook定理中定义的布尔表达式A，…，G或者已是合取范式，或者有的虽然不是合取范式，但可以用布尔代数中的变换方法将它们化成合取范式，而且合取范式的长度与原表达式的长度只差一个常数因子。问题描述：给定一个合取范式α，判定它是否可满足。如果一个布尔表达式是一些因子和之积，则称之为合取范式，简称CNF(ConjunctiveNormalForm)。这里的因子是变量或。例如：就是一个合取范式，而就不是合取范式。xx))()((3213221xxxxxxx321xxx22合取范式的可满足性问题CNF-3SAT证明思路：3-SAT∈NP是显而易见的。为了证明3-SAT∈NPC，只要证明CNF-SAT∝p3-SAT，即合取范式的可满足性问题可在多项式时间内变换为3-SAT。问题描述：给定一个3元合取范式α，判定它是否可满足。23团问题CLIQUE证明思路：已经知道CLIQUE∈NP。通过3-SAT∝pCLIQUE证明团问题是NP完全的。MOTIFFINDING问题描述：给定一个无向图G=(V，E)和一个正整数k，判定图G是否包含一个k团，即是否存在，V’V，|V’|=k，且对任意u，w∈V’有(u，w)∈E。24顶点覆盖问题证明思路：首先，VERTEX-COVER∈NP。其次，通过CLIQUE∝pVERTEX-COVER来证明顶点覆盖问题是NPC的。问题描述：给定一个无向图G=(V，E)和一个正整数k，判定是否存在V’V，|V’|=k，使得对于任意(u，v)∈E有u∈V’或v∈V’。如果存在这样的V’，就称V’为图G的一个大小为k顶点覆盖。25第九章NP完全问题的近似算法迄今为止，所有的NP完全问题都还没有多项式时间算法。对于这类问题，通常可采取以下几种解题策略：(1)只对问题的特殊实例求解(2)用动态规划法或分支限界法求解(比穷举法好)(3)用概率算法求解(4)只求近似解(5)用启发式方法求解26若一个最优化问题的最优值为c*，求解该问题的一个近似算法求得的近似最优解相应的目标函数值为c，则将该近似算法的性能比定义为在通常情况下，该性能比是问题输入规模n的一个函数ρ(n)，即该近似算法的相对误差定义为若对问题的