清华大学出版社 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
清华大学出版社 TSINGHUA UNIVERSITY PRESS 93旅行售货员问题近似算法 问题描述:给定一个完全无向图G=(vE),其每一边 u)∈E有一非负整数费用c{uV)。要找出G的最小费用哈 密顿回路。 旅行售货员问题的一些特殊性质 比如,费用函数c往往具有三角不等式性质,即对任 意的3个顶点uW∈V,有:c(u,W)≤cUV)+c(W)。当 图G中的顶点就是平面上的点,任意2顶点间的费用就 是这2点间的欧氏距离时,费用函数C就具有三角不等式 性质
6 9.3 旅行售货员问题近似算法 问题描述：给定一个完全无向图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就具有三角不等式 性质。 旅行售货员问题的一些特殊性质：
清华大学出版社 TSINGHUA UNIVERSITY PRESS 93.1具有三角不等式性质的 旅行售货员问题 对于给定的无向图G,可以利用找图G的最小生成树的 算法设计找近似最优的旅行售货员回路的算法。 void approxTSP(Graph g) (1)选择g的任一顶点r (2)用Prim算法找出带权图g的一棵以r为根的最小生成树T; (3)前序遍历树T得到的顶点表L (4)将加到表的末尾,按表L中顶点次序组成回路H,作为计算 结果返回; 当费用函数满足三角不等式时,算法找出的旅行售货员回路的 费用不会超过最优旅行售货员回路费用的2倍
7 9.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倍
清华大学出版社 TSINGHUA UNIVERSITY PRESS 93.1具有三角不等式性质的 旅行售货员问题举例 a adh b⑦f+(g (bHf f十g h h ①h (b)表示找到的最小生成 ①b+g 树T;(c)表示对T作前序 遍历的次序;(d)表示L产 ①h 生的哈密顿回路H; (e)是G的一个最小费用 (e) 旅行售货员回路。 8
8 9.3.1 具有三角不等式性质的 旅行售货员问题举例 (b)表示找到的最小生成 树T；(c)表示对T作前序 遍历的次序；(d)表示L产 生的哈密顿回路H； (e)是G的一个最小费用 旅行售货员回路
清华大学出版社 TSINGHUA UNIVERSITY PRESS 93.2一般的旅行售货员问题 在费用函数不一定满足三角不等式的一般情况 下,不存在具有常数性能比的解TSP问题的多项式 时间近似算法,除非P=NP。换句话说,若P≠NP 则对任意常数p>1,不存在性能比为p的解旅行售 货员问题的多项式时间近似算法
9 9.3.2 一般的旅行售货员问题 在费用函数不一定满足三角不等式的一般情况 下，不存在具有常数性能比的解TSP问题的多项式 时间近似算法，除非P=NP。换句话说，若P≠NP， 则对任意常数ρ>1，不存在性能比为ρ的解旅行售 货员问题的多项式时间近似算法
清华大学出版社 TSINGHUA UNIVERSITY PRESS 94集合覆盖问题的近似算法 问题描述:给定一个完全无向图G=(vE),其每一边 (u)∈E有一非负整数费用c(uV)。要找出G的最小费用哈 密顿回路。 集合覆盖问题的一个实例〈X,F〉由一个有限集X及X的 一个子集族F组成。子集族F覆盖了有限集Ⅹ。也就是说X 中每元素至少属于F中的一个子集,即X。对于F中 的一个子集CcF,若C中的X的子集覆盖了X,即士,则 称C覆盖了Ⅹ。集合覆盖问题就是要找岀F中覆盖X的最小 子集C,使得 C|=min{(CCcF且C覆盖X
10 9.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} S F S S C S