计算机算法设计与分析第9章.ppt

第9章 NP完全性理论与近似算法1 学习要点学习要点学习要点学习要点 理解理解RAMRAM，RASPRASP和图灵机计算模型和图灵机计算模型 理解非确定性图灵机的概念理解非确定性图灵机的概念 理解理解P P类与类与NPNP类语言的概念类语言的概念 理解理解NPNP完全问题的概念完全问题的概念 理解近似算法的性能比及多项式时间近似格式的概念理解近似算法的性能比及多项式时间近似格式的概念 通过范例学习通过范例学习NPNP完全问题的近似算法完全问题的近似算法（1 1）顶点覆盖问题；）顶点覆盖问题；（2 2）旅行售货员问题；）旅行售货员问题；（3 3）集合覆盖问题；）集合覆盖问题；（4 4）子集和问题。）子集和问题。29.19.1 计算模型计算模型n n在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型，包括定在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型，包括定义该计算模型中所用的基本运算。义该计算模型中所用的基本运算。n n建立计算模型的目的是为了使问题的计算复杂性分析有一个共同的客观尺度。建立计算模型的目的是为了使问题的计算复杂性分析有一个共同的客观尺度。n n3 3个基本计算模型：个基本计算模型：n n随机存取机随机存取机RAM(RandomRAM(Random Access Machine)Access Machine)；n n随机存取存储程序机随机存取存储程序机RASP(RandomRASP(Random Access Stored Program Machine)Access Stored Program Machine)n n图灵机图灵机(Turing Machine)(Turing Machine)。n n这这3 3个计算模型在计算能力上是等价的，但在计算速度上是不同的。个计算模型在计算能力上是等价的，但在计算速度上是不同的。39.1.1 随机存取机RAM1、RAMRAM的结构的结构49.1.1 随机存取机RAM2、RAMRAM程序程序 一个RAM程序定义了从输入带到输出带的一个映射。可以对这种映射关系作2种不同的解释。解释一：把解释一：把RAMRAM程序看成是计算一个函数程序看成是计算一个函数若一个RAM程序P总是从输入带前n个方格中读入n个整数x1，x2，xn，并且在输出带的第一个方格上输出一个整数y后停机，那么就说程序P计算了函数f(xf(x1 1，x x2 2，x xn n)=y)=y 解释二：把解释二：把RAMRAM程序当作一个语言接受器。程序当作一个语言接受器。将字符串S=a1a2an放在输入带上。在输入带的第一个方格中放入符号a1，第二个方格中放入符号a2，第n个方格中放入符号an。然后在第n+1个方格中放入0，作为输入串的结束标志符。如果一个RAM程序P读了字符串S及结束标志符0后，在输出带的第一格输出一个1并停机，就说程序P接受字符串S。59.1.1 随机存取机RAM3、RAMRAM程序的耗费标准程序的耗费标准标准一：均匀耗费标准标准一：均匀耗费标准在均匀耗费标准下，每条RAM指令需要一个单位时间；每个寄存器占用一个单位空间。以后除特别注明，RAM程序的复杂性将按照均匀耗费标准衡量。标准二：对数耗费标准标准二：对数耗费标准对数耗费标准是基于这样的假定，即执行一条指令的耗费与以二进制表示的指令的操作数长度成比例。在RAM计算模型下，假定一个寄存器可存放一个任意大小的整数。因此若设l(i)是整数i所占的二进制位数，则 69.1.2 随机存取存储程序机RASP1、RASPRASP的结构的结构RASP的整体结构类似于RAM，所不同的是RASP的程序是存储在寄存器中的。每条RASP指令占据2个连续的寄存器。第一个寄存器存放操作码的编码，第二个寄存器存放地址。RASP指令用整数进行编码。2、RASPRASP程序程序的复杂性的复杂性不管是在均匀耗费标准下，还是在对数耗费标准下，RAM程序和RASP程序的复杂性只差一个常数因子。在一个计算模型下T(n)时间内完成的输入-输出映射可在另一个计算模型下模拟，并在kT(n)时间内完成。其中k是一个常数因子。空间复杂性的情况也是类似的。79.1.3 图灵机89.1.3 图灵机 根据有限状态控制器的当前状态及每个读写头读到的带符号，图灵机的一个计算步可实现下面3个操作之一或全部。(1)改变有限状态控制器中的状态。(2)清除当前读写头下的方格中原有带符号并写上新的带符号。(3)独立地将任何一个或所有读写头，向左移动一个方格(L)或向右移动一个方格(R)或停在当前单元不动(S)。k带图灵机可形式化地描述为一个7元组(Q，T，I，b，q0，qf)，其中:(1)Q是有限个状态的集合。(2)T是有限个带符号的集合。(3)I是输入符号的集合，IT。(4)b是唯一的空白符，bT-I。(5)q0是初始状态。(6)qf是终止(或接受)状态。(7)是移动函数。它是从QTk的某一子集映射到Q(TL，R，S)k的函数。99.1.3 图灵机图灵机M的时间复杂性T(n)是它处理所有长度为n的输入所需的最大计算步数。如果对某个长度为n的输入，图灵机不停机，T(n)对这个n值无定义。图灵机的空间复杂性S(n)是它处理所有长度为n的输入时，在k条带上所使用过的方格数的总和。如果某个读写头无限地向右移动而不停机，S(n)也无定义。与RAM模型类似，图灵机既可作为语言接受器，也可作为计算函数的装置。109.2 P类与NP类问题n n一一般般地地说说，将将可可由由多多项项式式时时间间算算法法求求解解的的问问题题看看作作是是易易处处理理的的问问题题，而而将将需需要要超超多多项项式时间才能求解的问题看作是难处理的问题。式时间才能求解的问题看作是难处理的问题。n n有有许许多多问问题题，从从表表面面上上看看似似乎乎并并不不比比排排序序或或图图的的搜搜索索等等问问题题更更困困难难，然然而而至至今今人人们们还还没没有有找找到到解解决决这这些些问问题题的的多多项项式式时时间间算算法法，也也没没有有人人能能够够证证明明这这些些问问题题需需要要超超多多项项式式时间下界。时间下界。n n在图灵机计算模型下，这类问题的计算复杂性至今未知。在图灵机计算模型下，这类问题的计算复杂性至今未知。n n为为了了研研究究这这类类问问题题的的计计算算复复杂杂性性，人人们们提提出出了了另另一一个个能能力力更更强强的的计计算算模模型型，即即非非确确定定性图灵机计算模型，简记为性图灵机计算模型，简记为NDTM(NondeterministicNDTM(Nondeterministic Turing Machine)Turing Machine)。n n在非确定性图灵机计算模型下，许多问题可以在多项式时间内求解。在非确定性图灵机计算模型下，许多问题可以在多项式时间内求解。119.2.1 非确定性图灵机非确定性图灵机非确定性图灵机（NDTMNDTM ）：一个k带的非确定性图灵机M是一个7元组：(Q，T，I，b，q0，qf)。与确定性图灵机不同的是非确定性图灵机允许移动函数具有不确定性具有不确定性，即对于QTk中的每一个值(q;x1,x2,xk)，当它属于的定义域时，Q(TL，R，S)k中有唯一的一个子集子集(q;x1,x2,xk)与之对应。可以在(q;x1,x2,xk)中随意选定一个值作为它的函数值。在图灵机计算模型中，移动函数是单值的是单值的，即对于QTk中的每一个值，当它属于的定义域时，Q(TL，R，S)k中只有唯一的值与之对应，称这种图灵机为确定性图灵机确定性图灵机，简记为DTMDTM(Deterministic Turing Machine)。129.2.2 P类与NP类语言 P类和NP类语言的定义：P=L|L是一个能在多项式时间内多项式时间内被一台DTMDTM所接受的语言 NP=L|L是一个能在多项式时间多项式时间内被一台NDTMNDTM所接受的语言由于一台确定性图灵机可看作是非确定性图灵机的特例，所以可在多项式时间内被确定性图灵机接受的语言也可在多项式时间内被非确定性图灵机接受。故P P NP NP。139.2.2 P类与NP类语言 NPNP类语言举例类语言举例无向图的团问题无向图的团问题。该问题的输入是一个有n个顶点的无向图G=(V，E)和一个整数k。要求判定图G是否包含一个k顶点的完全子完全子图图(团团)，即判定是否存在VV，|V|=k，且对于所有的u，vV，有(u，v)E。若用邻接矩阵表示图G，用二进制串表示整数k，则团问题的一个实例可以用长度为 的二进位串表示。因此，团问题可表示为语言：CLIQUE=w#v|w，v0，1*，以w为邻接矩阵的图G有一个k顶点的团，其中v是k的二进制表示。149.2.2 P类与NP类语言 接受该语言CLIQUE的非确定性算法非确定性算法：用非确定性选择指令选出包含k个顶点的候选顶点子集V，然后确定性地检查该子集是否是团问题的一个解。算法分为3个阶段：算法的第一阶段将输入串w#v分解，并计算出n=，以及用v表示的整数k。若输入不具有形式w#v或|w|不是一个平方数就拒绝该输入。显而易见，第一阶段可 在时间内完成。在算法的第二阶段中，非确定性地选择V的一个k元子集VV。算法的第三阶段是确定性地检查V的团性质。若V是一个团则接受输入，否则拒绝输入。这显然可以在 时间内完成。因此，整个算法的时间复杂性为 。非确定性算法在多项式时间内接受语言CLIQUE，故CLIQUENP。159.2.3 多项式时间验证 VP=L|L*，为一有限字符集，存在一个多项式p和一个多项式时间验证算法A(X，Y)使得对任意X*，XL当且仅当存在Y*，|Y|p(|X|)且A(X，Y)=1。多项式时间可验证语言类VP可定义为：定理定理9-19-1：VP=NP。例如(哈密顿回路问题哈密顿回路问题)：一个无向图G含有哈密顿回路吗?无向图G的哈密顿回路是通过G的每个顶点恰好一次的简单回路。可用语言HAM-CYCLE 定义该问题如下：HAM-CYCLE=G|G含有哈密顿回路 169.3 NP完全问题n nP P NPNP。n n直直观观上上看看，P P类类问问题题是是确确定定性性计计算算模模型型下下的的易易解解问问题题类类，而而NPNP类类问问题题是是非非确确定定性性计计算算模模型下的易验证问题类。型下的易验证问题类。n n大多数的计算机科学家认为大多数的计算机科学家认为NPNP类中包含了不属于类中包含了不属于P P类的语言，即类的语言，即PNPPNP。n nNPNP完完全全问问题题有有一一种种令令人人惊惊奇奇的的性性质质，即即如如果果一一个个NPNP完完全全问问题题能能在在多多项项式式时时间间内内得得到到解解决，那么决，那么NPNP中的每一个问题都可以在多项式时间内求解，即中的每一个问题都可以在多项式时间内求解，即P=NPP=NP。n n目前还没有一个目前还没有一个NPNP完全问题有多项式时间算法。完全问题有多项式时间算法。179.3.1 多项式时间变换 定义：定义：语言L是NP完全的当且仅当 (1)LNP；(2)对于所有LNP有L p L。如果有一个语言L满足上述性质(2)，但不一定满足性质(1)，则称该语言是NPNP难难的。所有NP完全语言构成的语言类称为NPNP完完全语言类全语言类，记为NPCNPC。设 ，是2个语言。所谓语言 能在多项式时间内变换为语言 (简记为 p )是指存在映身f:，且f满足：(1)有一个计算f的多项式时间确定性图灵机；(2)对于所有x ，x ，当且仅当f(x)。189.3.1 多项式时间变换 定理定理9-29-2：设L是NP完全的，则 (1)LP当且仅当PNP；(2)若Lp ，且 NP，则 是NP完全的。定理的定理的(2)(2)可用来可用来证明问题的证明问题的NPNP完全完全性。但前提是：要性。但前提是：要有第一个有第一个NPNP完全问完全问题题L L。199.3.2 一些典型的NP完全问题部分NP完全问题树20 迄今为止，所有的NP完全问题都还没有多项式时间算法。对于这类问题，通常可采取以下几种解题策略。(1)只对问题的特殊实例求解(2)用动态规划法或分支限界法求解(3)用概率算法求解(4)只求近似解(5)用启发式方法求解 9.4 NP完全问题的近似算法219.4.1 近似算法的性能 若一个最优化问题的最优值为c*，求解该问题的一个近似算法求得的近似最优解相应的目标函数值为c，则将该近似算法的性能比近似算法的性能比定义为=。在通常情况下，该性能比是问题输入规模n的一个函数(n)，即 (n)。该近似算法的相对误差近似算法的相对误差定义为=。若对问题的输入规模n，有一函数(n)使得 (n)，则称(n)为该近似算法的相对误差界近似算法的相对误差界。近似算法的性能比(n)与相对误差界(n)之间显然有如下关系：(n)(n)(n)-1(n)-1。229.4.2 顶点覆盖问题的近似算法 问题描述：无向图G=(V,E)的顶点覆盖是它的顶点集V的一个子集VV，使得若(u,v)是G的一条边，则vV或uV。顶点覆盖V的大小是它所包含的顶点个数|V|。VertexSet approxVertexCoverapproxVertexCover(Graph g)cset=；e1=g.e；while(e1!=)从e1中任取一条边(u,v)；cset=csetu,v；从e1中删去与u和v相关联的所有边；return c CsetCset用来存储顶点用来存储顶点覆盖中的各顶点。初覆盖中的各顶点。初始为空，不断从边集始为空，不断从边集e1e1中选取一边中选取一边(u,v)u,v)，将边的端点加入将边的端点加入csetcset中，并将中，并将e1e1中已中已被被u u和和v v覆盖的边删去，覆盖的边删去，直至直至csetcset已覆盖所有已覆盖所有边。即边。即e1e1为空。为空。239.4.2 顶点覆盖问题的近似算法 图图(a)a)(e)(e)说明说明了算法的运行过程了算法的运行过程及结果。及结果。(e)e)表示表示算法产生的近似最算法产生的近似最优顶点覆盖优顶点覆盖csetcset，它由顶点它由顶点b,c,d,e,f,gb,c,d,e,f,g所组所组成。成。(f)f)是图是图G G的一的一个最小顶点覆盖，个最小顶点覆盖，它只含有它只含有3 3个顶点：个顶点：b,db,d和和e e。算法approxVertexCoverapproxVertexCover的性能比为2。249.4.3 旅行售货员问题近似算法 问题描述：给定一个完全无向图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就具有三角不等式性质。旅行售货员问题的一些特殊性质特殊性质：251 满足三角不等式的旅行售货员问题满足三角不等式的旅行售货员问题 对于给定的无向图G，可以利用找图图G G的最小生成树的最小生成树的算法设计找近似最优的旅行售货员回路的算法。void approxTSPapproxTSP(Graph g)(1)选择g的任一顶点r；(2)用Prim算法找出带权图g的一棵以r为根的最小生成树T；(3)前序遍历树T得到的顶点表L；(4)将r加到表L的末尾，按表L中顶点次序组成回路H，作为计算结果返回；当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的2倍。26(b)b)表示找到的最小生成表示找到的最小生成树树T T；(c)c)表示对表示对T T作前序作前序遍历的次序；遍历的次序；(d)(d)表示表示L L产产生的哈密顿回路生的哈密顿回路H H；(e)(e)是是G G的一个最小费用旅的一个最小费用旅行售货员回路。行售货员回路。272 一般一般的的旅行售货员问题旅行售货员问题 在费用函数不一定满足三角不等式的一般情况下，不存在具有常数性能比的解TSP问题的多项式时间近似算法，除非P=NPP=NP。换句话说，若PNP，则对任意常数1，不存在性能比为的解旅行售货员问题的多项式时间近似算法。289.4.4 集合覆盖问题的近似算法 问题描述：给定一个完全无向图G=(V,E)，其每一边(u,v)E有一非负整数费用c(u,v)。要找出G的最小费用哈密顿回路。集合覆盖问题的一个实例X,F由一个有限集X及X的一个子集族F组成。子集族F覆盖了有限集X。也就是说X中每一元素至少属于F中的一个子集，即X=。对于F中的一个子集CF，若C中的X的子集覆盖了X，即X=，则称C覆盖了X。集合覆盖问题就是要找出F中覆盖X的最小子集C*，使得|C*|=min|C|CF且C覆盖X 299.4.4 集合覆盖问题的近似算法集合覆盖问题举例：用用1212个黑点表示集个黑点表示集合合X X。F=S1,S2,S3,S4,SF=S1,S2,S3,S4,S5,S6,5,S6,，如图所示。如图所示。容易看出，对于这容易看出，对于这个例子，最小集合个例子，最小集合覆盖为：覆盖为：C=S3,S4,S5,C=S3,S4,S5,。309.4.4 集合覆盖问题的近似算法集合覆盖问题近似算法贪心算法 算法的循环体最多算法的循环体最多执行执行min|X|min|X|，|F|F|次。次。而循环体内的计算显然而循环体内的计算显然可在可在O(|X|F|)O(|X|F|)时间内完时间内完成。因此，算法的计算成。因此，算法的计算时间为时间为O(|X|F|min|X|O(|X|F|min|X|，|F|)|F|)。由此即知，该由此即知，该算法是一个多项式时间算法是一个多项式时间算法。算法。Set greedySetCovergreedySetCover (X,F)U=X；C=；while(U!=)选择F中使|SU|最大的子集S；U=U-S；C=CS；return C；319.4.5 子集和问题的近似算法 问题描述：设子集和问题的一个实例为S,t。其中，S=x1，x2，xn是一个正整数的集合，t是一个正整数。子集和问题判定是否存在S的一个子集S1，使得 。321 子集和问题的指数时间算法int exactSubsetSumexactSubsetSum (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(Ln)；算法以集合算法以集合S=xS=x1 1，x x2 2，x xn n 和目标值和目标值t t作为输入。算法中作为输入。算法中用到将用到将2 2个有序表个有序表L1L1和和L2L2合并成为一个新合并成为一个新的有序表的算法的有序表的算法mergeListsmergeLists(L1,L2)(L1,L2)。332 子集和问题的完全多项式时间近似格式 基于算法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来代表。342 子集和问题的完全多项式时间近似格式对有序表L修整算法List trimtrim(L,)int m=|L|；L1=L1；int last=L1；for(int i=2；i=m；i+)if(last(1-)*Li)将Li加入表L1的尾部；last=Li；return L1；子集和问题近似格式int approxSubsetSumapproxSubsetSum(S,t,)n=|S|；L0=0；for(int i=1；i=n；i+)Li=Merge-Lists(Li-1,Li-1+Si)；Li=Trim(Li,/n)；删去Li中超过t的元素；return max(Ln)；35课后作业课后作业课后作业课后作业n n习题习题 9-19-1，9-39-3，9-49-4，9-59-5，9-99-9，9-169-163637