近似算法概述课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,近似算法,Approximation Algorithms,1近似算法Approximation Algorithms,2,近似算法,迄今为止，所有的,NP,完全问题都还没有多项式时间算法。对于这类问题，通常可采取以下几种解题策略。,(1)只对问题的特殊实例求解,(2)用动态规划法或分支限界法求解,(3)用概率算法求解,(4)只求近似解,(5)用启发式方法求解,本章主要讨论解,NP,完全问题的,近似算法,。,2近似算法 迄今为止，所有的NP完全问题都还没有多项式时间,主要内容,近似算法的性能定义,顶点覆盖问题,旅行售货商,(TSP),问题,子集和问题,近似方案：,(,完全,),多项式近似方案,3,主要内容近似算法的性能定义3,4,1 近似算法的性能,若一个最优化问题的最优值为,c*，,求解该问题的一个近似算法求得的近似最优解相应的目标函数值为,c，,则将该,近似算法的性能比,定义为,=。在通常情况下，该性能比是问题输入规模,n,的一个函数,(n)。,该,近似算法的相对误差,定义为,=。若对问题的输入规模,n，,有一函数,(n),使得 ,(n)，,则称,(n),为该,近似算法的相对误差界,。,近似算法的性能比,(n),与相对误差界,(n),之间有如下关系：,(n)(n)-1,。,41 近似算法的性能若一个最优化问题的最优值为c*，求解该问,5,2 顶点覆盖问题的近似算法,问题描述：,无向图,G=(V,E),的顶点覆盖是它的顶点集,V,的一个子集,V,V，,使得若(,u,v),是,G,的一条边，则,vV,或,uV,。,顶点覆盖,V,的大小是它所包含的顶点个数|,V,|。,顶点覆盖问题：,找最小顶点覆盖。,VertexSet ApproxVertexCover(Graph G),Cset=,；,E1=E；,while(E1!=,),从,E1,中任取一条边,e=,(,u,v)；,Cset=Csetu,v；,从,E1,中删去与,u,和,v,相关联的所有边；,return Cset,Cset,用来存储顶点覆盖中的各顶点。初始为空，不断从边集,E1,中选取一边(,u,v)，,将边的端点加入,Cset,中，并将,E1,中已被,u,和,v,覆盖的边删去，直至,Cset,已覆盖所有边。即,E1,为空。,52 顶点覆盖问题的近似算法问题描述：无向图G=(V,E),6,2,顶点覆盖问题的近似算法,图(,a)(e),说明了算法的运行过程及结果。(,e),表示算法产生的近似最优顶点覆盖,C,set,，,它由顶点,b,c,d,e,f,g,所组成。,(,f),是图,G,的一个最小顶点覆盖，它只含有3个顶点：,b,d,和,e。,算法,approxVertexCover,的性能比为2。（,c=6,，,c*=3,）,62 顶点覆盖问题的近似算法图(a)(e)说明了算法的运行,7,近似比,:2-Approximation,Theorem.,Algorithm,ApproxVertexCover,is a 2-approximation algorithm.,Pf.,Let,A,denote the set of edges that were picked by,Algorithm,ApproxVertexCover.Let,C,*,be an optimal vertex cover.Then,C,*,must include at least one endpoint of each edge in,A,.,Since no two edges in,A,share an endpoint,no two edges in,A,are covered by the same vertex from,C,*.Hence we have the lower bound,C,*,|A|.,On the other hand,the algorithm,picks an edge for which neither of its endpoints is already in,C.,Then,|C|=2|A|,Hence,|,C,|=2|,A,|2|,C,*|.,7近似比:2-Approximation Theorem.,8,Vertex cover:summary,No better constant-factor approximation is known!,More precisely,minimum vertex cover is known to be approximable within(for a given|V|,2)(ADM85),but cannot be approximated within,7/6(Hastad STOC97),for any sufficiently large vertex degree,Dinur Safra (STOC02),1.36067,8Vertex cover:summaryNo bette,9,Vertex cover:summary,Eran Halperin,Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs,SIAM Journal on Computing,31/5(2002):1608-1623.,Tomokazu Imamura,Kazuo Iwama,Approximating vertex cover on dense graphs,Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms 2005,9Vertex cover:summaryEran Hal,10,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,就具有三角不等式性质。,旅行售货员问题的一些,特殊性质,：,103 旅行售货员问题近似算法问题描述：给定一个完全无向图,11,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倍。,113.1 旅行售货员问题近似算法对于给定的无向图G，可以,12,Preorder Traversal,Preorder:(root-left-right),Visit the,root first,;and then,traverse the,left,subtree;and then,traverse the,right,subtree.,Example:,Order:,A,B,C,D,E,F,G,H,I,12 Preorder Traversal Preord,13,3.1,旅行售货员问题举例,(,b),表示找到的最小生成树,T；,(,c),表示对,T,作前序遍历的次序；,(d),表示,L,产生的哈密顿回路,H,，作为近似解,；,(e),是,G,的一个最小费用旅行售货员回路的最优解。,133.1 旅行售货员问题举例(b)表示找到的最小生成树,14,3.2 一般,的,旅行售货员问题,在费用函数不一定满足三角不等式的一般情况下，不存在具有常数性能比的解,TSP,问题的多项式时间近似算法，除非,P=NP,。,换句话说，若,PNP，,则对任意常数,1，,不存在性能比为,的解旅行售货员问题的多项式时间近似算法。,143.2 一般的旅行售货员问题在费用函数不一定满足三角不,15,2-approximation,Theorem.,ApproxTSP,is a polynomial-time 2-approximation algorithm for the traveling-salesman problem with the triangle inequality.,Pf.,Let,C,OPT,be the optimal cycle,Cost(T)Cost(C,OPT,),Removing an edge from,H,gives a spanning tree,T,is a spanning tree of minimum cost,Cost(W)=2 Cost(T),Each edge visited twice,Cost(H)Cost(W),Triangle inequality,Cost(H)2 Cost(COPT),152-approximationTheorem.Appr,16,4,子集和问题,问题描述：设子集和问题的一个实例为,S,t。,其中，,S=x,1,，x,2,，,，x,n,是一个正整数的集合，,t,是一个正整数。子集和问题判定是否存在,S,的一个子集,S1，,使得 。,164 子集和问题问题描述：设子集和问题的一个实例为S,17,4,.1 子集和问题的指数时间算法,int E,xactSubsetSum,(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,合并成为一个新的有序表的算法,M,ergeLists,(L1,L2)。,174.1 子集和问题的指数时间算法int ExactSu,18,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来代表。,185.2 子集和问题的近似算法基于算法ExactSubs,19,5.2 子集合问题的近似算法,对有序表,L,修整算法,List T,rim,(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