算法设计与分析王红梅第二版第11章近似算法

1、11.1 11.1 概概 述述11.1 11.1 概概 述述cccc*,*maxcccc*,*max11.1 11.1 概概 述述*ccc*ccc 11.1 11.1 概概 述述11.1 概概 述述 11.2 图图问题中的近似法问题中的近似法11.3 组合问题中的近似法组合问题中的近似法*11.4 实验项目实验项目TSP问题的近似法问题的近似法11.2.1 顶点覆盖问题顶点覆盖问题 11.2.2 TSP问题问题n 问题描述：问题描述： 无向图G=(V,E)的顶点覆盖问题：指是它的顶点集V 的一个子集V V，使得使得: :若(u,v) 是G的一条边，则vV 或uV。顶点覆盖V 的大小是它所包含的

2、顶点个数顶点个数 |V|。 VertexSet approxVertexCover ( Graph g ) cset=； e1=g.e； while (e1 != ) 从e1中任取一条边(u,v)； cset=csetu,v； 从e1 中删去与u 和v 相关联的所有边； return c cset用来存储顶点用来存储顶点覆盖中的各顶点。初覆盖中的各顶点。初始为空，不断从边集始为空，不断从边集e1中选取一边中选取一边(u,v)，将边的端点加入将边的端点加入cset中，并将中，并将e1中已被中已被u和和v覆盖的边删去，覆盖的边删去，直至直至cset已覆盖所有已覆盖所有边。即边。即e1为空。为空。

3、图图(a)(a)(e)(e)说明说明了算法的运行过程了算法的运行过程及结果。及结果。(e)(e)表示表示算法产生的近似最算法产生的近似最优顶点覆盖优顶点覆盖csetcset，它由顶点它由顶点b,c,d,e,f,gb,c,d,e,f,g所组所组成。成。(f)(f)是图是图G G的一的一个最小顶点覆盖，个最小顶点覆盖，它只含有它只含有3 3个顶点：个顶点：b,db,d和和e e。 算法approxVertexCoverapproxVertexCover的性能比为2。 11.2.1 顶点覆盖问题11.2.1 顶点覆盖问题顶点覆盖问题 11.2.2 TSP问题问题问题描述：问题描述：给定一个完全无向图

4、给定一个完全无向图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中的中的顶点就是平面上的点，任意顶点就是平面上的点，任意2顶点间的费用就是这顶点间的费用就是这2点间的点间的欧氏距离时，费用函数欧氏距离时，费用函数c就具有三角不等式性质。就具有三角不等式性质。 TSP 问题的一些特殊性质特殊性质：但

5、是，可以设计一个近似算法，其近似比为2。图11.2(a)给出了一个满足三角不等式的无向图，图中方格的边长为1。求解TSP问题的近似算法首先采用Prim算法生成图的最小生成树T，如图(b)所示，图中粗线表示最小生成树中的边，然 后 对T进 行 深 度 优 先 遍 历 ， 经 过 的 路 线 为abcbhbadefegeda，得到遍历序列L=(a, b, c, h, d, e, f, g)，由序列L得到哈密顿回路，即近似最优解，如图(d)所示，其路径长度约为19.074，图(e)所示是(a)的最优解，其路径长度约为16.084。(b)(b)表示找到的最小生成表示找到的最小生成树树T T；(c)(c

6、)表示对表示对T T作深度作深度优先遍历的次序；优先遍历的次序；(d)(d)表表示示L L产生的哈密顿回路产生的哈密顿回路H H；(e)(e)是是G G的一个最小费用旅的一个最小费用旅行售货员回路。行售货员回路。 对于给定的无向图G，可以利用找图图G的最小生成树的最小生成树的算法设计找近似最优的旅行售货员回路的算法。 void approxTSP (Graph g) (1)选择 G的任一顶点 r； (2)用 Prim 算法找出带权图 G 的一棵以r 为根的最小生成树 T； (3)对生成树T从顶点r出发进行深度优先遍历，得遍历序列 L； (4)将r 加到表 L 的末尾，按表 L 中顶点次序组成回

