第十五讲NP完全性理论与近似算法

1内容提要理解RAM，RASP和图灵机计算模型理解非确定性图灵机的概念理解P类与NP类语言的概念理解NP完全问题的概念理解近似算法的性能比及多项式时间近似格式的概念通过范例学习NP完全问题的近似算法（1）顶点覆盖问题（2）旅行售货员问题（3）集合覆盖问题（4）子集和问题。第十五讲NP完全性理论与近似算法215.1计算模型在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型，包括定义该计算模型中所用的基本运算。目的:为了使问题的计算复杂性分析有一个共同的客观尺度。3个基本计算模型：随机存取机RAM(RandomAccessMachine)；随机存取存储程序机RASP(RandomAccessStoredProgramMachine)图灵机(TuringMachine)。这3个计算模型在计算能力上是等价的，但在计算速度上是不同的。315.1.1随机存取机RAM1、RAM的结构415.1.1随机存取机RAM2、RAM程序一个RAM程序定义了从输入带到输出带的一个映射。可以对这种映射关系作2种不同的解释。解释一：把RAM程序看成是计算一个函数若一个RAM程序P总是从输入带前n个方格中读入n个整数x1，x2，…，xn，并且在输出带的第一个方格上输出一个整数y后停机，那么就说程序P计算了函数f(x1，x2，…，xn)=y解释二：把RAM程序当作一个语言接受器。将字符串S=a1a2…an放在输入带上。在输入带的第一个方格中放入符号a1，第二个方格中放入符号a2，…，第n个方格中放入符号an。然后在第n+1个方格中放入0，作为输入串的结束标志符。如果一个RAM程序P读了字符串S及结束标志符0后，在输出带的第一格输出一个1并停机，就说程序P接受字符串S。515.1.1随机存取机RAM3、RAM程序的耗费标准标准一：均匀耗费标准在均匀耗费标准下，每条RAM指令需要一个单位时间；每个寄存器占用一个单位空间。以后除特别注明，RAM程序的复杂性将按照均匀耗费标准衡量。标准二：对数耗费标准对数耗费标准是基于这样的假定，即执行一条指令的耗费与以二进制表示的指令的操作数长度成比例。在RAM计算模型下，假定一个寄存器可存放一个任意大小的整数。因此若设l(i)是整数i所占的二进制位数，则615.1.2随机存取存储程序机RASP1、RASP的结构RASP的整体结构类似于RAM，所不同的是RASP的程序是存储在寄存器中的。每条RASP指令占据2个连续的寄存器。第一个寄存器存放操作码的编码，第二个寄存器存放地址。RASP指令用整数进行编码。2、RASP程序的复杂性不管是在均匀耗费标准下，还是在对数耗费标准下，RAM程序和RASP程序的复杂性只差一个常数因子。在一个计算模型下T(n)时间内完成的输入-输出映射可在另一个计算模型下模拟，并在kT(n)时间内完成。其中k是一个常数因子。空间复杂性的情况也是类似的。715.1.3图灵机815.1.3图灵机根据有限状态控制器的当前状态及每个读写头读到的带符号，图灵机的一个计算步可实现下面3个操作之一或全部。(1)改变有限状态控制器中的状态。(2)清除当前读写头下的方格中原有带符号并写上新的带符号。(3)独立地将任何一个或所有读写头，向左移动一个方格(L)或向右移动一个方格(R)或停在当前单元不动(S)。k带图灵机可形式化地描述为一个7元组(Q，T，I，δ，b，q0，qf)，其中:(1)Q是有限个状态的集合。(2)T是有限个带符号的集合。(3)I是输入符号的集合，IT。(4)b是唯一的空白符，b∈T-I。(5)q0是初始状态。(6)qf是终止(或接受)状态。(7)δ是移动函数。它是从QTk的某一子集映射到Q(T{L，R，S})k的函数。915.1.3图灵机图灵机M的时间复杂性T(n)是它处理所有长度为n的输入所需的最大计算步数。如果对某个长度为n的输入，图灵机不停机，T(n)对这个n值无定义。图灵机的空间复杂性S(n)是它处理所有长度为n的输入时，在k条带上所使用过的方格数的总和。如果某个读写头无限地向右移动而不停机，S(n)也无定义。与RAM模型类似，图灵机既可作为语言接受器，也可作为计算函数的装置。1015.2P类与NP类问题可由多项式时间算法求解的问题易处理的问题，需要超多项式时间才能求解的问题难处理的问题。有许多问题，从表面上看似乎并不比排序或图的搜索等问题更困难，然而至今人们还没有找到解决这些问题的多项式时间算法，也没有人能够证明这些问题需要超多项式时间下界。在图灵机计算模型下，这类问题的计算复杂性至今未知。为了研究这类问题的计算复杂性，人们提出了另一个能力更强的计算模型，即非确定性图灵机计算模型，简记为NDTM(NondeterministicTuringMachine)。在非确定性图灵机计算模型下，许多问题可以在多项式时间内求解。1115.2.1非确定性图灵机非确定性图灵机（NDTM）：一个k带的非确定性图灵机M是一个7元组：(Q，T，I，δ，b，q0，qf)。与确定性图灵机不同的是非确定性图灵机允许移动函数δ具有不确定性，即对于QTk中的每一个值(q;x1,x2,…,xk)，当它属于δ的定义域时，Q(T{L，R，S})k中有唯一的一个子集δ(q;x1,x2,…,xk)与之对应。可以在δ(q;x1,x2,…,xk)中随意选定一个值作为它的函数值。在图灵机计算模型中，移动函数δ是单值的，即对于QTk中的每一个值，当它属于δ的定义域时，Q(T{L，R，S})k中只有唯一的值与之对应，称这种图灵机为确定性图灵机，简记为DTM(DeterministicTuringMachine)。1215.2.2P类与NP类语言P类和NP类语言的定义：P={L|L是一个能在多项式时间内被一台DTM所接受的语言}NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言}由于一台确定性图灵机可看作是非确定性图灵机的特例，所以可在多项式时间内被确定性图灵机接受的语言也可在多项式时间内被非确定性图灵机接受。故PNP。1315.2.2P类与NP类语言NP类语言举例——无向图的团问题。该问题的输入是一个有n个顶点的无向图G=(V，E)和一个整数k。要求判定图G是否包含一个k顶点的完全子图(团)，即判定是否存在V’V，|V’|=k，且对于所有的u，v∈V’，有(u，v)∈E。若用邻接矩阵表示图G，用二进制串表示整数k，则团问题的一个实例可以用长度为的二进位串表示。因此，团问题可表示为语言：CLIQUE={w#v|w，v∈{0，1}*，以w为邻接矩阵的图G有一个k顶点的团，其中v是k的二进制表示。}1415.2.2P类与NP类语言接受该语言CLIQUE的非确定性算法：用非确定性选择指令选出包含k个顶点的候选顶点子集V，然后确定性地检查该子集是否是团问题的一个解。算法分为3个阶段：算法的第一阶段将输入串w#v分解，并计算出n=，以及用v表示的整数k。若输入不具有形式w#v或|w|不是一个平方数就拒绝该输入。显而易见，第一阶段可在时间内完成。在算法的第二阶段中，非确定性地选择V的一个k元子集V’V。算法的第三阶段是确定性地检查V’的团性质。若V’是一个团则接受输入，否则拒绝输入。这显然可以在时间内完成。因此，整个算法的时间复杂性为。非确定性算法在多项式时间内接受语言CLIQUE，故CLIQUE∈NP。1515.2.3多项式时间验证VP={L|L∈∑*，∑为一有限字符集，存在一个多项式p和一个多项式时间验证算法A(X，Y)使得对任意X∈∑*，X∈L当且仅当存在Y∈∑*，|Y|≤p(|X|)且A(X，Y)=1}。多项式时间可验证语言类VP可定义为：定理15-1：VP=NP。例如(哈密顿回路问题)：一个无向图G含有哈密顿回路吗?无向图G的哈密顿回路是通过G的每个顶点恰好一次的简单回路。可用语言HAM-CYCLE定义该问题如下：HAM-CYCLE={G|G含有哈密顿回路}1615.3NP完全问题PNP。直观上看，P类问题是确定性计算模型下的易解问题类，而NP类问题是非确定性计算模型下的易验证问题类。大多数的计算机科学家认为NP类中包含了不属于P类的语言，即P≠NP。NP完全问题有一种令人惊奇的性质，即如果一个NP完全问题能在多项式时间内得到解决，那么NP中的每一个问题都可以在多项式时间内求解，即P=NP。目前还没有一个NP完全问题有多项式时间算法。1715.3.1多项式时间变换定义：语言L是NP完全的当且仅当(1)L∈NP；(2)对于所有L’∈NP有L’∝pL。如果有一个语言L满足上述性质(2)，但不一定满足性质(1)，则称该语言是NP难的。所有NP完全语言构成的语言类称为NP完全语言类，记为NPC。设，是2个语言。所谓语言能在多项式时间内变换为语言(简记为∝p)是指存在映身f:，且f满足：(1)有一个计算f的多项式时间确定性图灵机；(2)对于所有x∈，x∈，当且仅当f(x)∈。1815.3.1多项式时间变换定理15-2：设L是NP完全的，则(1)L∈P当且仅当P＝NP；(2)若L∝p，且∈NP，则是NP完全的。定理的(2)可用来证明问题的NP完全性。但前提是：要有第一个NP完全问题L。1915.3.2一些典型的NP完全问题部分NP完全问题树20迄今为止，所有的NP完全问题都还没有多项式时间算法。对于这类问题，通常可采取以下几种解题策略。(1)只对问题的特殊实例求解(2)用动态规划法或分支限界法求解(3)用概率算法求解(4)只求近似解(5)用启发式方法求解本节主要讨论解NP完全问题的近似算法15.4NP完全问题的近似算法21学习要点:理解近似算法的性能比的概念理解多项式时间近似格式的概念通过范例学习NP完全问题的近似算法22概述近似算法 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 思想放弃求解最优解，用近似最优解代替最优解，以此换取：算法设计上的简化时间复杂性的降低近似算法是可行的：问题的输入数据是近似的；问题的解允许有一定程度的误差；近似算法可在很短的时间内得到问题的近似解。23衡量近似算法性能的标准：时间复杂性：必须是多项式阶的——基本目标解的近似程度：——重要目标若一个最优化问题的最优值为c*，求解该问题的一个近似算法求得的近似最优值为c，则将该近似算法的近似比定义为=在通常情况下，该性能比是问题输入规模n的一个函数ρ(n)，即≤ρ(n)≥1；且越大，近似解越差！最小化问题c≥c*最大化问题，c*≥c15.4.1近似算法的性能24近似算法的相对误差λ定义为：λ=λ表示一个近似最优解与最优解相差的程度。若问题的输入规模为n，存在一个函数ε(n)，使得：≤ε(n)ε(n)称为近似算法的相对误差界。且有：ε(n)≤ρ(n)-115.4.1近似算法的性能2515.4.2顶点覆盖问题的近似算法问题描述：无向图G=(V,E)的顶点覆盖是它的顶点集V的一个子集V’V，使得若(u,v)是G的一条边，则v∈V’或u∈V’。顶点覆盖V’的大小是它所包含的顶点个数|V’|。近似算法思想：初始时边集E’=E，顶点集V’={}，每次从边集E’中任取一条边(u,v)，把顶点u和v加入到顶点集V’中，再把与u和v顶点相邻接的所有边从边集E’中删除，直到边集E’为空。2615.4.2顶点覆盖问题的近似算法VertexSetapproxVertexCover(Graphg){cset=；e1=g.e；while(e1!=){从e1中任取一条边(u,v)；cset=cset∪{u,v}；从e1中删去与u和v相关联的所有边；}returnc}Cset用来存储顶点覆盖中的各顶点。初始为空，不断从边集e1中选取一边(u,v)，将边的端点加入cset中，并将e1中已被u和v覆盖的边删去，直至cset已覆盖所有边。即e1为空。算法的时间复杂性：O(n+e)27求解过程：图(a)～(e)说明了算法的运行过程及结果。(e)表示算法产生的近似最优顶点覆盖cset，它由顶点b,c,d,e,f,g所组成。(f)是图G的一个最小顶点覆盖，它只含有3个顶点：b,d和e。算法approxVertexCover的性能比为2。A={(b,c),(e,f),(d,g)}A={(b,c)}A={(b,c),(e,f)}初始：E’=E={(a,b),(b,c),(c,d),(c,e),(d,e),(d,f),(d,g),(e,f)}V’={b,c}V’={b,c,e,f}V’={b,c,e,f,d,g}2815.4.3旅行售货员问题近似算法问题描述：给定一个完全无向图G=(V,E)，其每一边(u,v)∈E有一非负整数费用c(u,v)。要找出G的最小费用哈密顿回路。比如，费用函数c往往具有三角不等式性质，即对任意的3个顶点u,v,w∈V，有：c(u,w)≤c(u,v)+c(v,w)。当图G中的顶点就是平面上的点，任意2顶点间的费用就是这2点间的欧氏距离时，费用函数c就具有三角不等式性质。旅行售货员问题的一些特殊性质：291满足三角不等式的旅行售货员问题对于给定的无向图G，可以利用找图G的最小生成树的算法设计找近似最优的旅行售货员回路的算法:首先生成图G的最小生成树T；然后，对T进行深度优先遍历，得到的遍历序列就是近似最优的旅行售货员回路。301满足三角不等式的旅行售货员问题voidapproxTSP(GraphG){(1)选择G的任一顶点r；(2)用Prim算法找出带权图G的一棵以r为根的最小生成树T；(3)前序遍历树T得到的顶点表L；(4)将r加到表L的末尾，按表L中顶点次序组成回路H，作为计算结果返回；}当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的2倍。算法的时间复杂性：O(n2)31(b)表示找到的最小生成树T；(c)表示对T作前序遍历的次序；(d)表示L产生的哈密顿回路H；(e)是G的一个最小费用旅行售货员回路。示例求解过程：线路：a→b→c→b→h→b→a→d→e→f→e→g→e→d→aL=(a,b,c,h,d,e,f,g)H=(a→b→c→h→d→e→f→g→a)H*=(a→b→c→h→f→g→e→d→a)322一般的旅行售货员问题在费用函数不一定满足三角不等式的一般情况下，不存在具有常数性能比的解TSP问题的多项式时间近似算法，除非P=NP。换句话说，若P≠NP，则对任意常数ρ>1，不存在性能比为ρ的解旅行售货员问题的多项式时间近似算法。3315.4.4集合覆盖问题的近似算法问题描述：集合覆盖问题的一个实例〈X,F〉由一个有限集X及X的一个子集族F组成。子集族F覆盖了有限集X。也就是说X中每一元素至少属于F中的一个子集，即X=。对于F中的一个子集CF，若C中的X的子集覆盖了X，即X=，则称C覆盖了X。集合覆盖问题就是要找出F中覆盖X的最小子集C*，使得|C*|=min{|C||CF且C覆盖X}3415.4.4集合覆盖问题的近似算法集合覆盖问题举例：用12个黑点表示集合X。F={S1,S2,S3,S4,S5,S6,}，如图所示。容易看出，对于这个例子，最小集合覆盖为：C={S3,S4,S5,}。3515.4.4集合覆盖问题的近似算法集合覆盖问题近似算法——贪心算法算法的循环体最多执行min{|X|，|F|}次。而循环体内的计算显然可在O(|X||F|)时间内完成。因此，算法的计算时间为O(|X||F|min{|X|，|F|})。由此即知，该算法是一个多项式时间算法。SetgreedySetCover(X,F){U=X；C=；while(U!=){选择F中使|S∩U|最大的子集S；U=U-S；C=C∪{S}；}returnC；}3615.4.5子集和问题的近似算法问题描述：设子集和问题的一个实例为〈S,t〉。其中，S={x1，x2，…，xn}是一个正整数的集合，t是一个正整数。子集和问题判定是否存在S的一个子集S1，使得。371子集和问题的指数时间算法intexactSubsetSum(S,t){intn=|S|；L[0]={0}；for(inti=1；i<=n；i++){L[i]=mergeLists(L[i-1],L[i-1]+S[i])；删去L[i]中超过t的元素；}returnmax(L[n])；}算法以集合S={x1，x2，…，xn}和目标值t作为输入。算法中用到将2个有序表L1和L2合并成为一个新的有序表的算法mergeLists(L1,L2)。382子集和问题的完全多项式时间近似格式基于算法exactSubsetSum，通过对表L[i]作适当的修整建立一个子集和问题的完全多项式时间近似格式。在对表L[i]进行修整时，用到一个修整参数δ，0＜δ＜1。用参数δ修整一个表L是指从L中删去尽可能多的元素，使得每一个从L中删去的元素y，都有一个修整后的表L1中的元素z满足(1-δ)y≤z≤y。可以将z看作是被删去元素y在修整后的新表L1中的代表。举例：若δ=0.1，且L=〈10,11,12,15,20,21,22,23,24,215〉，则用δ对L进行修整后得到L1=〈10，12，15，20，23，215〉。其中被删去的数11由10来代表，21和22由20来代表，24由23来代表。392子集和问题的完全多项式时间近似格式对有序表L修整算法Listtrim(L,δ){intm=|L|；L1=〈L[1]〉；intlast=L[1]；for(inti=2；i<=m；i++){if(last<(1-δ)*L[i]){将L[i]加入表L1的尾部；last=L[i]；}returnL1；}子集和问题近似格式intapproxSubsetSum(S,t,ε){n=|S|；L[0]=〈0〉；for(inti=1；i<=n；i++){L[i]=Merge-Lists(L[i-1],L[i-1]+S[i])；L[i]=Trim(L[i],ε/n)；删去L[i]中超过t的元素；}returnmax(L[n])；}40设：S=<104,102,201,101>，t=308，i=1,2,...,n。由算法确定的修整参数δ是ε/4=0.05。初始时，L[0]=<0>。计算L[i]的3阶段结果：L[1]=<0,104>L[1]=<0,104>L[1]=<0,104>L[2]=<0,102,104,206>L[2]=<0,102,206>L[2]=<0,102,206>L[3]=<0,102,201,206,303,407>L[3]=<0,102,201,303,407>L[3]=<0,102,201,303>L[4]=<0,101,102,201,203,302,303,404>L[4]=<0,101,201,302,404>L[4]=<0,101,201,302>算法最后返回z=302最为近似解答。容易看出该例的最优解为104+102+101=307，误差≤2%。示例求解：41本章小结近似算法放弃求最优解，用近似解代替最优解，以换取算法设计上的简化和时间复杂性的降低。近似算法通常采用两个标准来衡量性能：算法的时间复杂性解的近似程度近似比相对误差λ相对误差界ε(n)42作业35.1-4,35.2-3