第十五章近似算法

1、第十五章第十五章 近似算法近似算法15.1 近似算法的性能近似算法的性能15.2 裝箱問題裝箱問題15.3 頂點覆蓋問題頂點覆蓋問題15.4 貨郎擔(dān)問題貨郎擔(dān)問題15.5 多項式近似方案多項式近似方案15.1 近似算法的性能近似算法的性能一、近似算法的基本要求一、近似算法的基本要求二、近似比率二、近似比率三、相對誤差三、相對誤差四、優(yōu)化問題的近似方案四、優(yōu)化問題的近似方案一、近似算法的基本要求一、近似算法的基本要求對于規(guī)模為對于規(guī)模為n的問題，的問題， 1. 算法能以算法能以n的多項式時間內(nèi)完成；的多項式時間內(nèi)完成；2. 算法的近似解滿足一定的精度。算法的近似解滿足一定的精度。二、近似比率二、

2、近似比率1、近似算法的近似比率、近似算法的近似比率2、與近似比率相關(guān)的問題、與近似比率相關(guān)的問題三、相對誤差三、相對誤差四、優(yōu)化問題的近似方案四、優(yōu)化問題的近似方案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

5、 = max(k,m); 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); /* 按首次適宜算法把排序過的物體裝入箱子按首次適宜算法把排序過的物體裝入箱子

6、*/5. 2. 裝箱問題的最適宜降序算法裝箱問題的最適宜降序算法 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 頂點覆蓋問題頂點覆蓋問題一、頂點覆蓋的優(yōu)化問題一、頂點覆蓋的優(yōu)化問題二、數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)結(jié)構(gòu) 三、求解步驟三、求解步驟四、近似算法的實

