NP完全性理论与近似算法课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,NP,完全性理论与近似算法,2,学习要点,理解,RAM,，,RASP,和图灵机计算模型,理解非确定性图灵机的概念,理解,P,类与,NP,类语言的概念,理解,NP,完全问题的概念,理解近似算法的性能比及多项式时间近似格式的概念,通过范例学习,NP,完全问题的近似算法,（,1,）顶点覆盖问题；,（,2,）旅行售货员问题；,（,3,）集合覆盖问题；,（,4,）子集和问题。,3,1,计算模型,在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型，包括定义该计算模型中所用的基本运算。,建立计算模型的目的是为了使问题的计算复杂性分析有一个共同的客观尺度。,3,个基本计算模型：,随机存取机,RAM(Random Access Machine),；,随机存取存储程序机,RASP(Random Access Stored Program Machine),图灵机,(Turing Machine),。,这,3,个计算模型在计算能力上是等价的，但在计算速度上是不同的。,4,1.1,随机存取机,RAM,1、,RAM,的结构,5,1.1,随机存取机,RAM,2、,RAM,程序,一个,RAM,程序定义了从输入带到输出带的一个映射。可以对,这种映射关系作2种不同的解释。,解释一：把,RAM,程序看成是计算一个函数,若一个,RAM,程序,P,总是从输入带前,n,个方格中读入,n,个整数,x,1,，x,2,，,，x,n,，,并且在输出带的第一个方格上输出一个整数,y,后停机，那么就说程序,P,计算了函数,f(x,1,，x,2,，,，x,n,)=y,解释二：把,RAM,程序当作一个语言接受器。,将字符串,S=a,1,a,2,a,n,放在输入带上。在输入带的第一个方,格中放入符号,a,1,，,第二个方格中放入符号,a,2,，,，,第,n,个方格中,放入符号,a,n,。,然后在第,n+1,个方格中放入0，作为输入串的结束标,志符。如果一个,RAM,程序,P,读了字符串,S,及结束标志符0后，在输出,带的第一格输出一个1并停机，就说程序,P,接受字符串,S。,6,1.1,随机存取机,RAM,3、,RAM,程序的耗费标准,标准一：均匀耗费标准,在均匀耗费标准下，每条,RAM,指令需要一个单位时间；每,个寄存器占用一个单位空间。以后除特别注明，,RAM,程序的复杂,性将按照均匀耗费标准衡量。,标准二：对数耗费标准,对数耗费标准是基于这样的假定，即执行一条指令的耗费,与以二进制表示的指令的操作数长度成比例。在,RAM,计算模型下，,假定一个寄存器可存放一个任意大小的整数。因此若设,l(i),是整,数,i,所占的二进制位数，则,7,1.2,随机存取存储程序机,RASP,1、,RASP,的结构,RASP,的整体结构类似于,RAM，,所不同的是,RASP,的程序是存,储在寄存器中的。每条,RASP,指令占据2个连续的寄存器。第一个,寄存器存放操作码的编码，第二个寄存器存放地址。,RASP,指令用,整数进行编码。,2、,RASP,程序的复杂性,不管是在均匀耗费标准下，还是在对数耗费标准下，,RAM,程序和,RASP,程序的复杂性只差一个常数因子。在一个计算模型下,T(n),时间内完成的输入-输出映射可在另一个计算模型下模拟，,并在,kT(n),时间内完成。其中,k,是一个常数因子。空间复杂性的情,况也是类似的。,8,1.3,图灵机,9,1.3,图灵机,根据有限状态控制器的当前状态及每个读写头读到的带符号，图灵机的一个计算步可实现下面3个操作之一或全部。,(1)改变有限状态控制器中的状态。,(2)清除当前读写头下的方格中原有带符号并写上新的带符号。,(3)独立地将任何一个或所有读写头，向左移动一个方格(,L),或向右移动一个方格(,R),或停在当前单元不动(,S)。,k,带图灵机可形式化地描述为一个7元组(,Q，T，I，b，q,0,，q,f,)，,其中:,(1),Q,是有限个状态的集合。 (2),T,是有限个带符号的集合。,(3),I,是输入符号的集合，,IT。(4)b,是唯一的空白符，,bT-I。,(5)q,0,是初始状态。 (6),q,f,是终止(或接受)状态。,(7),是移动函数。它是从,QT,k,的某一子集映射到,Q (TL，R，S),k,的函数。,10,1.3,图灵机,图灵机,M,的时间复杂性,T(n),是它处理所有长度为,n,的输入所需的最大计算步数。如果对某个长度为,n,的输入，图灵机不停机，,T(n),对这个,n,值无定义。,图灵机的空间复杂性,S(n),是它处理所有长度为,n,的输入时，在,k,条带上所使用过的方格数的总和。如果某个读写头无限地向右移动而不停机，,S(n),也无定义。,与,RAM,模型类似，图灵机既可作为语言接受器，也可作为计算函数的装置。,11,2P,类与,NP,类问题,一般地说，将可由多项式时间算法求解的问题看作是易处理的问题，而将需要超多项式时间才能求解的问题看作是难处理的问题。,有许多问题，从表面上看似乎并不比排序或图的搜索等问题更困难，然而至今人们还没有找到解决这些问题的多项式时间算法，也没有人能够证明这些问题需要超多项式时间下界。,在图灵机计算模型下，这类问题的计算复杂性至今未知。,为了研究这类问题的计算复杂性，人们提出了另一个能力更强的计算模型，即非确定性图灵机计算模型，简记为,NDTM(Nondeterministic Turing Machine),。,在非确定性图灵机计算模型下，许多问题可以在多项式时间内求解。,12,2.1,非确定性图灵机,非确定性图灵机,（,NDTM,）,：一个,k,带的非确定性图灵机,M,是一个7元组：(,Q，T，I，b，q,0,，q,f,)。,与确定性图灵机不同的是非确定性图灵机允许移动函数,具有不确定性,，即对于,QT,k,中的每一个值(,q;x,1,x,2,x,k,)，,当它属于,的定义域时，,Q(TL，R，S),k,中有唯一的一个,子集,(q;x,1,x,2,x,k,),与之对应。可以在,(q;x,1,x,2,x,k,),中随意选定一个值作为它的函数值。,在图灵机计算模型中，移动函数,是单值的,，即对于,QT,k,中的每一个值，当它属于,的定义域时，,Q(TL，R，S),k,中只有唯一的值与之对应，称这种图灵机为,确定性图灵机,，简记为,DTM,(Deterministic Turing Machine)。,13,2.2,P,类与,NP,类语言,P,类和,NP,类语言的定义：,P=L|L,是一个能在,多项式时间内,被一台,DTM,所接受的语言,NP=L|L,是一个能在,多项式时间,内被一台,NDTM,所接受的语言,由于一台确定性图灵机可看作是非确定性图灵机的特例，所以可在多项式时间内被确定性图灵机接受的语言也可在多项式时间内被非确定性图灵机接受。故,P NP,。,14,2.2,P,类与,NP,类语言,NP,类语言举例,无向图的团问题,。,该问题的输入是一个有,n,个顶点的无向图,G=(V，E),和一个整数,k。,要求判定图,G,是否包含一个,k,顶点的,完全子图(团),，即判定是否存在,V,V，|V,|=k，,且对于所有的,u，vV,，,有(,u，v)E。,若用邻接矩阵表示图,G，,用二进制串表示整数,k，,则团问题的一个实例可以用长度为 的二进位串表示。因此，团问题可表示为语言：,CLIQUE=w#v|w，v0，1*，,以,w,为邻接矩阵的图,G,有一个,k,顶点的团，其中,v,是,k,的二进制表示。,15,2.2,P,类与,NP,类语言,接受该语言,CLIQUE,的,非确定性算法,：用非确定性选择指令选出包含,k,个顶点的候选顶点子集,V，,然后确定性地检查该子集是否是团问题的一个解。算法分为3个阶段：,算法的第一阶段将输入串,w#v,分解，并计算出,n= ，,以及用,v,表示的整数,k。,若输入不具有形式,w#v,或|,w|,不是一个平方数就拒绝该输入。显而易见，第一阶段可 在时间内完成。,在算法的第二阶段中，非确定性地选择,V,的一个,k,元子集,V,V。,算法的第三阶段是确定性地检查,V,的团性质。若,V,是一个团则接受输入，否则拒绝输入。这显然可以在 时间内完成。因此，整个算法的时间复杂性为 。,非确定性算法在多项式时间内接受语言,CLIQUE，,故,CLIQUENP。,16,2.3,多项式时间验证,VP=L|L*，,为一有限字符集，存在一个多项式,p,和一个多项式时间验证算法,A(X，Y),使得对任意,X*，XL,当且仅当存在,Y*，|Y|p(|X|),且,A(X，Y)=1。,多项式时间可验证语言类,VP,可定义为：,定理,15-1,：,VP=NP。,例如(,哈密顿回路问题,)：一个无向图,G,含有哈密顿回路吗?,无向图,G,的哈密顿回路是通过,G,的每个顶点恰好一次的简单回路。可用语言,HAM-CYCLE,定义该问题如下：,HAM-CYCLE=G|G,含有哈密顿回路,17,3NP,完全问题,PNP,。,直观上看，,P,类问题是确定性计算模型下的易解问题类，而,NP,类问题是非确定性计算模型下的易验证问题类。,大多数的计算机科学家认为,NP,类中包含了不属于,P,类的语言，即,PNP,。,NP,完全问题有一种令人惊奇的性质，即如果一个,NP,完全问题能在多项式时间内得到解决，那么,NP,中的每一个问题都可以在多项式时间内求解，即,P=NP,。,目前还没有一个,NP,完全问题有多项式时间算法。,18,3.1,多项式时间变换,定义：,语言,L,是,NP,完全的当且仅当,(1),LNP；,(2),对于所有,L,NP,有,L,p,L。,如果有一个语言,L,满足上述性质(2)，但不一定满足性质(1)，则称该语言是,NP,难,的。所有,NP,完全语言构成的语言类称为,NP,完全语言类,，记为,NPC,。,设 ， 是2个语言。所谓语言 能在多项式时间内变换为语言 (简记为 ,p,),是指存在映身,f: ，,且,f,满足：,(1)有一个计算,f,的多项式时间确定性图灵机；,(2)对于所有,x ，x ，,当且仅当,f(x) 。,19,3.1,多项式时间变换,定理,15-2,：设,L,是,NP,完全的，则,(1)LP,当且仅当,PNP；,(2),若,L,p,，,且 ,NP，,则 是,NP,完全的。,定理的(2)可用来证明问题的,NP,完全性。但前提是：要有第一个,NP,完全问题,L。,20,3.2,一些典型的,NP,完全问题,部分,NP,完全问题树,21,迄今为止，所有的,NP,完全问题都还没有多项式时间算法。,对于这类问题，通常可采取以下几种解题策略。,(1)只对问题的特殊实例求解,(2)用动态规划法或分支限界法求解,(3)用概率算法求解,(4)只求近似解,(5)用启发式方法求解,本节主要讨论解,NP,完全问题的,近似算法,4 NP,完全问题的近似算法,22,学习要点,:,理解近似算法的性能比的概念,理解多项式时间近似格式的概念,通过范例学习,NP,完全问题的近似算法,23,概述,近似算法设计思想,放弃求解最优解，用近似最优解代替最优解,，以此换取：,算法设计上的简化,时间复杂性的降低,近似算法是,可行的,：,问题的输入数据是近似的；,问题的解允许有一定程度的误差；,近似算法可在很短的时间内得到问题的近似解。,24,衡量近似算法性能的标准：,时间复杂性,：必须是多项式阶的,基本目标,解的近似程度,：,重要目标,若一个最优化问题的最优值为,c*,，求解该问题的一个近似算法求得的近似最优值为,c,，则将该近似算法的,近似比,定义为,=,在通常情况下，该性能比是问题输入规模,n,的一个函数,(n),，即,(n), ,1,；且,越大，近似解越差！,最小化问题,cc*,最大化问题，,c*c,4.1,近似算法的性能,25,近似算法的,相对误差,定义为：,=,表示一个近似最优解与最优解相差的程度。,若问题的输入规模为,n,，存在一个函数,(n),，使得：,(n),(n),称为近似算法的,相对误差界,。且有：,(n),(n)-1,4.1,近似算法的性能,26,4.2,顶点覆盖问题的近似算法,问题描述：,无向图,G=(V,E),的顶点覆盖是它的顶点集,V,的一个子集,V,V，,使得若(,u,v),是,G,的一条边，则,vV,或,uV,。,顶点覆盖,V,的大小是它所包含的顶点个数|,V,|。,近似算法思想：,初始时边集,E,=E,，顶点集,V,=,，每次从边集,E,中任取一条边,(u, v),，把顶点,u,和,v,加入到顶点集,V,中，再把与,u,和,v,顶点,相邻接的所有边,从边集,E,中删除，直到边集,E,为空。,27,4.2,顶点覆盖问题的近似算法,VertexSet approxVertexCover ( Graph g ), cset=；,e1=g.e；,while (e1 != ) ,从,e1,中任取一条边(,u,v)；,cset=csetu,v；,从,e1,中删去与,u,和,v,相关联的所有边；,return c,Cset,用来存储顶点覆盖中的各顶点。初始为空，不断从边集,e1,中选取一边(,u,v)，,将边的端点加入,cset,中，并将,e1,中已被,u,和,v,覆盖的边删去，直至,cset,已覆盖所有边。即,e1,为空。,算法的时间复杂性：,O(n+e),28,求解过程：,图,(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,29,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,就具有三角不等式性质。,旅行售货员问题的一些,特殊性质,：,30,1,满足三角不等式的旅行售货员问题,对于给定的无向图,G，,可以利用找,图,G,的最小生成树,的算法设计找近似最优的旅行售货员回路的算法,:,首先生成图,G,的最小生成树,T,；,然后，对,T,进行深度优先遍历，,得到的遍历序列就是近似最优的旅行售货员回路。,31,1,满足三角不等式的旅行售货员问题,void approxTSP (Graph G),(1),选择,G,的任一顶点,r；,(2),用,Prim,算法找出带权图,G,的一棵以,r,为根的最小生成树,T；,(3),前序遍历树,T,得到的顶点表,L；,(4),将,r,加到表,L,的末尾，按表,L,中顶点次序组成回路,H，,作为计算结果返回；,当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的2倍。,算法的时间复杂性：,O(n,2,),32,(,b),表示找到的最小生成树,T；,(,c),表示对,T,作前序遍历的次序；,(d),表示,L,产生的哈密顿回路,H；,(e),是,G,的一个最小费用旅行售货员回路。,示例求解过程：,线路：,a,b,c,b,h,b,a,d,e,f,e,g,e,d,a,L=(a, b, c, h, d, e, f, g),H=(abchde,fga),H*=(abchf,geda),33,2 一般,的,旅行售货员问题,在费用函数不一定满足三角不等式的一般情况下，,不存在,具有常数性能比的解,TSP,问题的,多项式时间近似算法,，除非,P=NP。,换句话说，若,PNP，,则对任意常数,1，,不存在性能比为,的解旅行售货员问题的多项式时间近似算法。,34,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,35,4.4,集合覆盖问题的近似算法,集合覆盖问题举例：,用12个黑点表示集合,X。F=S1,S2,S3,S4,S5,S6,，,如图所示。容易看出，对于这个例子，最小集合覆盖为：,C=S3,S4,S5,。,36,4.4,集合覆盖问题的近似算法,集合覆盖问题近似算法贪心算法,算法的循环体最多执行,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 C；,37,4.5,子集和问题的近似算法,问题描述,：设子集和问题的一个实例为,S,t。,其中，,S=x,1,，x,2,，,，x,n,是一个正整数的集合，,t,是一个正整数。子集和问题判定是否存在,S,的一个子集,S1，,使得 。,38,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(Ln),；,算法以集合,S=x,1,，x,2,，,，x,n,和目标值,t,作为输入。算法中用到将2个有序表,L1,和,L2,合并成为一个新的有序表的算法,mergeLists,(L1,L2)。,39,2 子集和问题的完全多项式时间近似格式,基于算法,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,215，,则用,对,L,进行修整后得到,L1=10，12，15，20，23，215。,其中被删去的数11由10来代表，21和22由20来代表，24由23来代表。,40,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,的尾部；,last=Li,；,return L1,；,子集和问题近似格式,int approxSubsetSum(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),；,41,设：,S=,，,t=308,，,i=1, 2, ., n,。,由算法确定的修整参数,是,/4=0.05,。,初始时，,L0=,。计算,Li,的,3,阶段结果：,L1=,L1=,L1=,L2=,L2=,L2=,L3=,L3=,L3=,L4=,L4=,L4=,算法最后返回,z=302,最为近似解答。容易看出该例的最优解为,104+102+101=307,，误差,2%,。,示例求解：,42,本章小结,近似算法,放弃求最优解，用近似解代替最优解，以换取算法设计上的简化和时间复杂性的降低。,近似算法通常采用两个标准来衡量性能：,算法的时间复杂性,解的近似程度,近似比,相对误差,相对误差界,(n),THE END,