貪婪策略貪婪策略（Greedy Method）常用來解決最佳化問題（Optimization Problem） 貪婪法是最直接的解法， 。
每次的決策都是朝向目前“最好” 的方向前進，而且不回頭。
舉例來說，某一個銀行出納櫃檯要服務 n 個 顧客，銀行的目標是希望顧客在櫃檯等待的平均時間要最少。
解決之道 是每次都從尚未服務的顧客中，選擇需要服務時間最短的顧客來服務， 如此就可達到預期目標。
像這樣每次都選擇最小服務時間的策略就是一 種貪婪策略。
現在以實例說明此演算法。
假設有 5 個顧客 A，B，C，D，E 幾乎同時到 達銀行櫃檯，其所需服務時間如下表：顧客服務時 間A B C D E5 1 4 2 3根據貪婪演算法，銀行櫃檯將依序服務 B，D，E，C，A。
顧客在櫃檯等 待的平均時間為[1 + (1 + 2) + (1 + 2 + 3) + (1 + 2 + 3 + 4) + (1 + 2 + 3 + 4 + 5) ] / 5 = 7。
再介紹一個可用貪婪策略解決的背包問題（Knapsack Problem）。
假設 有多個可分解的物件和一只限重 W 的背包， 每件物件有其重量及其被選 取放入背包內的利益。
請問要如何將物件放進背包內而使得獲得的利益 最大？解決的方法是每次在限重的情形下， 選取尚未放入的物件中擁有 最大的利益與重量的比值之物件放入背包內。
設背包限重 100，有 A，B，C，D，E 共五個物件，其資料如下表：物件 A B C D E重量 10 20 30 40 50利益 20 30 66 40 60利益/重量 2.0 1.5 2.2 1.0 1.2因為物件 C 的利益/重量最高，所以將物件 C 放入背包內，此時背包的 重量為 30。
接著從物件 A，B，D，E 中挑出其利益/重量最高的物件 A 放入背包內，這時背包的重量為 30＋10＝40。
接下來，從物件 B，D，E 中挑出其利益/重量最高的物件 B 裝入背包內，之後背包的重量為 40+20=60。
再從剩下的物件 D 和 E 中選出其利益/重量最高的物件 E。
由 於物件 E 整個放入背包內會超過重量 100﹐所以物件 E 只能放入 0.8 個。
最後得到的利益為 66+20+30+60 放入以後得總重量為 60+50 0.8=100。
0.8=164。
物件裝入背包的情形整理於下表﹕物件個數 累計利益 累計重量C A B E1 1 1 0.866 86 116 16430 40 60 100接著介紹最小擴展樹（Minimum Spanning Tree）問題。
圖 22.5 是由頂 點（Vertex）及邊（Edge）構成的圖形，其中圓圈代表頂點，連接兩頂 點的線為邊，而且每個邊都有非負的加權（Weight）（例如頂點 V3 與頂 點 V5 間的邊之加權為 5）。
由於圖 22.5 的邊都無方向，稱圖 22.5 的圖 形為無向圖（Undirected Graph）。
定義無向圖的路徑（Path）為頂點 的序列，其中序列裏每個頂點與其後一個頂點之間必有邊相連。
例如圖 1 中[V1, V5, V2]是一條從頂點 V1 到頂點 V2 的路徑。
圖1 若無向圖的任兩頂點都存在一條路徑，則稱此圖為聯通圖（Connected Graph）。
例如圖 1 就是聯通圖。
從某頂點出發回到該頂點的路徑稱為 迴圈（Cycle）。
例如圖 1 的[V1, V5, V2, V1]路徑就是迴圈。
一個沒有迴 圈的圖形稱為無迴圈圖（Acyclic Graph）。
定義樹（Tree）為聯通的 無迴圈圖。
若圖形 G 的頂點所成的集合為 V， 邊所成的集合為 E， G=(V, 以 E)表示圖形 G。
定義圖形 G=(V, E)的擴展樹 T=(V, E’)是包括所有 G的頂點的樹，其中 E’是 E 的子集合。
例如圖 2(a)及(b)都是圖 1 的擴 展樹。
圖2 定義擴展樹 T=(V, E)的加權為集合 E’中所有的邊的加權的總和。
例如 圖 2 (a)的擴展樹加權為 1+3+5+7=16，而 2 (b) 的擴展樹加權為 1+2+3+6=12。
圖形 G 的最小擴展樹就是擁有最小加權的擴展樹。
如圖 2 (b) 的擴展樹是圖 1 的最小擴展樹。
最小擴展樹問題就是去求出給定的聯通 且加權的無向圖之最小擴展樹。
接著介紹以貪婪策略設計的 Kruskal 演算法。
假設要求圖形 G=(V, E) 的最小擴展樹。
此演算法依據邊的加權由小到大的順序考慮該邊是否為 最小擴展樹的邊。
若邊 e 加入後不會產生迴圈，則邊 e 為最小擴展樹的 一員；反之，邊 e 就不是最小擴展樹的一員。
如此重複直到建構出最小 擴展樹。
詳細的步驟分述於下：步驟 1： 將圖形 G=(V, E)所有的邊依其加權由小到大排好， 依序為 e1, e2, e3, …, em。
步驟 2：建立圖形 T=(V, E’)，其中 E’ = 。
設 i = 1。
步驟 3： ei 加入圖形 T 中不產生迴圈， 若 則將 ei 加入圖形 T， E’= E’ 即 ? { ei }；否則，i = i + 1。
步驟 4：若圖形 T 不是圖形 G 的擴展樹，則重複步驟 3；否則，圖形 T 是圖形 G 的最小擴展樹，結束演算法執行。
圖3 用(a, b)表示頂點 a 與頂點 b 的邊。
以找圖 1 的最小擴展樹為例，將圖 1 的邊依加權排序後得 e1 =(V1, V5), e2 =(V2, V3), e3 =(V2, V5), e4 =(V1, V2), e5 =(V3, V5), e6 =(V1, V4), e7 =(V4, V5), e8 =(V3, V4)。
一開始 圖形 T 只有頂點但沒有邊（圖 3 (a)）。
考慮 e1 =(V1, V5)，因不產生 迴圈，就將(V1, V5)加入 T 內（圖 3 (b)）。
同樣的， e2 =(V2, V3)及 e3 =(V2, V5)也依序加入 T 內（圖 3(c)和(d)）。
當考慮 e4 =(V1, V2)時， 因加入後會產生[V1, V5, V2, V1]的迴圈，所以拒絕(V1, V2)的加入（圖 3 (e)）。
同樣的理由，也拒絕 e5 =(V3, V5)的加入（圖 3(f)）。
而後 因 e6 =(V1, V4)加入 T 後不產生迴圈， 所以將(V1, V4)加入 T 中 （圖 3(g)） 。
此時 T 為 G 的擴展樹， 停止演算法。
最後得到的圖 3(g)就是圖 1 的最小 擴展樹。
最後介紹最短路徑問題（Shortest Path Problem）。
下圖是 S、A、B、 T 四個地點的交通路線，各路線分別標上距離：假設要求從 S 到 T 的最短路徑長度。
D(a,b)表示從 a 到 b 的最短路徑 令 長度。
從上圖﹐可知 D(S,T)=D(S,A)+D(A,B)+D(B,T)=10+15+20=45。
如此只要利用貪婪策略就能得到答案。
但是此貪婪策略並不適用於所有的 最短路徑問題，例如要找下圖的 D(S,T)，則 D(S,T)=24+20=44，此結果 不等於 D(S,A)+D(A,B)+D(B,T)=45。
郵票問題如何買到最少的郵票數 1.計算 99 元可買幾張 50 元最貴的郵票 (1 張) , 然後剩下多少 錢. (餘 49 元)2.計算 49 元可買幾張 25 元次貴的郵票 (1 張) , 然後剩下多少錢. (餘 24 元) 3.計算 24 元可買幾張 10 元再次貴的郵票 (2 張) , 然後剩下多少錢. (餘 4 元) 4.計算 4 元可買幾張 5 元再次貴的郵票 (0 張) , 然後剩下多少錢. (餘 4 元)5.計算 4 元可買幾張 1 元再次貴的郵票 (4 張) , 然後剩下多少錢. (餘 0 元) 附註:1.由最貴的郵票先買 2.當錢數為 0 整時停止 動畫:The Stamp ProblemPrim用 Prim's 的方法找到最小擴展樹 1.由 A 點為起點 , v 為所有點的集合 , x={A} ; y= v-x={B,C,D,E,F}2.找出以 A 點為起點而相鄰的最短路徑 (18--D 點) , 連接 A 點 D 點 , 將 D 點放入 x 中 , y={B,C,E,F} 3.以 D 點為起點找出相鄰的最短路徑 (6--E 點) ,連接 D 點 E 點 , E 點放入 x 中 , y={B,C,F} 4.以 E 點為起點找出相鄰的最短路徑 (5--F 點) ,連接 E 點 F 點 , F 點放入 x 中 , y={B,C} 5.以 F 點為起點找出相鄰的最短路徑 (10--D 點) , 但 D 點 E 點 F 點 形 成一個迴圈, 故退回到 E 點 6.以 E 點為起點找出相鄰的最短路徑 (11--C 點) ,連接 E 點 C 點 , C 點放入 x 中 , y={B} 7.以 C 點為起點找出相鄰的最短路徑 (14--D 點) , 但 C 點 D 點 E 點 形 成一個迴圈, 故退回到 E 點 8.以 E 點為起點找出相鄰的最短路徑 (16--B 點) , 連接 E 點 B 點 , 將 B 點放入 x 中 , y={} 9.當 y 為空集合時, 此圖為最小擴展樹 將 將 將動畫:The Prim's Method to Find a Minimal Spanning TreeKruskal用 Kruskal's 的方法找到最小擴展樹 1.找出所有邊的最小值 (5) , 並連接兩點 (E 點 F 點) 2.找出所有邊的次小值 (6) ,並連接兩點 (D 點 E 點) 3.找出所有邊的再次小值 (10) , 但 D 點 E 點 F 點為一個迴圈 , 故此 邊線不連接 4.找出所有邊的次小值 (11) ,並連接兩點 (C 點 E 點) 5.找出所有邊的再次小值 (14) , 但 C 點 D 點 E 點為一個迴圈 , 故此 邊線不連接6.找出所有邊的次小值 (16) ,並連接兩點 (B點 E點)7.找出所有邊的次小值 (18) ,並連接兩點 (A點 D點)8.當所有的點都有連線 , 則此圖為最小擴展樹動畫:The Kruskal's Method to Find a Minimal Spanning Tree。