多階段決策過程（multistepdecisionprocess）是指這樣一類特殊的

1、.PAGE ;PAGE 25第四部分 貪心算法（Greedy Algorithm）41 貪心算法的基本思想顧名思義，貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當然，希望貪心算法得到的最終結果也是整體最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產生整體最優(yōu)解。如單源最短路經問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結果卻是最優(yōu)解的很好近似?；舅枷耄和ㄟ^一系列選擇步驟來構造問題的解，每一步都是對當前部分解的一個擴展，直至獲得問題的完整解。所做的每一步選擇都必須滿

2、足：可行的：必須滿足問題的約束。局部最優(yōu)：當前所有可能的選擇中最佳的局部選擇。不可取消: 選擇一旦做出，在后面的步驟中就無法改變了。貪心算法是通過做一系列的選擇來給出某一問題的最優(yōu)解，對算法的每一個決策點，做一個當時（看起來）是最佳的選擇。這種啟發(fā)式策略并不總是能產生出最優(yōu)解。2基于貪心算法的實例求解421活動選擇問題活動安排問題：設有n個活動a1, a2, , an , 每個活動都要求使用同一資源，而同一時間內只允許一個活動使用這一資源。已知活動ai要求使用該資源的起始時間為si，結束時間為fi，且si= fi 。要求在a1, a2, , an中選出最大的相容活動子集。兩活動ai , aj

3、(ij)相容是指：。例：n=4 , 活動： a1 a2 a3 a4 si： 4 2 1 8 fi： 7 4 5 10貪心選擇策略：按結束時間從早到晚安排活動，每次選擇與已選出的活動相容的結束時間盡可能早的活動。局部最優(yōu)性：每次為資源留下盡可能多的時間以容納其它活動。貪心算法：算法 ACTIVITY_ARRANGEMENT輸入：活動數n，表示n個活動起始時間和結束時間的數組s1.n和f1.n。輸出：這n個活動的最大的相容活動子集A。/對f1.n按升序地址排序，排序結果返回到數組d1.n中,/使得fd1=fd2=fj then A=A+di/在A中加入活動di。 j=di end if end f

4、or return Aend ACTIVITY_ARRANGEMENT該算法的時間復雜性：(nlogn)(主要為排序的時間) 貪心算法的特點：貪心算法往往效率高，一般時間復雜性為多項式階。貪心算法一般較簡單，其關鍵和難點在于貪心選擇策略的確定，更困難的是證明某貪心算法確實可求出最優(yōu)解?；顒影才艈栴}的貪心選擇策略的正確性證明：證明貪心算法ACTIVITY_ARRANGEMENT求出的解為最優(yōu)解。證明思路：任意一個最優(yōu)解都可通過替換變成該貪心算法求出的解，而且解的最優(yōu)性不變。422 哈夫曼編碼Huffman codes哈夫曼編碼是廣泛地用于數據文件壓縮的十分有效的編碼方法。其壓縮率通常在20%90

5、%之間。哈夫曼編碼算法用字符在文件中出現的頻率表來建立一個用0，1串表示各字符的最優(yōu)表示方式。 給出現頻率高的字符較短的編碼，出現頻率較低的字符以較長的編碼，可以大大縮短總碼長。 例如一個包含100,000個字符的文件，各字符出現頻率不同，如下表所示。定長變碼需要300,000位，而按表中變長編碼方案，文件的總碼長為： （451+133+123+163+94+54）1000=224,000。比用定長碼方案總碼長較少約45%。 對每一個字符規(guī)定一個0,1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱為前綴碼。 編碼的前綴性質可以使譯碼方法非常簡單。 表示最優(yōu)前綴碼的二叉樹

