第十五章近似算法

1、第十五章第十五章 近似算法近似算法15.1 近似算法的性能近似算法的性能15.2 装箱问题装箱问题15.3 顶点覆盖问题顶点覆盖问题15.4 货郎担问题货郎担问题15.5 多项式近似方案多项式近似方案15.1 近似算法的性能近似算法的性能一、近似算法的基本要求一、近似算法的基本要求二、近似比率二、近似比率三、相对误差三、相对误差四、优化问题的近似方案四、优化问题的近似方案一、近似算法的基本要求一、近似算法的基本要求对于规模为对于规模为n的问题，的问题， 1. 算法能以算法能以n的多项式时间内完成；的多项式时间内完成；2. 算法的近似解满足一定的精度。算法的近似解满足一定的精度。二、近似比率二、

2、近似比率1、近似算法的近似比率、近似算法的近似比率2、与近似比率相关的问题、与近似比率相关的问题三、相对误差三、相对误差四、优化问题的近似方案四、优化问题的近似方案15.2 装箱问题装箱问题15.2.0 概述概述15.2.1 首次适宜算法首次适宜算法15.2.2 最适宜算法及其它算法最适宜算法及其它算法15.2.0 概述概述一、装箱问题（一、装箱问题（BIN PACKING）二、装箱问题的四种算法二、装箱问题的四种算法一、装箱问题（一、装箱问题（BIN PACKING）二、装箱问题的四种算法二、装箱问题的四种算法15.2.1 首次适宜算法首次适宜算法一、一、FF算法算法二、二、FF算法的分析算

3、法的分析一、一、FF算法算法 1. void first_fit(float s,int n,float C,float 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)10. j+; 11. bj += si; 12. k = max(k,j); 13. 14. k+;15. 二、二、FF算法的分析算法的分析15.2.2 最适宜算法及其它算法最适宜算法及其它算法一、最适宜算法一、最适宜算法二、首次适宜降序算法二、首次适

4、宜降序算法FFD及最适宜降序算法及最适宜降序算法 1. void best_fit(float s,int n,float C,float b,int &k) 2. 3. int i,j,m; 4. float min,temp; 5. k = 0; 6. for (i=0;in;i+) 7. bi = 0; 1. 最适宜算法最适宜算法 8. for (i=0;in;i+) 9. min = C; m = k + 1;10. for (j=0;j=0)&(tempmin) 14. min = temp; m = j;15. 16. 17. bm += si; 18. k = max(k,m);

5、 19. 20. k+;21. 1. 最适宜算法最适宜算法二、首次适宜降序算法二、首次适宜降序算法FFD及最适宜降序算法及最适宜降序算法 1. 装箱问题的首次适宜降序算法装箱问题的首次适宜降序算法 1. void first_fit_dec(float s ,int n,float C,float b ,int &k) 2. 3. mergsort(s,n); /* 把物体按体积大小的递减顺序排序把物体按体积大小的递减顺序排序 */ 4. first_fit(s,n,C,b,k); /* 按首次适宜算法把排序过的物体装入箱子按首次适宜算法把排序过的物体装入箱子 */5. 2. 装箱问题的最适宜

6、降序算法装箱问题的最适宜降序算法 1. void best_fit_dec(float s ,int n,float C,float b ,int &k) 2. 3. mergsort(s,n); /* 把物体按体积大小递减的顺序排序把物体按体积大小递减的顺序排序 */ 4. best_fit_dec(s,n,C,b,k); /* 按最适宜算法把排序过的物体装入箱子按最适宜算法把排序过的物体装入箱子 */ 5. 15.3 顶点覆盖问题顶点覆盖问题一、顶点覆盖的优化问题一、顶点覆盖的优化问题二、数据结构二、数据结构 三、求解步骤三、求解步骤四、近似算法的实现过程四、近似算法的实现过程 五、算法的