7、路H，作为 计算结果返回； 当费用函数满足三角不等式时，算法找出的旅行售货员回路当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的的费用不会超过最优旅行售货员回路费用的2 2倍倍。 在费用函数不一定满足三角不等式的一般情况下，不存在具有常数性能比的解TSP问题的多项式时间近似算法，除非P=NP。换句话说，若PNP，则对任意常数1，不存在性能比为的解旅行售货员问题的多项式时间近似算法。 11.1 概概 述述 11.2 图图问题中的近似法问题中的近似法11.3 组合问题中的近似法组合问题中的近似法*11.4 实验项目实验项目TSP问题的近似法问题的近似法例如

8、，有10个物品，其体积分别为S(4, 2, 7, 3, 5, 4, 2, 3, 6, 2)，若干个容量为10的箱子，采用首次适宜法得到的装箱结果如图11.3所示。 0.3(s4)0.2(s2)0.4(s1)0.2(s7)0.7(s3)0.4(s6)0.5(s5)0.6(s9)0.3(s8)0.2(s10)(a) 箱子1 (b) 箱子2 (c) 箱子3 (d) 箱子4 (e) 箱子5图11.3 首次适宜法求解装箱问题示例（阴影表示闲置部分） 首次适宜法求解装箱问题的算法如下：算法算法11.3FF 算法算法 1. void first_fit(float s,int n,float C,float

9、 b,int &k) 2. 3. int i,j; 4. k = 0;/* 装入物体的箱子下标装入物体的箱子下标 */ 5. for (i=0;in;i+)/* 箱子初始化为空箱子初始化为空 */ 6. bi = 0; 7. for (i=0;in;i+) /* 按物体顺序装入按物体顺序装入 */ 8. j = 0; 9. while (C-bj)si) /* 检索能容纳物体检索能容纳物体i的下标最小的箱子的下标最小的箱子j */ 10. j+; 11. bj += si; 12. k = max(k,j); /* 已装入物体的箱子最大下标已装入物体的箱子最大下标 */ 13. 14. k+;