6、總是一棵完全二叉樹，即樹中任一結點都有2個兒子結點。 平均碼長定義為： 使平均碼長達到最小的前綴碼編碼方案稱為給定編碼字符集C的最優(yōu)前綴碼。哈夫曼提出構造最優(yōu)前綴碼的貪心算法，由此產生的編碼方案稱為哈夫曼編碼。 哈夫曼算法以自底向上的方式構造表示最優(yōu)前綴碼的二叉樹T。 算法以|C|個葉結點開始，執(zhí)行|C|1次的“合并”運算后產生最終所要求的樹T。HUFFMAN(c)1 n|c|2 QC3 for i to n-14 do allocate a new code z5 leftzxEXTRACT-MIN(Q)6 rightzyEXTRACT-MIN(Q)7 fz=fx+fy8 INSERT(Q,

7、z)9 return EXTRACT-MIN(Q) 圖4.1 哈夫曼算法的操作步驟時間分析，我們假設Q是作為最小二叉堆實現的。對包含個字符的集合C，第二行中對Q的初始化可用在前面建堆章節(jié)中介紹所用的時間O(n)內完成。第3-8行中的for循環(huán)執(zhí)行了n-1次，又因每一次堆操作需要O（lgn）時間，故整個循環(huán)需要O（nlgn）時間。這樣，作用于n個字符集合的HUFFMAN的總的運行時間為O（nlgn）。423 最小生成樹Minimum spanning trees 假設已知一無向連通圖G=(V,E)，其加權函數為w:ER，我們希望找到圖G的最小生成樹。后文所討論的兩種算法都運用了貪心方法，但在如何

8、運用貪心法上卻有所不同。 下列的算法GENERNIC-MIT正是采用了貪心策略，每步形成最小生成樹的一條邊。算法設置了集合A，該集合一直是某最小生成樹的子集。在每步決定是否把邊(u,v)添加到集合A中，其添加條件是A(u,v)仍然是最小生成樹的子集。我們稱這樣的邊為A的安全邊，因為可以安全地把它添加到A中而不會破壞上述條件。 GENERNIC-MIT(G,W)1. A2. while A沒有形成一棵生成樹3 do 找出A的一條安全邊(u,v);4. AA(u,v);5. return A注意從第1行以后，A顯然滿足最小生成樹子集的條件。第2-4行的循環(huán)中保持著這一條件，當第5行中返回集合A時，

9、A就必然是一最小生成樹。算法最棘手的部分自然是第3行的尋找安全邊。必定存在一生成樹，因為在執(zhí)行第3行代碼時，根據條件要求存在一生成樹T，使AT，且若存在邊(u,v)T且(u,v)A，則(u，v)是A的安全邊。定理4.1設圖G(V,E)是一無向連通圖，且在E上定義了相應的實數值加權函數w，設A是E的一個子集且包含于G的某個最小生成樹中，割(S,V-S)是G的不妨害A的任意割且邊(u,v)是穿過割(S,V-S)的一條輕邊，則邊(u,v)對集合A是安全的。下面介紹兩個算法：Kruskal算法和Prim算法 Kruskal算法是直接基于上面中給出的一般最小生成樹算法的基礎之上的。該算法找出森林中連結任

10、意兩棵樹的所有邊中具有最小權值的邊(u,v)作為安全邊，并把它添加到正在生長的森林中。設C1和C2表示邊(u,v)連結的兩棵樹。因為(u,v)必是連C1和其他某棵樹的一條輕邊，所以由 HYPERLINK http:/.sg/xujia/mirror/ l lemma2 推論2可知(u,v)對C1是安全邊。Kruskal算法同時也是一種 HYPERLINK http:/ 貪心算法，因為算法每一步添加到森林中的邊的權值都盡可能小。 Kruskal算法的實現類似于 HYPERLINK http:/ 計算連通支的算法。它使用了 HYPERLINK http:/ 分離集合數據結構以保持數個互相分離的元素

