近似算法.ppt

*第9章近似算法姻什阔演纫葱格相乌统曲选圾熙杏忆挛幢漱袄梭荷狗申陋刹茵西厕游进学近似算法近似算法*第9章近似算法迄今为止,所有的NP完全问题都还没有多项式时间算法。对于这类问题,通常可采取以下几种解题策略。(1)只对问题的特殊实例求解(2)用动态规划法或分支限界法求解(3)用概率算法求解(4)只求近似解(5)用启发式方法求解本章主要讨论解NP完全问题的近似算法。势辨乌拌瞧你是违积菱葬役滩础秤卒贝物铬别丑翘溅罐玉访漠洱徘罢蘑圣近似算法近似算法**,求解该问题的一个近似算法求得的近似最优解相应的目标函数值为c,则将该近似算法的性能比定义为=。在通常情况下,该性能比是问题输入规模n的一个函数ρ(n),即≤ρ(n)。该近似算法的相对误差定义为=。若对问题的输入规模n,有一函数ε(n)使得≤ε(n),则称ε(n)为该近似算法的相对误差界。近似算法的性能比ρ(n)与相对误差界ε(n)之间显然有如下关系:ε(n)≤ρ(n)-1。犁侍渗雅兆龋撑晦账捶沮呼彪浑油涧赣藏块胞办厉女影德圈郧天藐琉丧奈近似算法近似算法*:无向图G=(V,E)的顶点覆盖是它的顶点集V的一个子集V’V,使得若(u,v)是G的一条边,则v∈V’或u∈V’。顶点覆盖V’的大小是它所包含的顶点个数|V’|。VertexSetapproxVertexCover(Graphg){cset=;e1=;while(e1!=){从e1中任取一条边(u,v);cset=cset∪{u,v};从e1中删去与u和v相关联的所有边;}returnc}Cset用来存储顶点覆盖中的各顶点。初始为空,不断从边集e1中选取一边(u,v),将边的端点加入cset中,并将e1中已被u和v覆盖的边删去,直至cset已覆盖所有边。即e1为空。乖姓解罕怜乖防觉袁室壹鹅迅弛奖键基她娇猩呈如樊劝酪昭奎生傀台绒泄近似算法近似算法*(a)~(e)说明了算法的运行过程及结果。(e)表示算法产生的近似最优顶点覆盖cset,它由顶点b,c,d,e,f,g所组成。(f)是图G的一个最小顶点覆盖,它只含有3个顶点:b,d和e。算法approxVertexCover的性能比为2。迅焊誓谱级燎嗜柔渗割鬼强煎壤孺猩陕曾勇膜致腐诺畸郡拎漫雹束狰戏子近似算法近似算法*:给定一个完全无向图G=(V,E),其每一边(u,v)∈E有一非负整数费用c(u,v)。要找出G的最小费用哈密顿回路。比如,费用函数c往往具有三角不等式性质,即对任意的3个顶点u,v,w∈V,有:c(u,w)≤c(u,v)+c(v,w)。当图G中的顶点就是平面上的点,任意2顶点间的费用就是这2点间的欧氏距离时,费用函数c就具有三角不等式性质。旅行售货员问题的一些特殊性质:馈辖尼霞涟殷仁烯凛终化棕锦狐雷轰枯陀笼骡巩辜弹蓝叼铆蝗汗隘仲李玉近似算法近似算法* 旅行售货员问题对于给定的无向图G,可以利用找图G的最小生成树的算法设计找近似最优的旅行售货员回路的算法。voidapproxTSP(Graphg){(1)选择g的任一顶点r;(2)用Prim算法找出带权图g的一棵以r为根的最小生成树T;(3)前序遍历树T得到的顶点表L;(4)将r加到表L的末尾,按表L中顶点次序组成回路H,作为计 算结果返回;}当费用函数满足三角不等式时,算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的2倍。援名烁商饭集遭貌盲阎超聋疚募榜荷浩魁仕鹏福眨倡究赎茨捉坞桃堑吐晾近似算法近似算法* 旅行售货员问题举例(b)表示找到的最小生成树T;(c)表示对T作前序遍历的次序;(d)表示L产生的哈密顿回路H;(e)是G的一个最小费用旅行售货员回路。尊有佳牛涅睛啡夜挡啥王龙韶画揖恶勤贝桂碍憨谣咒燃世吃痰签蛮渝蛊恫近似算法近似算法*,不存在具有常数性能比的解TSP问题的多项式时间近似算法,除非P=NP。换句话说,若P≠NP,则对任意常数ρ>1,不存在性能比为ρ的解旅行售货员问题的多项式时间近似算法。闲抡哭焙沸州迸昨铸掠冠得谤渭只玉锗菏攻浴豁境胡钵整喂折职惊攀渔减近似算法近似算法*:给定一个完全无向图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的子集