10、/* 箱子的最大下标转换为箱子的个数箱子的最大下标转换为箱子的个数 */ 15. iiniikiis11ii12 , 1ki， niikiikiis111niikiikiisIFF1112)(kkkkkk11kkkkkk11所以，所以，及及2)(1017)(IOPTIFFniisIOPT1)(2)()()(IOPTIFFIFFFFFF算法的性能比率算法的性能比率)( IFF2 2最适宜法最适宜法 最适宜法的物品装入过程与首次适宜法类似，不同的是，总是把物品装到能够容纳它并且目前最满的箱子中，使得该箱子装入物品后闲置空间最小。 例如，有10个物品，其体积分别为S(4, 2, 7, 3, 5, 4

11、, 2, 3, 6, 2)，若干个容量为10的箱子，采用最适宜法得到的装箱结果如图11.4所示。 0.4(s6)0.2(s2)0.4(s1)0.3(s4)0.7(s3)0.3(s8)0.2(s7)0.5(s5)0.2(s10)0.6(s9)(a) 箱子1 (b) 箱子2 (c) 箱子3 (d) 箱子4图11.4 最适宜法求解装箱问题示例（阴影表示闲置部分）算法算法11.4BF 算法算法 1. void Best_fit(float s,int n,float C,float b,int &k) 2. /假设物品体积为整数，假设物品体积为整数，bj为第为第j个箱子已装入物品的体积，数组下标均从个

12、箱子已装入物品的体积，数组下标均从1开始开始 3. int i,j; 4. k = 0;/* 初始化初始化 */ 5. for (j=0;jn;j+) 6. bj = 0; 7. for (i=0;in;i+) /* 装入第装入第i个物品个物品 */ 8. min=C; m=k+1; 9. for(j=1;j0&tempminmin=temp;m=j; 12. 13. bm+=si; k = max(k,m); /* 已装入物体的箱子最大下标已装入物体的箱子最大下标 */ 14. 15. return k;/* 已装入物品的箱子个数已装入物品的箱子个数 */ 16. 11.3.2 11.3.2

13、 子集和问题子集和问题 令S=s1, s2, sn是一个正整数的集合，子集和问题要求在这个正整数集合中，找出其和不超过正整数C的最大和数的子集。 考虑蛮力法求解子集和问题，为了求得集合s1, s2, sn的所有子集和，先将所有子集和的集合初始化为L0=0，然后求得子集和中包含s1的情况，即L0中的每一个元素加上s1，用L0+s1表示对集合L0中的每个元素加上s1后得到的新集合，则所有子集和的集合为L1=L0+(L0+s1)=0, s1；再求得子集和中包含s2的情况，即L1中的每一个元素加上s2，所有子集和的集合为L2=L1+(L1+s2)=0, s1, s2, s1+s2；依此类推，一般情况下

14、，为求得子集和中包含si（1in）的情况，即Li-1中的每一个元素加上si，所有子集和的集合为Li=Li-1+(Li-1+si)。因为子集和问题要求不超过正整数C，所以，每次合并后都要在Li中删除所有大于C的元素。例如，若S=104, 102, 201, 101，C=308，利用上述算法求解子集和问题的过程如图11.7所示L0=0L1=L0+(L0+104)=0+104=0, 104L2=L1+(L1+102)=0, 104+102, 206=0, 102, 104, 206L3=L2+(L2+201)=0, 102, 104, 206+201, 303, 305, 407 =0, 102,

15、104, 201, 206, 303, 305L4=L3+(L2+101)=0, 102, 104, 201, 206, 303, 305+101, 203, 205, 302, 307, 404, 406 =0, 101, 102, 104, 201, 203, 205, 206, 302, 303, 305, 307图11.7 蛮力法求解子集和问题示例 集合Li以数组Li的形式存储，n个元素的正整数集合S用数组sn存储且下标从1开始，两个集合的合并操作与4.3.1中介绍的归并排序的合并算法类似，蛮力法求解子集和问题的算法如下： 算法11.5子集和问题 int SubsetSum1(int

16、n, int s , int C) L0=0； for (i=1; i=n; i+) /依次计算子集和中包含元素si Li=Merge(Li-1, Li-1+si)； 删去Li中超过C的元素； return max(Ln)； 算法SubsetSum1中的数组Li是一个包含了不超过C的所有可能的(s1, s2, si)的子集和，在最坏情况下（即Li中的元素各不相同），Li中的元素个数为2i，所以，算法SubsetSum1的时间复杂性为O(2n)基于算法SubsetSum1的近似算法的基本思想是，在迭代过程中，对数组Li进行适当的修整，使得在子集和不超过一定误差的前提下，尽可能减少数组Li中的元素

17、个数，从而获得算法时间性能的提高。具体方法是：用一个修整参数（01），从数组Li中删去尽可能多的元素，得到一个数组L1i，使得每一个从Li中删去的元素y，在数组L1i中都有一个修整后的元素z满足(1-)yzy，可以将z看作是被删去元素y在修整后的数组L1i中的代表。 例如，若=0.1，且L=10, 11, 12, 15, 20, 21, 22, 23, 24, 29，则用对L进行修整后得到L1=10, 12, 15, 20, 23, 29。其中被删去的元素11由10来代表，21和22由20来代表，24由23来代表。 给定一个修整参数，对有序数组L的修整算法如下： 算法11.6有序数组的修整 i

18、nt Trim(int m, int L , int L1 , double ) /数组L的长度为m，下标从1开始， /对数组L修整后存储在数组L1中 L11=L1;/数组L1中一定包含数组L的最小元素，并作为修整的基础 last=L1； for (i=2; i=m; i+) if (last(1-)*Li) /将所有与last相差的元素删去 将Li加入表L1的尾部； last=Li； return L1; 算法Trim的基本语句是for循环中的条件语句，显然，其时间复杂性为O(m)。 子集和问题的近似算法与蛮力法求解子集和问题的算法类似。不同的是，近似算法在每次合并结束并且删除所有大于C的元素后，在子集和不超过近似误差的前提下，以=/n作为修整参数对合并结果Li进行修整，尽可能减少下次参与迭代的元素个数。例如，设正整数的集合S=104, 102, 201, 101，C=308，给定近似参数=