第9章 近似算法

第9章 近似算法

第9章 近似算法迄今为止，所有的NP完全问题都还没有多 项式时间算法。对于这类问题，通常可采取以 下几种解题策略。 (1)只对问题的特殊实例求解 (2)用动态规划法或分支限界法求解 (3)用概率算法求解 (4)只求近似解 (5)用启发式方法求解 本章主要讨论解NP完全问题的近似算法。2

9.1 近似算法的性能若一个最优化问题的最优值为c*,求解该问题的一个 近似算法求得的近似最优解相应的目标函数值为c,则将 c c * max , 该近似算法的性能比定义为 = c * c 。在通常情况 下，该性能比是问题输入规模n的一个函数ρ(n),即 c c * max , ≤ρ(n)。 c * c

该近似算法的相对误差定义为 = 。若对问题 c c* 的输入规模n,有一函数ε(n)使得 c * ≤ε(n),则称 ε(n)为该近似算法的相对误差界。近似算法的性能比 ρ(n)与相对误差界ε(n)之间显然有如下关系： ε(n)≤ρ(n)-1。3

c c* c*

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为空。4

9.2 顶点覆盖问题的近似算法图(a)~(e)说明 了算法的运行过程 及结果。(e)表示 算法产生的近似最 优顶点覆盖cset, 它由顶点 b,c,d,e,f,g所组 成。(f)是图G的一 个最小顶点覆盖， 它只含有3个顶点： b,d和e。

算法approxVertexCover的性能比为2。5

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就具有三角不等式 性质。6

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倍。

9.3.1 具有三角不等式性质的 旅行售货员问题举例

(b)表示找到的最小生成 树T;(c)表示对T作前序 遍历的次序；(d)表示L产 生的哈密顿回路H; (e)是G的一个最小费用旅 行售货员回路。

9.3.2 一般的旅行售货员问题在费用函数不一定满足三角不等式的一般情 况下，不存在具有常数性能比的解TSP问题的多项 式时间近似算法，除非P=NP。换句话说，若P≠NP, 则对任意常数ρ>1,不存在性能比为ρ的解旅行 售货员问题的多项式时间近似算法。

9.4 集合覆盖问题的近似算法问题描述：给定一个完全无向图G=(V,E),其每一边 (u,v)∈E有一非负整数费用c(u,v)。要找出G的最小费用 哈密顿回路。

集合覆盖问题的一个实例〈X,F〉由一个有限集X及X 的一个子集族F组成。子集族F覆盖了有限集X。也就是说X 中每一元素至少属于F中的一个子集，即X= S 。对于F中 的一个子集C F,若C中的X的子集覆盖了X,即X= S ,则 称C覆盖了X。集合覆盖问题就是要找出F中覆盖X的最小子 集C*,使得 |C*|=min{|C||C F且C覆盖X}S FS C

9.4 集合覆盖问题的近似算法集合覆盖问题举例：

用12个黑点表示集 合X 。 F={S1,S2,S3,S4,S 5,S6,},如图所示。 容易看出，对于这 个例子，最小集合 覆盖为： C={S3,S4,S5,}。11

9.4 集合覆盖问题的近似算法集合覆盖问题近似算法——贪心算法Set greedySetCover (X,F) { U=X; C= ; while (U != ) { 选择F中使|S∩U|最大的子集S; U=U-S; C=C∪{S}; } return C; 算法的循环体最多 执行min{|X|,|F|}次。 而循环体内的计算显然 可在O(|X||F|)时间内完 成。因此，算法的计算 时间为O(|X||F|min{|X|, |F|})。由此即知，该算 法是一个多项式时间算 法。

}12

9.5 子集合问题的近似算法问题描述：设子集和问题的一个实例为〈S,t〉。 其中，S={x1,x2,…,xn}是一个正整数的集合，t是 一个正整数。子集和问题判定是否存在S的一个子集 S1,使得 x t 。x S 1

9.5.1 子集合问题的指数时间算法int exactSubsetSum (S,t) { int n=|S|; L[0]={0}; for (int i=1;i<=n;i++) { L[i]=mergeLists(L[i-1],L[i-1]+S[i]); 删去L[i]中超过t的元素； } return max(L[n]); }

算法以集合S={x1, x2,…,xn}和目标 值t作为输入。算法 中用到将2个有序表 L1和L2合并成为一 个新的有序表的算 法 mergeLists(L1,L2)。14

9.5.2 子集合问题的完全多项式 时间近似格式基于算法exactSubsetSum,通过对表L[i]作适当的修整建 立一个子集和问题的完全多项式时间近似格式。 在对表L[i]

进行修整时，用到一个修整参数δ,0<δ<1。 用参数δ修整一个表L是 …… 此处隐藏：1285字，全部文档内容请下载后查看。喜欢就下载吧 ……