7、現(xiàn)過程四、近似算法的實現(xiàn)過程 五、算法的近似性能五、算法的近似性能 一、頂點覆蓋的優(yōu)化問題一、頂點覆蓋的優(yōu)化問題二、數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)結(jié)構(gòu) 假定，頂點用假定，頂點用 0,1,n 編號；用下面的鄰接表存放頂點與頂點編號；用下面的鄰接表存放頂點與頂點之間的關(guān)聯(lián)邊。之間的關(guān)聯(lián)邊。struct adj_list /* 鄰接表結(jié)點的數(shù)據(jù)結(jié)構(gòu)鄰接表結(jié)點的數(shù)據(jù)結(jié)構(gòu) */ int v_num;/* 鄰接頂點的編號鄰接頂點的編號 */ struct adj_list *next;/* 下一個鄰接頂點下一個鄰接頂點 */;typedef struct adj_list NODE;NODE *Vn;/* 圖圖G的鄰接

8、表頭結(jié)點的鄰接表頭結(jié)點 */三、求解步驟三、求解步驟四、近似算法的實現(xiàn)過程四、近似算法的實現(xiàn)過程 算法算法15.5 頂點覆蓋優(yōu)化問題的近似算法頂點覆蓋優(yōu)化問題的近似算法輸入輸入:無向圖無向圖G的鄰接表的鄰接表V ,頂點個數(shù)頂點個數(shù)n輸出輸出:圖圖G的頂點覆蓋的頂點覆蓋C ,C中的頂點個數(shù)中的頂點個數(shù)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;四、近似算法的實現(xiàn)過程四、近似算法的實現(xiàn)過程 6. for (u=0;uv_num; m += 2;10.

9、while (p!=NULL) /* 則選取邊則選取邊(u,v)的頂點的頂點 */11. delete_e(p-v_num,u); /* 刪去與刪去與u關(guān)聯(lián)的所有邊關(guān)聯(lián)的所有邊 */12. p = p-next;13. 14. Vu.next = NULL;15. p1 = Vv.next;16. while (p1!=NULL) /* 刪去與刪去與v關(guān)聯(lián)的所有邊關(guān)聯(lián)的所有邊 */17. delete_e(p-v_num,v);18. p = p-next;19. 20. Vv.next = NULL;21. 22. 23. 例：圖例：圖15.2表示頂點覆蓋近似算法的執(zhí)行過程表示頂點覆蓋近似算

10、法的執(zhí)行過程圖圖15.2(a)表示圖的初始狀態(tài)表示圖的初始狀態(tài)；圖圖15.2(g)表示最后得到的結(jié)果。表示最后得到的結(jié)果。五、算法的近似性能五、算法的近似性能 15.4 貨郎擔(dān)問題貨郎擔(dān)問題15.4.0 貨郎擔(dān)問題概述貨郎擔(dān)問題概述15.4.1 歐幾里德貨郎擔(dān)問題歐幾里德貨郎擔(dān)問題15.4.2 一般的貨郎擔(dān)問題一般的貨郎擔(dān)問題15.4.0 貨郎擔(dān)問題概述貨郎擔(dān)問題概述15.4.1 歐幾里德貨郎擔(dān)問題歐幾里德貨郎擔(dān)問題一、解歐幾里德貨郎擔(dān)問題的近似算法的思想方法一、解歐幾里德貨郎擔(dān)問題的近似算法的思想方法二、實現(xiàn)步驟二、實現(xiàn)步驟三、算法的實現(xiàn)過程三、算法的實現(xiàn)過程四、算法的性能比率四、算法的性能

11、比率一、解歐幾里德貨郎擔(dān)問題的近似算法的思想方法一、解歐幾里德貨郎擔(dān)問題的近似算法的思想方法 構(gòu)造圖構(gòu)造圖G的最小花費生成樹的最小花費生成樹T，遍歷，遍歷T的頂點，把的頂點，把T轉(zhuǎn)換為一轉(zhuǎn)換為一條哈密爾頓回路條哈密爾頓回路L。二、實現(xiàn)步驟二、實現(xiàn)步驟三、算法的實現(xiàn)過程三、算法的實現(xiàn)過程 算法算法15.6 歐幾里德貨郎擔(dān)問題的近似算法歐幾里德貨郎擔(dān)問題的近似算法輸入：圖輸入：圖G的費用矩陣的費用矩陣C ,頂點個數(shù)頂點個數(shù)n輸出：哈密爾頓回路輸出：哈密爾頓回路L及回路的費用及回路的費用f 1. void MST_salesman_app(float C ,int n,int L , float &

12、amp;f) 2. 3. int i,k,prenn,postnn; 4. EDGE Tn;/* 存放最小生成樹的邊集存放最小生成樹的邊集 */ 5. NODE noden,*p; 6. for (i=0;in;i+) /* 最小生成樹的鄰接表頭結(jié)點初始化最小生成樹的鄰接表頭結(jié)點初始化 */ 7. nodei.next = NULL; 8. prim(C,n,T,k); /* 調(diào)用普里姆算法構(gòu)造最小生成樹的邊集調(diào)用普里姆算法構(gòu)造最小生成樹的邊集T */三、算法的實現(xiàn)過程三、算法的實現(xiàn)過程 9. for (i=0;iv = Ti.v; 12. p-next = nodeTi.u.next;13.

13、 nodeTi.u.next = p;14. p = new NODE;15. p-v = Ti.u;16. p-next = nodeTi.v.next;17. nodeTi.v.next = p;18. /* 調(diào)用深度優(yōu)先搜索算法遍歷調(diào)用深度優(yōu)先搜索算法遍歷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. 例：最小生成樹探索算法的執(zhí)行過程和性能比率的說明例：最小生成樹探索算法的執(zhí)行過程

14、和性能比率的說明 圖圖15.3(b)中的粗線表示用深度優(yōu)先中的粗線表示用深度優(yōu)先搜索算法前序遍歷生成樹搜索算法前序遍歷生成樹T所得到的所得到的結(jié)果，這個結(jié)果也是最小生成樹探結(jié)果，這個結(jié)果也是最小生成樹探索算法的執(zhí)行結(jié)果。索算法的執(zhí)行結(jié)果。圖圖15.3(a)表示由普里姆算法所表示由普里姆算法所生成的最小花費生成樹生成的最小花費生成樹T；四、算法的性能比率四、算法的性能比率15.4.2 一般的貨郎擔(dān)問題一般的貨郎擔(dān)問題15.5 多項式近似方案多項式近似方案15.5.1 0/1背包問題的多項式近似方案背包問題的多項式近似方案15.5.2 子集求和問題的完全多項式近似方案子集求和問題的完全多項式近似方

15、案15.5.1 0/1背包問題的多項式近似方案背包問題的多項式近似方案15.5.1 0/1背包問題的多項式近似方案背包問題的多項式近似方案一、貪婪算法的性能比率可能無界一、貪婪算法的性能比率可能無界二、二、0/1背包問題的近似算法背包問題的近似算法三、多項式近似方案算法三、多項式近似方案算法一、貪婪算法的性能比率可能無界一、貪婪算法的性能比率可能無界二、二、0/1背包問題的近似算法背包問題的近似算法2、數(shù)據(jù)結(jié)構(gòu)：、數(shù)據(jù)結(jié)構(gòu)： typedef struct int num; /* 物體序號物體序號 */ float s;/* 物體體積物體體積 */ float v;/* 物體價值物體價值 */

16、float p;/* 物體的價值體積比物體的價值體積比 */ 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中選擇物體中選擇物體 */

17、 8. if (si=C-r) 9. kpk+ = si.num; /* 裝入背包的物體的原始序號裝入背包的物體的原始序號 */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) /* 若候選者的價值大于貪婪法選取的價值若候選者的價值大于貪婪法選取

18、的價值*/22. V = V1; kp0 = si.num; k = 1; 23. /* 取候選者作為輸出結(jié)果取候選者作為輸出結(jié)果 */24. 三、多項式近似方案算法三、多項式近似方案算法15.5.2 子集求和問題的完全多項式近似方案子集求和問題的完全多項式近似方案一、子集求和問題一、子集求和問題二、動態(tài)規(guī)劃算法二、動態(tài)規(guī)劃算法 三、近似算法三、近似算法一、子集求和問題一、子集求和問題 二、動態(tài)規(guī)劃算法二、動態(tài)規(guī)劃算法 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