11、集合。每一集合包含當前森林中某個樹的結點，操作FIND-SET(u)返回包含u的集合的一個代表元素，因此我們可以通過FIND-SET(v)來確定兩結點u和v是否屬于同一棵樹，通過操作UNION來完成樹與樹的聯結。 MST-KRUSKAL(G,w)1. A2. for 每個結點v VG 3. do MAKE-SET(v)4. 根據權w的非遞減順序對E的邊進行排序5. for 每條邊(u,v)E，按權的非遞減次序6. do if FIND-SET(u) FIND-SET(v)7. then AA(u,v)8. UNION(u,v)9 return A(a) (b) (c) (d) (e) (f)

12、(g) (h) (i) (j) (k) (l) (m) (n) 圖4.2 Kruskal算法在 HYPERLINK http:/.sg/xujia/mirror/ l fig1 圖4.1所示的圖上的執(zhí)行流程 Kruskal算法在圖G=(V,E)上的運行時間取決于分離集合這一數據結構如何實現。我們采用在 HYPERLINK http:/ 分離集合中描述的 HYPERLINK http:/ 按行結合和通路壓縮的啟發(fā)式方法來實現分離集合森林的結構，這是由于從漸近意義上來說，這是目前所知的最快的實現方法。初始化需占用時間O(V)，第4行中對邊進行排序需要的運行時間為O(EE)；對分離集的森林要進行O(

13、E)次操作，總共需要時間為O(E(E,V)，其中函數為Ackerman函數的反函數。因為(E,V)=O(E)，所以KruskaI算法的全部運行時間為O(EE)。 正如Kruskal算法一樣，Prim算法也是第上面中討論的 HYPERLINK http:/.sg/xujia/mirror/ 一般最小生成樹算法的特例。Prim算法的執(zhí)行非常類似于尋找圖的最短通路的 HYPERLINK http:/ Dijkstra算法。Prim算法的特點是集合A中的邊總是只形成單棵樹。因為每次添加到樹中的邊都是使樹的權盡可能小的邊，因此上述策略也是 HYPERLINK http:/ 貪心的。 有效實現Prim算法

14、的關鍵是設法較容易地選擇一條新的邊添加到由A的邊所形成的樹中，在下面的偽代碼中，算法的輸入是連通圖G和將生成的最小生成樹的根r。在算法執(zhí)行過程中，不在樹中的所有結點都駐留于優(yōu)先級基于key域的隊列Q中。對每個結點v，keyv是連接v到樹中結點的邊所具有的最小權值；按常規(guī)，若不存在這樣的邊則keyv=。域v說明樹中v的“父母”。在算法執(zhí)行中， HYPERLINK http:/.sg/xujia/mirror/ l GENERIC-MST GENERIC-MST的集合A隱含地滿足： A=(v,v)|vV-r-Q當算法終止時，優(yōu)先隊列Q為空，因此G的最小生成樹A滿足: A=(v,v)|v V-r (

15、a) (b) (c) (d) (e) (f) (g) (h) (i) 圖4.3 Prim算法在 HYPERLINK http:/.sg/xujia/mirror/ l fig1 圖4.1所示的圖上的執(zhí)行流程 MST-PRIM(G,w,r)1. QVG2. for 每個uQ3. do keyu4. keyr05. rNIL6. while Q7. do uEXTRACT-MIN(Q)8. for 每個vAdju9. do if vQ and w(u,v)keyv10. then vu11. keyvw(u,v)Prim算法的性能取決于我們如何實現優(yōu)先隊列Q。若 HYPERLINK http:/

16、用二叉堆來實現Q,我們可以使用過程BUILD-HEAP來實現第1-4行的初始化部分，其運行時間為O(V)。循環(huán)需執(zhí)行|V|次，且由于每次EXTRACT-MIN操作需要O(V)的時間，所以對EXTRACT-MIN的全部調用所占用的時間為O(VV)。第8-11行的for循環(huán)總共要執(zhí)行O(E)次，這是因為所有鄰接表的長度和為2|E|。在for循環(huán)內部，第9行對隊列Q的成員條件進行測試可以在常數時間內完成，這是由于我們可以為每個結點空出1位(bit)的空間來記錄該結點是否在隊列Q中，并在該結點被移出隊列時隨時對該位進行更新。第11行的賦值語句隱含一個對堆進行的DECREASE-KEY操作，該操作在堆上

17、可用0(V)的時間完成。因此，Prim算法的整個運行時間為O(VV+EV)=O(EV)，從漸近意義上來說，它和實現Kruskal算法的運行時間相同。 通過使用Fibonacci堆，Prim算法的漸近意義上的運行時間可得到改進。在 HYPERLINK http:/ Fibonacci堆中我們己經說明，如果|V|個元素被組織成Fibonacci堆，可以在O(V)的平攤時間內完成EXTRACT-MIN操作，在O(1)的平攤時間里完成DECREASE-KEY操作（為實現第11行的代碼），因此，若我們用Fibonacci堆來實現優(yōu)先隊列Q，Prim算法的運行時間可以改進為O(E+VV)。4.2.4背包問

18、題問題描述：設有一個容量為C的背包，n個物品的集合U=u1, u2, , un，物品ui的體積和價值分別為sj和vj，C, sj, vj都是正實數。在U中選擇物品裝入背包，使得裝入背包的物品總價值最大。設允許取每種物品的一部分裝入背包。 數學模型： z=max v1x1+ v2x2+ vnxn s1x1+ s2x2+ snxn=C 0= xi =yd2=ydn。 d=sort(y, n) for i=1 to n xi=0 /對x1.n初始化。 i=1; maxv=0; rc=C /以下rc表示當前背包的剩余容量。while rc0 and i=nj=di / uj為當前考慮選擇的物品 if

19、sj=rc then xj=1; rc=rc-sj /物品uj全部裝入背包。 else xj=rc/sj /選擇物品uj的一部分將背包填滿。 rc=0 end if maxv=maxv+vj*xji=i+1 end while return maxv, x1.nend GREEDY_KNAPSACK 算法的時間復雜性：(nlogn) (主要為排序的時間)43 參考代碼/* 活動選擇的問題 */templatevoid greedyselector(int n, type s 1, type f , bool a a 1 = true;int j = 1;for (int i=2;i=fj) a

20、i = true; j=i;else ai= false;/* Huffman編碼問題的設計和實現 */#include #include #include #define MAXLEN 100#define MAXVALUE 10000/* 結點結構定義 */typedef struct int weight; /*權值*/ int flag; /*標記*/ int parent; /*指向父結點的指針*/ int lchild; int rchild;HuffNode;/*Huffman 編碼結構*/typedef struct char bitMAXLEN; int len; int w

21、eight;Code;/* HuffTree 初始化 */void HuffmanInit(int weight, int n, HuffNode hufftree) int i; /* huffman結構初始化，n個葉結點的二叉樹有2n-1個結點 */ for(i = 0; i 2 * n - 1; i+) hufftreei.weight = (i n) ? weighti : 0; hufftreei.parent = -1; /*根，無父結點 */ hufftreei.flag = 0; hufftreei.lchild = -1; /* i不可能是某個結點的左子樹或右子樹*/ huf

22、ftreei.rchild = -1; /*建立權值為weight0.n-1的n個結點的HuffTree */void Huffman(int weight, int n, HuffNode hufftree) int i, j, m1, m2, x1, x2; HuffmanInit(weight, n, hufftree); /*初始化 */ /* 構造n - 1個非葉結點 */ for(i = 0; i n - 1; i+) m1 = m2 = MAXVALUE; /* m1 = m2 */ x1 = x2 = 0; for(j = 0; j n + i; j+)/*在森林中找兩個權值最

23、小的結點*/ if(hufftreej.flag = 0) /* 該結點未加入到huffman樹中 */ if(hufftreej.weight m1) m2 = m1; x2 = x1; m1 = hufftreej.weight; x1 = j; else if(hufftreej.weight m2) m2 = hufftreej.weight; x2 = j; hufftreex1.parent = n + i; hufftreex2.parent = n + i; hufftreex1.flag = 1; hufftreex2.flag = 1; hufftreen + i.weig

24、ht = hufftreex1.weight + hufftreex2.weight; hufftreen + i.lchild = x1; hufftreen + i.rchild = x2; /* huffman編碼函數 */void HuffmanCode(HuffNode hufftree, int n, Code huffcode) Code cd; int i, j, child, parent; for(i = 0; i n; i+) /* 求第i個結點的Huffman編碼 */ cd.len = 0; cd.weight = hufftreei.weight; child =

25、i; parent = hufftreei.parent; /* 準備往上爬 */ while(parent != -1) /* 不到?*/ cd.bitcd.len+ = (hufftreeparent.lchild = child) ?0 : 1; child = parent; parent = hufftreechild.parent; for(j = 0; j cd.len; j+) huffcodei.bitj = cd.bitcd.len - 1 - j; huffcodei.bitcd.len = 0; huffcodei.len = cd.len; huffcodei.wei

26、ght = cd.weight; /* 打印huffman編碼 */void PrintCode(Code c, int n) int i; printf(OutPut code :n); for(i = 0; i n; i+) printf(weight = %d code %sn, ci.weight, ci.bit);/* 測試程序 */void main(void) int w = 3, 1, 4, 8, 2, 5, 7; HuffNode huff100; Code hcode10; Huffman(w, 7, huff); HuffmanCode(huff, 7, hcode);

27、PrintCode(hcode, 7); getch();/ 圖的存儲結構以 數組鄰接矩陣表示, 用普里姆（Prim）算法構造圖的最小生成樹。#include #include #include #include #define TRUE 1#define FALSE 0#define NULL 0#define OVERFLOW -2#define OK 1#define ERROR 0typedef int Status;typedef int VRType;typedef char InfoType; /弧相關的信息typedef char VertexType10; /頂點的名稱為字符

28、串#define INFINITY 32767 /INT_MAX 最大整數#define MAX_VERTEX_NUM 20 /最大頂點數 typedef enumDG,DN,AG,AN GraphKind; /有向圖,有向網,無向圖,無向網typedef struct ArcCell VRType adj; / VRType 是頂點的關系情況,對無權圖用1或0表示有關系否,對帶權圖(網), / 則填權值。InfoType *info; / 指向該弧相關信息的指針。 ArcCell, AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM ;typedef struct

29、VertexType vexsMAX_VERTEX_NUM; / 頂點數據元素AdjMatrix arcs; / 二維數組作鄰接矩陣int vexnum, arcnum; / 圖的當前頂點數和弧數 GraphKind kind; / 圖的種類標志 MGraph;Status CreateGraph(MGraph &G, GraphKind kd)/ 采用數組鄰接矩陣表示法，構造圖G Status CreateDG(MGraph &G); Status CreateDN(MGraph &G); Status CreateAG(MGraph &G); Status CreateAN(MGraph

30、&G); G.kind=kd; switch(G.kind) case DG: return CreateDG(G); /構造有向圖G case DN: return CreateDN(G); /構造有向網G case AG: return CreateAG(G); /構造無向圖G case AN: return CreateAN(G); /構造無向網G default: return ERROR;/CreateGraphStatus CreateDG(MGraph &G)return OK;Status CreateDN(MGraph &G)return OK;Status CreateAG

31、(MGraph &G)return OK;Status CreateAN(MGraph &G)/構造無向網G int i,j,k;/char v3, w3 , vwinfo10= ; /邊有關信息置空 char v103=v1,v1,v2,v2,v5,v5,v6,v6,v4,v4; char w103=v2,v3,v5,v3,v6,v3,v4,v3,v1,v3;int q10= 6, 1, 3, 5, 6, 6, 2, 4, 5, 5 ; char vwinfo10= ; printf(輸入要構造的網的頂點數和弧數：n);/scanf(%d,%d,&G.vexnum,&G.arcnum);G.

32、vexnum=6; G.arcnum=10; printf(依次輸入網的頂點名稱v1 v2 .等等：n);/ for (i=0; iG.vexnum; i+) scanf(%s,G.vexsi);/構造頂點數據 strcpy(G.vexs0,v1); strcpy(G.vexs1,v2); strcpy(G.vexs2,v3); strcpy(G.vexs3,v4); strcpy(G.vexs4,v5); strcpy(G.vexs5,v6); for (i=0; iG.vexnum; i+) for (j=0; jG.vexnum; j+) G.arcsij.adj=INFINITY; G

33、.=NULL;/初始化鄰接矩陣 printf(按照： 頂點名1 頂點名2 權值 輸入數據:n); for (k=0; kG.arcnum; k+)/ scanf(%s %s %d,v,w,&q); for(i=0;iG.vexnum; i+) if(strcmp(G.vexsi,vk)=0) break;/查找出v在vexs中的位置i if(i=G.vexnum) return ERROR; for(j=0;jG.vexnum; j+) if(strcmp(G.vexsj,wk)=0) break;/查找出v在vexs中的位置j if(j=G.vexnum) return ERROR;G.ar

34、csij.adj=qk; /鄰接矩陣對應位置置權值G.arcsji.adj=qk; /鄰接矩陣對稱位置置權值G.=(char *)malloc(10); strcpy(G.,vwinfo);/置入邊有關信息 return OK;void PrintMGraph(MGraph &G)int i,j;switch(G.kind) case DG: for (i=0; iG.vexnum; i+) for (j=0; jG.vexnum; j+) printf( %d | ,G.arcsij.adj); if(G.=NULL) printf(NULL); else printf(%s路,G.); p

35、rintf(n); break; case DN: for (i=0; iG.vexnum; i+) for (j=0; jG.vexnum; j+) if(G.arcsij.adj!=0) printf( %d | ,G.arcsij.adj); else printf( | ); printf(n); break; case AG: for (i=0; iG.vexnum; i+) for (j=0; jG.vexnum; j+) printf( %d | ,G.arcsij.adj); printf(n); break; case AN: for (i=0; iG.vexnum; i+)

36、 for (j=0; jG.vexnum; j+) if(G.arcsij.adjINFINITY) printf( %d | ,G.arcsij.adj); else printf( | ); printf(n); return;Status MiniSpanTree_PRIM(MGraph G, VertexType u) int i, j, k, r, min;struct VertexType adjvex;VRType lowcost;closedgeMAX_VERTEX_NUM; /定義輔助數組/k=LocateVex(G,u);for(i=0;iG.vexnum; i+) if(

37、strcmp(G.vexsi,u)=0) break;/查找出v在vexs中的位置i if(i=G.vexnum) return ERROR; k=i;for(j=0; jG.vexnum; +j) /輔助數組初始化if(j!=k) strcpy(closedgej.adjvex,u); closedgej.lowcost=G.arcskj.adj;closedgek.lowcost=0; /初始, U=0, 即v1for(i=1; iG.vexnum; +i)/ k=mininum(closedge); /求權值最小的頂點 min=INFINITY; for(r=0; r 0 & closedger.lowcost %sn,k,closedgek.adjvex, G.vexsk); /輸出邊 closedgek.lowcost=0; /第頂點并入 U 集for(int j=0; jG.vexnum; +j) if(G.arcskj.adj closedgej.lowcost) /新頂點并入 U 集后,重新選擇最小邊 strcpy(closedgej.adjvex,G.vexsk); closedgej.lowcost=G.