演算法方式總覽 The Divide-and-Conquer Strategy (個各擊破)(binary Searching、Quick Sort…. ) The Greedy Method(貪婪演算法) (Prim MST、Kruskal MST、Djikstra's algorithm) Dynamic Programming(動態演算法)(矩陣連乘、最佳二元搜尋樹…) Tree Searching Strategy(圖論) Trace Back
貪婪演算法 (Greedy Algorithm) \\\ 以下，教務組的簡報， 預計將以30分鐘時間， 由我、與鄭惠珍館長、以及簡忠漢主任，分別代表教務處、圖書館、及電算中心， 向各位委員報告本校的概況。 [15sec/90，換頁]
貪婪演算法簡介 一種短視/近利/偷懶/貪婪的想法 每一步都不管大局，只求局部解決方法 它透過一步步的選擇局部最佳解來得到問題的解答。 它所做的每一個選擇是根據某種準則來決定的，而且前後次的決定並無關聯性。 它用來解決最佳化問題時，通常很有效率且簡單。 它並不能解決所有最佳化問題，例如：最短路徑問題。
貪婪演算法的演算過程 重複下列步驟直到找出解答為止： 選擇程序 你事先設計好一個挑選局部最佳解的規則，並用它來挑選下一個要加入解集合的項目。 可行性檢查 檢查新的解集合是否符合題目限制。 解答檢查 檢查新的解集合是否已經是正確的結果。
Example 問題：從n各數字中挑出k各數字出來且總合是 最大的。 想法: for i = 1 to k { }
選擇最短路徑 問題: 從V0到V3 找出一條最短路徑. 想法: 使用貪婪演算法 124 最短路徑:7
選擇最短路徑 問題: 從V0到V3 找出一條最短路徑. 1913 最短路徑:7 想法: 使用貪婪演算法
需要用動態演算法 (dynamic programming ) 來解決
零錢換整問題 問題: 要把 41 個 1 元硬幣兌換成 25 元, 18 元, 5 元, 1 元硬幣, 如何兌換可以讓最終的硬幣數最少? 貪婪演算法：每一步都不管大局, 只求這一步換掉越多 1 元硬幣越好。 用 greedy algorithm 解得 1 個 25 元, 0 個 18 元, 3 個 5 元, 1 個 1 元; 最佳解是 0 個 25 元, 2 個 18 元, 1 個 5 元, 0 個 1 元。
Minimum spanning trees (MST) 最小生成樹 Minimum spanning trees (MST)
無向圖的幾個定義 1 1 V1 V2 V1 V2 3 3 6 6 4 4 V3 V4 V3 V4 2 5 2 5 V5 V5 (a)一個無向連通權重圖G (b) 就算 (V4, V5) 移除，依然 是連通的。但若連 (V2, V4) 也移除，則變成不連通了。
無向圖的幾個定義 ‧簡單循環(simple cycle) 在無向圖中的一條至少包含三個頂點，且由其中某一 頂點出發、經過不同中點、最後回到該頂點的路徑。 ‧非環狀(acyclic) 在無向圖中找不到任何簡單循環，即如此稱之。 1 1 V1 V2 V1 V2 3 6 3 4 V3 V4 V3 V4 5 2 V5 V5 (c)G的生成樹 (非環狀圖) (d)G的最小生成樹 (非環狀圖)
最小生成樹 Minimum spanning trees (MST) Definition: G = (V, E): weighted connected undirected graph Spanning tree : S = (V, T), T E, undirected tree Minimum spanning tree(MST) : a spanning tree with the smallest total weight.
最小生成樹的定義 樹 (tree) ： 一個無向連通非環狀圖 (acyclic, connected, undirected graph) 有根樹 (rooted tree) ：以某個頂點為根的樹 (獨立於樹之外的頂點不能作為根)。 因此有根樹也被直接稱為樹。 生成樹 (spanning tree) ： 包含圖中所有頂點且符合樹的定義的連通子圖。 最小生成樹 (minimum spanning tree) ： 即具有最小weight的生成樹。
解最小生成樹的貪婪演算法 F = 空集合 //將 edge 集合初始化為空集合 while ( 當此問題未得解 ) { //選擇程序 //可行性檢查 if ( 將選出的edge加入 F 中不會產生任何 cycle ) 將選出之 edge 加入 F 中 ; //解答檢查 if ( T = ( V，F ) 是生成樹 ) 此問題得解 ; } 設計自己的規則
Prim 演算法 F = 空集合 //將edge集合初始化為空集合 Y = {V1} ; //將頂點集合初始化為僅包含V1 while ( 當此問題尚未得解 ) { 選擇 V-Y 中的某一個頂點且 //選擇程序 該點與Y有最近的距離之條件 ; //可行性檢查 將選出的頂點加入Y中 ; 將選出的edge加入F中 ; if ( Y == V ) //解答檢查 此問題得解 ; }
執行 Prim 演算法的過程 1 1 V1 V2 V1 V2 3 3 3 6 3 6 4 4 V3 V4 V3 V4 2 5 2 5 V5 欲找出一個最小生成樹 1. 首先選擇 V1
1 1 V1 V2 V1 V2 3 3 3 6 3 6 4 4 V3 V4 V3 V4 2 5 2 5 V5 V5 2. 選擇 V2，因為它最 接近 {V1} 3. 選擇 V3，因為它最 接近 {V1，V2}
1 1 V1 V2 V1 V2 3 3 3 6 3 6 4 4 V3 V4 V3 V4 2 5 2 5 V5 V5 4. 選擇 V5，因為它最 接近 {V1，V2，V3} 5. 選擇 V4，因為它最 接近 {V1，V2，V3，V4}
得到一個最小生成樹 1 V1 V2 3 4 V3 V4 2 V5
Time complexity : O(n2), n = |V|.
Kruskal 演算法 F = 空集合 ; //將edge集合初始化為空集合 於V中產生等同於頂點數目且互不交集的頂點子集合， 每個頂點子集合中僅有一個頂點 ; while ( 當此問題尚未得解 ) { 選擇下一個weight最小的邊線 ; //選擇程序 if ( 選出的邊線連接了兩個disjoint之子集合 ) { //可行性檢查 合併該兩子集合 ; 將選出之邊線加入 F 集合 ; } if ( 所有的頂點子集合都已經被合併 ) //解答檢查 此問題得解 ;
執行 Kruskal 演算法的過程 1 V1 V2 V1 V2 3 3 6 4 V3 V4 V3 V4 2 5 V5 V5 欲找出一個最小生成樹 產生互不交集的頂點子集合， 每個集合僅包含一個頂點。
1 1 V1 V2 V1 V2 V3 V4 V3 V4 2 V5 V5 2. 選擇邊線(V1，V2) 3. 選擇邊線(V3，V5)
1 1 V1 V2 V1 V2 3 3 V3 V4 V3 V4 2 2 V5 V5 4. 選擇邊線(V1，V3) 5. 選擇邊線(V2，V3) 會造成simple cycle， 故不選此邊線。
1 V1 V2 3 4 V3 V4 2 V5 6. 選擇邊線(V3，V4) 得到最小生成樹。
Time complexity: O(|E| log|E|)
課堂練習 請找出下面無向連通圖形的最小生成樹：
An example of Kruskal’s algorithm
An example for Prim’s algorithm
The 2-way merging problem # of comparisons required for the linear 2-way merge algorithm is m1+ m2 -1 where m1 and m2 are the lengths of the two sorted lists respectively. 2-way merging example 2 3 5 6 1 4 7 8 The problem: There are n sorted lists, each of length mi. What is the optimal sequence of merging process to merge these n lists into one sorted list ?
Extended binary trees An extended binary tree representing a 2-way merge
An example of 2-way merging Example: 6 sorted lists with lengths 2, 3, 5, 7, 11 and 13.
Time complexity for generating an optimal extended binary tree:O(n log n)
資料編碼 目的 固定長度二進位編碼 找出一個最有效率的方式來對資料檔案進行編碼，使得 檔案花費的儲存空間最少。 例如，欲對一字元集 {a,b,c} 進行編碼，可編成下面的碼： a : 00 b : 01 c : 11 則根據此編碼方式，若有一檔案內容為 ababcbbbc，則可 編碼為 000100011101010111 a b a b c b b b c 長度需要18個位元。
資料編碼 (續) 可變動長度二進位編碼 若檔案內容為 ababcbbbc 觀察得到 b 的出現頻率最高，故給它單獨一個 0 字碼， 則 a 不可用 00 編碼，因為會無法分清楚這是 a 或 b。 編碼方式為： a : 10 b : 0 c : 11 (4.2) 則上面檔案可被編碼為： 1001001100011 a b a b c bbb c 長度僅需13個位元。
前置碼 (Prefix Code) 前置碼 ‧是一種可變動長度二進位碼。 ‧每一個字元所屬的字碼都不能拿來當作別的字元的字碼 的起始位元。 例如： a : 01 ，則 011 不可拿來當作 b 的字碼， 因為 01 已經被 a 拿來當作字碼了。
前置碼 (Prefix Code) (續) 每一種前置碼均可用二元樹來表示之，樹葉即是要被編碼 的字元。 例如，(4.2) 的編碼方式： a : 10 b : 0 c : 11 對應的二元樹如下： 1 b 1 a c
前置碼 (Prefix Code) (續) 優點 解碼過程 ‧不需要檢查接下來的位元即可完成解碼。 ‧可非常容易的用二元樹表示編碼。 由檔案最左邊的位元與二元樹的根部開始解碼。 1.循序檢查檔案中每個位元，並同時在二元樹中根據該位元 2.為 0 或 1 來決定在樹中該往右下還是左下走。 3.走到樹葉時，就表示已經解出該葉子代表的字元。 4.再回到樹根，繼續檢查檔案的下一個字元。
解碼範例 編碼方式： a : 10 b : 0 c : 11 編碼內容： 010110 解出：bacb 1 b 1 a c
範例 有一字元集 {a,b,c,d,e,f}，每個字元在檔案中出現次數如下： 每種編碼方式所使用的位元數如下： 頻率 C1(固定) C2 C3(霍夫曼) a 16 000 10 00 b 5 001 11110 1110 c 12 010 110 d 17 011 01 e 100 11111 1111 f 25 101 每種編碼方式所使用的位元數如下： Bits(C1)=16(3)+5(3)+12(3)+17(3)+10(3)+25(3)=255 Bits(C2)=16(2)+5(5)+12(4)+17(3)+10(5)+25(1)=231 Bits(C3)=16(2)+5(4)+12(3)+17(2)+10(4)+25(2)=212 (最佳)
C2與C3(霍夫曼Huffman)對應二元樹 1 1 f:25 1 1 a:16 a:16 d:17 f:25 1 1 d:17 1 c:12 1 c:12 1 b:5 e:10 b:5 e:10 C2 編碼方式 C3(霍夫曼)編碼方式
霍夫曼編碼過程 (0) b:5 e:10 c:12 a:16 d:17 f:25 15 (1) c:12 a:16 d:17 f:25 1 1 b:5 e:10
(2) a:16 d:17 f:25 27 15 c:12 1 b:5 e:10 (3) f:25 27 33 1 15 c:12 a:16 d:17 1 b:5 e:10
(4) 33 52 1 1 a:16 d:17 f:25 27 15 c:12 1 b:5 e:10
(5) 85 1 33 52 1 1 a:16 d:17 f:25 27 15 c:12 1 b:5 e:10 到此為止，霍夫曼編碼完成。
0-1 背包問題 假設有 n 個物品，令： S = {item1，item2，...，itemn} wi = itemi 的重量 pi = itemi 的價值 W = 背包的最大載重 其中，wi、Pi、W均為正整數，找出子集合 A 使得：
貪婪解法範例 (1) 先拿價值最高的。 (2) 先拿重量最輕的。 (3) 先拿「價值/重量」比率最高的。 浪費5磅空間 最 大 載 重 30磅 20磅 $140 20磅 20磅 $60 $50 10磅 10磅 5磅 5磅 拿取順序：1，3，2。 背包 貪婪 解法 最佳解 物品1 物品2 物品3
Fractional 背包問題 在此問題中，物品是類似一袋金粉或銀粉之類可以只拿 部份的東西。 則應用先前的貪婪法則可以找到最佳解。