第9章近似算法竞赛专用

1第第9章章 近似算法近似算法2第第9章章 近似算法近似算法*迄今为止，所有的NP完全问题都还没有多项式时间算法。对于这类问题，通常可采取以下几种解题策略。(1)只对问题的特殊实例求解(2)用动态规划法或分支限界法求解(3)用概率算法求解(4)只求近似解(5)用启发式方法求解 本章主要讨论解NP完全问题的近似算法近似算法。39.1 近似算法的性能近似算法的性能 若一个最优化问题的最优值为c*，求解该问题的一个近似算法求得的近似最优解相应的目标函数值为c，则将该近似算法的性能比近似算法的性能比定义为=。在通常情况下，该性能比是问题输入规模n的一个函数(n)，即 (n)。cccc*,*maxcccc*,*max该近似算法的相对误差近似算法的相对误差定义为=。若对问题的输入规模n，有一函数(n)使得 (n)，则称(n)为该近似算法的相对误差界近似算法的相对误差界。近似算法的性能比(n)与相对误差界(n)之间显然有如下关系：(n)(n)(n)-1(n)-1。*ccc*ccc 49.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为空。为空。59.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。69.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就具有三角不等式性质。旅行售货员问题的一些特殊性质特殊性质：79.3.1 具有三角不等式性质的具有三角不等式性质的旅行售货员问题旅行售货员问题 对于给定的无向图G，可以利用找图图G G的最小生成树的最小生成树的算法设计找近似最优的旅行售货员回路的算法。void approxTSPapproxTSP(Graph g)(1)选择g的任一顶点r；(2)用Prim算法找出带权图g的一棵以r为根的最小生成树T；(3)前序遍历树T得到的顶点表L；(4)将r加到表L的末尾，按表L中顶点次序组成回路H，作为计算结果返回；当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的2倍。89.3.1 具有三角不等式性质的具有三角不等式性质的旅行售货员问题举例旅行售货员问题举例(b)b)表示找到的最小生成表示找到的最小生成树树T T；(c)c)表示对表示对T T作前序作前序遍历的次序；遍历的次序；(d)(d)表示表示L L产产生的哈密顿回路生的哈密顿回路H H；(e)(e)是是G G的一个最小费用旅的一个最小费用旅行售货员回路。行售货员回路。99.3.2 一般一般的的旅行售货员问题旅行售货员问题 在费用函数不一定满足三角不等式的一般情况下，不存在具有常数性能比的解TSP问题的多项式时间近似算法，除非P=NPP=NP。换句话说，若PNP，则对任意常数1，不存在性能比为的解旅行售货员问题的多项式时间近似算法。109.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 FSSCSS119.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,。129.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；139.5 子集合问题的近似算法子集合问题的近似算法 问题描述：设子集和问题的一个实例为S,t。其中，S=x1，x2，xn是一个正整数的集合，t是一个正整数。子集和问题判定是否存在S的一个子集S1，使得 。txSx 1149.5.1 子集合问题的指数时间算法子集合问题的指数时间算法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)。159.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来代表。169.5.2 子集合问题的完全多项式子集合问题的完全多项式时间近似格式时间近似格式对有序表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 approxSubsetSum 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)；