第9章 近似算法(竞赛专用).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第9章 近似算法,1,第9章 近似算法,*,迄今为止，所有的,NP,完全问题都还没有多项式时间算法。对于这类问题，通常可采取以下几种解题策略。,(1)只对问题的特殊实例求解,(2)用动态规划法或分支限界法求解,(3)用概率算法求解,(4)只求近似解,(5)用启发式方法求解,本章主要讨论解,NP,完全问题的,近似算法,。,2,9.1 近似算法的性能,若一个最优化问题的最优值为,c*，,求解该问题的一个近似算法求得的近似最优解相应的目标函数值为,c，,则将该,近似算法的性能比,定义为,=。在通常情况下，该性能比是问题输入规模,n,的一个函数,(n)，,即,(n)。,该,近似算法的相对误差,定义为,=,。若对问题的输入规模,n,，,有一函数,(n),使得,(n),，,则称,(n),为该,近似算法的相对误差界,。近似算法的性能比,(n),与相对误差界,(n),之间显然有如下关系：,(n),(n)-1,。,3,9.2 顶点覆盖问题的近似算法,问题描述：无向图,G=(V,E),的顶点覆盖是它的顶点集,V,的一个子集,V,V，,使得若(,u,v),是,G,的一条边，则,vV,或,uV。,顶点覆盖,V,的大小是它所包含的顶点个数|,V|。,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,为空。,4,9.2 顶点覆盖问题的近似算法,图(,a)(e),说明了算法的运行过程及结果。(,e),表示算法产生的近似最优顶点覆盖,cset,，,它由顶点,b,c,d,e,f,g,所组成。(,f),是图,G,的一个最小顶点覆盖，它只含有3个顶点：,b,d,和,e。,算法,approxVertexCover,的性能比为2。,5,9.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,就具有三角不等式性质。,旅行售货员问题的一些,特殊性质6,9.3.1,具有三角不等式性质的,旅行售货员问题,对于给定的无向图,G，,可以利用找,图,G,的最小生成树,的算法设计找近似最优的旅行售货员回路的算法。,void,approxTSP,(Graph g),(1),选择,g,的任一顶点,r；,(2),用,Prim,算法找出带权图,g,的一棵以,r,为根的最小生成树,T；,(3),前序遍历树,T,得到的顶点表,L；,(4),将,r,加到表,L,的末尾，按表,L,中顶点次序组成回路,H，,作为计算结果返回；,当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的2倍。,7,9.3.1,具有三角不等式性质的旅行售货员问题举例,(,b),表示找到的最小生成树,T；,(,c),表示对,T,作前序遍历的次序；,(d),表示,L,产生的哈密顿回路,H；,(e),是,G,的一个最小费用旅行售货员回路。,8,9.3.2 一般,的,旅行售货员问题,在费用函数不一定满足三角不等式的一般情况下，不存在具有常数性能比的解,TSP,问题的多项式时间近似算法，除非,P=NP,。,换句话说，若,PNP，,则对任意常数,1，,不存在性能比为,的解旅行售货员问题的多项式时间近似算法。,9,9.4 集合覆盖问题的近似算法,问题描述：给定一个完全无向图,G=(V,E)，,其每一边(,u,v)E,有一非负整数费用,c(u,v)。要找出,G,的最小费用哈密顿回路。,集合覆盖问题的一个实例,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,10,9.4 集合覆盖问题的近似算法,集合覆盖问题举例：,用12个黑点表示集合,X。F=S1,S2,S3,S4,S5,S6,，,如图所示。容易看出，对于这个例子，最小集合覆盖为：,C=S3,S4,S5,。,11,9.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；,12,9.5 子集合问题的近似算法,问题描述：设子集和问题的一个实例为,S,t。,其中S=x,1,，x,2,，,x,n,是一个正整数的集合，,t,是一个正整数。子集和问题判定是否存在,S,的一个子集,S1，,使得 。,13,9.5.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)。,14,9.5.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,29，,则用,对,L,进行修整后得到,L1=10，12，15，20，23，29。,其中被删去的数11由10来代表，21和22由20来代表，24由23来代表。,15,9.5.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),；,16,