算法设计与分析Ch9-2.ppt





《算法设计与分析Ch9-2.ppt》由会员分享,可在线阅读,更多相关《算法设计与分析Ch9-2.ppt(16页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第9章 近似算法1第9章 近似算法 迄今为止,所有的NP完全问题都还没有多项式时间算法。对于这类问题,通常可采取以下几种解题策略。(1)只对问题的特殊实例求解(2)用动态规划法或分支限界法求解(3)用概率算法求解(4)只求近似解(5)用启发式方法求解 本章主要讨论解NP完全问题的近似算法近似算法。29.1 近似算法的性能 若一个最优化问题的最优值为c*,求解该问题的一个近似算法求得的近似最优解相应的目标函数值为c,则将该近似算法的性能比近似算法的性能比定义为=。在通常情况下,该性能比是问题输入规模n的一个函数(n),即 (n)。该近似算法的相对误差近似算法的相对误差定义为=。若对问题的输入规模
2、n,有一函数(n)使得 (n),则称(n)为该近似算法的相对误差界近似算法的相对误差界。近似算法的性能比(n)与相对误差界(n)之间显然有如下关系:(n)(n)(n)-1(n)-1。39.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
3、和v相关联的所有边;return c CsetCset用来存储顶点用来存储顶点覆盖中的各顶点。初覆盖中的各顶点。初始为空,不断从边集始为空,不断从边集e1e1中选取一边中选取一边(u,v)u,v),将边的端点加入将边的端点加入csetcset中,并将中,并将e1e1中已中已被被u u和和v v覆盖的边删去,覆盖的边删去,直至直至csetcset已覆盖所有已覆盖所有边。即边。即e1e1为空。为空。49.2 顶点覆盖问题的近似算法 图图(a)a)(e)(e)说明说明了算法的运行过程了算法的运行过程及结果。及结果。(e)e)表示表示算法产生的近似最算法产生的近似最优顶点覆盖优顶点覆盖csetcset
4、,它由顶点它由顶点b,c,d,e,f,gb,c,d,e,f,g所组所组成。成。(f)f)是图是图G G的一的一个最小顶点覆盖,个最小顶点覆盖,它只含有它只含有3 3个顶点:个顶点:b,db,d和和e e。算法approxVertexCoverapproxVertexCover的性能比为2。59.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中的顶点就是平面
5、上的点,任意2顶点间的费用就是这2点间的欧氏距离时,费用函数c就具有三角不等式性质。旅行售货员问题的一些特殊性质特殊性质:69.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,作为计算结果返回;当费用函数满足三角不等式时,算法找出的旅行售货员回路的费用不会


- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 分析 Ch9

限制150内