清华大学出版社 TSINGHUA UNIVERSITY PRESS 第9章近似算法
1 第9章 近似算法
清华大学出版社 TSINGHUA UNIVERSITY PRESS 第9章近似算法 迄今为止,所有的NP完全问题都还没有多 项式时间算法。对于这类问题,通常可采取以 下几种解题策略。 (1)只对问题的特殊实例求解 (2)用动态规划法或分支限界法求解 3)用概率算法求解 (4)只求近似解 (5)用启发式方法求解 本章主要讨论解NP完全问题的近似算法。 2
2 第9章 近似算法 迄今为止，所有的NP完全问题都还没有多 项式时间算法。对于这类问题，通常可采取以 下几种解题策略。 (1)只对问题的特殊实例求解 (2)用动态规划法或分支限界法求解 (3)用概率算法求解 (4)只求近似解 (5)用启发式方法求解 本章主要讨论解NP完全问题的近似算法
清华大学出版社 TSINGHUA UNIVERSITY PRESS 91近似算法的性能 若一个最优化问题的最优值为c*,求解该问题的一个近 似算法求得的近似最优解相应的目标函数值为C,则将该 近似算法的性能比定义为η=mx{在通常情况下,该 性能比是问题输入规模η的一个函数ρ(nη),即 maX ≤pn) 该近似算法的相对误差定义为入=26若对问题 的输入规模n,有一函数)使得n),则称(n)为 该近似算法的相对误差界。近似算法的性能比p(n)与相 对误差界ε(n)之间显然有如下关系:ε(m)≤p(n)-1
3 9.1 近似算法的性能 若一个最优化问题的最优值为c*，求解该问题的一个近 似算法求得的近似最优解相应的目标函数值为c，则将该 近似算法的性能比定义为= 。在通常情况下，该 性能比是问题输入规模n的一个函数ρ(n)，即 ≤ρ(n)。 c c c c * , * max c c c c * , * max 该近似算法的相对误差定义为= 。若对问题 的输入规模n，有一函数ε(n)使得 ≤ε(n)，则称ε(n)为 该近似算法的相对误差界。近似算法的性能比ρ(n)与相 对误差界ε(n)之间显然有如下关系：ε(n)≤ρ(n)-1。 * * c c − c * * c c − c
清华大学出版社 TSINGHUA UNIVERSITY PRESS 92顶点覆盖问题的近似算法 问题描述:无向图G=(VE)的顶点覆盖是它的顶点集V的 个子集vsV,使得若(u,)是G的一条边,则v∈V或 u∈V。顶点覆盖V的大小是它所包含的顶点个数V Vertex Set approx Vertex Cover( Graph g cset=0 Cset用来存储顶点 el=ge i 覆盖中的各顶点。初 始为空,不断从边集 while(el!=0)i e1中选取一边(u,v), 从e1中任取一条边(u,V); 将边的端点加入cset cset=cset∪uUV} 中,并将e1中已被u 从e1中删去与u和M相关联的所有边; 和v覆盖的边删去, 直至cset已覆盖所有 边。即e1为空 return c 4
4 9.2 顶点覆盖问题的近似算法 问题描述：无向图G=(V,E)的顶点覆盖是它的顶点集V的 一个子集V’V，使得若(u,v)是G的一条边，则v∈V’或 u∈V’ 。顶点覆盖V’的大小是它所包含的顶点个数|V’|。 VertexSet approxVertexCover ( Graph g ) { cset=； e1=g.e； while (e1 != ) { 从e1中任取一条边(u,v)； cset=cset∪{u,v}； 从e1中删去与u和v相关联的所有边； } return c } Cset用来存储顶点 覆盖中的各顶点。初 始为空，不断从边集 e1中选取一边(u,v)， 将边的端点加入cset 中，并将e1中已被u 和v覆盖的边删去， 直至cset已覆盖所有 边。即e1为空
清华大学出版社 TSINGHUA UNIVERSITY PRESS 92顶点覆盖问题的近似算法 图(a)~(e)说明 a 了算法的运行过程 及结果。(e)表示 算法产生的近似最 优顶点覆盖cset, a((a(ef 它由顶点 c,d,e,f,g所组 (d) 成。(f)是图G的 个最小顶点覆盖, 它只含有3个顶点: b,d和e。 a e g (e) 算法 approx Vertex Cover的性能比为2
5 9.2 顶点覆盖问题的近似算法 图(a)～(e)说明 了算法的运行过程 及结果。(e)表示 算法产生的近似最 优顶点覆盖cset， 它由顶点 b,c,d,e,f,g所组 成。(f)是图G的一 个最小顶点覆盖， 它只含有3个顶点： b,d和e。 算法approxVertexCover的性能比为2