7、近似性能五、算法的近似性能 一、顶点覆盖的优化问题一、顶点覆盖的优化问题二、数据结构二、数据结构 假定，顶点用假定，顶点用 0,1,n 编号；用下面的邻接表存放顶点与顶点编号；用下面的邻接表存放顶点与顶点之间的关联边。之间的关联边。struct adj_list /* 邻接表结点的数据结构邻接表结点的数据结构 */ int v_num;/* 邻接顶点的编号邻接顶点的编号 */ struct adj_list *next;/* 下一个邻接顶点下一个邻接顶点 */;typedef struct adj_list NODE;NODE *Vn;/* 图图G的邻接表头结点的邻接表头结点 */三、求解步骤

8、三、求解步骤四、近似算法的实现过程四、近似算法的实现过程 算法算法15.5 顶点覆盖优化问题的近似算法顶点覆盖优化问题的近似算法输入输入:无向图无向图G的邻接表的邻接表V ,顶点个数顶点个数n输出输出:图图G的顶点覆盖的顶点覆盖C ,C中的顶点个数中的顶点个数m 1. vertex_cover_app(NODE *V ,int n,int C ,int &m) 2. 3. NODE *p,*p1; 4. int u,v; 5. m = 0;四、近似算法的实现过程四、近似算法的实现过程 6. for (u=0;uv_num; m += 2;10. while (p!=NULL) /* 则选取边则

9、选取边(u,v)的顶点的顶点 */11. delete_e(p-v_num,u); /* 删去与删去与u关联的所有边关联的所有边 */12. p = p-next;13. 14. Vu.next = NULL;15. p1 = Vv.next;16. while (p1!=NULL) /* 删去与删去与v关联的所有边关联的所有边 */17. delete_e(p-v_num,v);18. p = p-next;19. 20. Vv.next = NULL;21. 22. 23. 例：图例：图15.2表示顶点覆盖近似算法的执行过程表示顶点覆盖近似算法的执行过程图图15.2(a)表示图的初始状态表

10、示图的初始状态；图图15.2(g)表示最后得到的结果。表示最后得到的结果。五、算法的近似性能五、算法的近似性能 15.4 货郎担问题货郎担问题15.4.0 货郎担问题概述货郎担问题概述15.4.1 欧几里德货郎担问题欧几里德货郎担问题15.4.2 一般的货郎担问题一般的货郎担问题15.4.0 货郎担问题概述货郎担问题概述15.4.1 欧几里德货郎担问题欧几里德货郎担问题一、解欧几里德货郎担问题的近似算法的思想方法一、解欧几里德货郎担问题的近似算法的思想方法二、实现步骤二、实现步骤三、算法的实现过程三、算法的实现过程四、算法的性能比率四、算法的性能比率一、解欧几里德货郎担问题的近似算法的思想方法

11、一、解欧几里德货郎担问题的近似算法的思想方法 构造图构造图G的最小花费生成树的最小花费生成树T，遍历，遍历T的顶点，把的顶点，把T转换为一转换为一条哈密尔顿回路条哈密尔顿回路L。二、实现步骤二、实现步骤三、算法的实现过程三、算法的实现过程 算法算法15.6 欧几里德货郎担问题的近似算法欧几里德货郎担问题的近似算法输入：图输入：图G的费用矩阵的费用矩阵C ,顶点个数顶点个数n输出：哈密尔顿回路输出：哈密尔顿回路L及回路的费用及回路的费用f 1. void MST_salesman_app(float C ,int n,int L , float &f) 2. 3. int i,k,prenn,p

12、ostnn; 4. EDGE Tn;/* 存放最小生成树的边集存放最小生成树的边集 */ 5. NODE noden,*p; 6. for (i=0;in;i+) /* 最小生成树的邻接表头结点初始化最小生成树的邻接表头结点初始化 */ 7. nodei.next = NULL; 8. prim(C,n,T,k); /* 调用普里姆算法构造最小生成树的边集调用普里姆算法构造最小生成树的边集T */三、算法的实现过程三、算法的实现过程 9. for (i=0;iv = Ti.v; 12. p-next = nodeTi.u.next;13. nodeTi.u.next = p;14. p = n

13、ew NODE;15. p-v = Ti.u;16. p-next = nodeTi.v.next;17. nodeTi.v.next = p;18. /* 调用深度优先搜索算法遍历调用深度优先搜索算法遍历T */19. traver_dfs(node,n,pren,postn,L);20. f = 0;21. for (i=0;in-1;i+)/* 计算回路的费用计算回路的费用 */22. f += CLiLi+1;23. f += CLn-1L0;24. 例：最小生成树探索算法的执行过程和性能比率的说明例：最小生成树探索算法的执行过程和性能比率的说明 图图15.3(b)中的粗线表示用深度优

14、先中的粗线表示用深度优先搜索算法前序遍历生成树搜索算法前序遍历生成树T所得到的所得到的结果，这个结果也是最小生成树探结果，这个结果也是最小生成树探索算法的执行结果。索算法的执行结果。图图15.3(a)表示由普里姆算法所表示由普里姆算法所生成的最小花费生成树生成的最小花费生成树T；四、算法的性能比率四、算法的性能比率15.4.2 一般的货郎担问题一般的货郎担问题15.5 多项式近似方案多项式近似方案15.5.1 0/1背包问题的多项式近似方案背包问题的多项式近似方案15.5.2 子集求和问题的完全多项式近似方案子集求和问题的完全多项式近似方案15.5.1 0/1背包问题的多项式近似方案背包问题的

15、多项式近似方案15.5.1 0/1背包问题的多项式近似方案背包问题的多项式近似方案一、贪婪算法的性能比率可能无界一、贪婪算法的性能比率可能无界二、二、0/1背包问题的近似算法背包问题的近似算法三、多项式近似方案算法三、多项式近似方案算法一、贪婪算法的性能比率可能无界一、贪婪算法的性能比率可能无界二、二、0/1背包问题的近似算法背包问题的近似算法2、数据结构：、数据结构： typedef struct int num; /* 物体序号物体序号 */ float s;/* 物体体积物体体积 */ float v;/* 物体价值物体价值 */ float p;/* 物体的价值体积比物体的价值体积比

16、*/ ITEM; ITEMkpn;3、算法描述、算法描述 1. void knapsack_reedy(ITEM ob ,int n,float C,int kp ,float &V,int &k) 2. 3. int i,j; 4. float r,V1; 5. mergesort(ob,n);/* 按价值体积比的递减顺序排序按价值体积比的递减顺序排序ob中物体中物体*/ 6. i = k =0; r = V = 0; 7. while (in)&(rC) /* 按贪婪法从按贪婪法从ob中选择物体中选择物体 */ 8. if (si=C-r) 9. kpk+ = si.num; /* 装入背

17、包的物体的原始序号装入背包的物体的原始序号 */10. r += si.s;/* 装入背包中物体的体积累计装入背包中物体的体积累计 */11. V += si.v;/* 装入背包中物体的价值累计装入背包中物体的价值累计*/12. 13. i+;14. 3、算法描述、算法描述 15. V1 = s0.v; j = 0;16. for (i=1;in;i+) /* 选取价值最大的物体作为候选者选取价值最大的物体作为候选者 */17. if (V1V) /* 若候选者的价值大于贪婪法选取的价值若候选者的价值大于贪婪法选取的价值*/22. V = V1; kp0 = si.num; k = 1; 23

18、. /* 取候选者作为输出结果取候选者作为输出结果 */24. 三、多项式近似方案算法三、多项式近似方案算法15.5.2 子集求和问题的完全多项式近似方案子集求和问题的完全多项式近似方案一、子集求和问题一、子集求和问题二、动态规划算法二、动态规划算法 三、近似算法三、近似算法一、子集求和问题一、子集求和问题 二、动态规划算法二、动态规划算法 1. void subset_sum(int s ,int n,int C,BOOL x ,int &sum) 2. 3. int i,j,k; 4. int (*T)C+1 = new intn+1C+1; /*分配表的工作单元分配表的工作单元 */ 5. for (i=0;i=n;i+) /* 初始化表的第初始化表的第0列列 */ 6. Ti0 = 0; xi = FALSE; /* 解向量初始化为解向量初始化为FALSE */ 7. 8. for (i=0;i=C;i+) /* 初始化表的第初始化表的第0行行 */ 9. T0i