講師:郭育倫 d95037@csie.ntu.edu.tw 第12章貪婪演算法 講師:郭育倫 d95037@csie.ntu.edu.tw 演算法導論，探矽工作室.

Presentation on theme: "講師:郭育倫 d95037@csie.ntu.edu.tw 第12章貪婪演算法 講師:郭育倫 d95037@csie.ntu.edu.tw 演算法導論，探矽工作室."— Presentation transcript:

1 講師:郭育倫 d95037@csie.ntu.edu.tw
第12章貪婪演算法 講師:郭育倫 演算法導論，探矽工作室

2 演算法導論，探矽工作室 本章學習重點 機器排程 0/1背包問題 拓樸排序 霍夫曼碼

3 最佳化問題(optimization problem)
演算法導論，探矽工作室 最佳化問題(optimization problem) 定義 很多問題常常存在許多的解答，而每個解答相對地也可以有一個數值，不過，我們希望能找出一個有最佳數值（最大值或最小值）的解答，稱為最佳解(之一) 範例 每天可在最少時間做最多的事 網路的速度越快越好 ….

4 貪婪演算法概述 在解決最佳化問題的過程中，通常是經過一個序列的步驟，而且在每個步驟中會有一群選擇
演算法導論，探矽工作室 貪婪演算法概述 在解決最佳化問題的過程中，通常是經過一個序列的步驟，而且在每個步驟中會有一群選擇 在所有解決最佳化問題的演算法中，貪婪演算法是最直覺的一種方法 方法 設定一個特定的選擇規範，稱為貪婪準則，以便在每一個步驟中做出目前看起來最好選擇，即局部最佳解 一旦做出了選擇，就不再更改，並希望這樣的選擇可以得到全域的最佳解 在一般情況下，其結果大多是非常接近最佳解。 是有效率的方法，但是並不保證永遠可得到(全域)最佳解

5 機器排程 問題描述 有n件工作和無限多台機器，每件工作可在任一機器上得到處理。
演算法導論，探矽工作室 機器排程 問題描述 有n件工作和無限多台機器，每件工作可在任一機器上得到處理。 假設每件工作的開始時間為si，完成時間為fi，而si<fi，[si,fi]便為處理工作i時所經歷的時間區間。 兩件工作i和j重疊是指兩個工作的時間區間有重疊，例如區間[1,5]和區間[2,4]重疊，但是和區間[5,7]就不算重疊。 一個可行的工作分配是指，沒有任何兩件或兩件以上重疊的工作分配給同一台機器。因此，在可行的工作分配中，每台機器在任何時刻最多只處理一個工作 最佳的分配是指使用最少機器的可行方案，即為最佳解。

6 貪婪準則 每次分配一件工作，而且按照每件工作的開始時間為次序來進行工作分配 選擇機器的準則
演算法導論，探矽工作室 貪婪準則 每次分配一件工作，而且按照每件工作的開始時間為次序來進行工作分配 選擇機器的準則 根據欲分配工作的開始時間，若此時有舊的機器可用，則將工作分配給舊的機器，否則就將任務分配給一台新的機器

7 貪婪演算法 先依照工作的開始時間對每個工作做排序，開始時間較早的為優先 依次取出每一件工作 時間複雜度:Ο(n2)
演算法導論，探矽工作室 貪婪演算法 先依照工作的開始時間對每個工作做排序，開始時間較早的為優先 依次取出每一件工作 若有舊機器登記的執行時間在此工作的開始時間之前，則將工作分配給舊的機器，並更新該機器的執行時間為此工作的結束時間 否則就將任務分配給一台新的機器，並更新該機器的執行時間 時間複雜度:Ο(n2) 步驟1的排序需要Ο(nlogn) 步驟2需要Ο(n2)

8 演算法導論，探矽工作室 機器排程之範例

9 演算法導論，探矽工作室 機器排程範例之長條圖

10 0/1背包問題（0/1 knapsack problem）
演算法導論，探矽工作室 0/1背包問題（0/1 knapsack problem） 問題描述 有個小偷帶一個背包到某家商店偷東西，他找到n個商品，第i個商品價值Vi元，重Wi公斤，而他帶的背包最多只能裝C公斤的物品，其中Vi、Wi、C都是整數 他的背包應該怎麼裝才能帶走最有價值的商品？ Why 0/1 ? 每個商品不是被拿走就是被留著這兩種狀況，而且每個商品不能被切割（如拿1/3個），也不能被拿超過一次

11 演算法導論，探矽工作室 數學表示式 在以下的限制條件之下 取得 的最大值

12 第一種貪婪準則 從剩餘的商品中，選出可以裝入背包其價值最大之商品 也就是 不能保證永遠得到最佳解！！ 範例
演算法導論，探矽工作室 第一種貪婪準則 從剩餘的商品中，選出可以裝入背包其價值最大之商品 也就是 在有足夠容量的條件下，價值最高的商品首先被裝入背包，然後是下一個價值最高的商品，以此類推 不能保證永遠得到最佳解！！ 範例 考慮n=3，W={100,10,10}，V={20,15,15}，C=105 採用這個貪婪準則時，我們得到的解為X={1,0,0}，而總價值為20。 而此範例的最佳解卻是X={0,1,1}，總價值為30

13 第二種貪婪準則 從剩下的商品中，選擇可裝入背包其重量最小的商品 不保證在任何情況下都可以得到最佳解！！ 範例
演算法導論，探矽工作室 第二種貪婪準則 從剩下的商品中，選擇可裝入背包其重量最小的商品 不保證在任何情況下都可以得到最佳解！！ 範例 考慮n=2，W={10,20}，V={5,100}，C=25 以此準則得到的解為X={1,0}，但是其最佳解應該為X={0,1}

14 貪婪演算法 依貪婪準則的不同，分別對商品的價值或重量作排序，價值較高或重量較輕的商品為優先。 依次考慮每件商品 時間複雜度:Ο(nlogn)
演算法導論，探矽工作室 貪婪演算法 依貪婪準則的不同，分別對商品的價值或重量作排序，價值較高或重量較輕的商品為優先。 依次考慮每件商品 若加上該商品的重量不超過背包最多可裝的重量C，則將該商品放入，並累加目前背包已裝商品的總重量 否則該商品不裝入背包 時間複雜度:Ο(nlogn) 步驟1的排序需要Ο(nlogn) 步驟2需要Ο(n)

15 分析與比較 保證可以得到(全域)最佳解的一個方法
演算法導論，探矽工作室 分析與比較 保證可以得到(全域)最佳解的一個方法 每樣商品都有裝入和不裝入兩種狀況，因此n個商品就有2n種狀況，再對這個狀況選取值不大於C之最大值的解，就是一個最佳解 時間複雜度:Ο(2n) 0/1背包問題屬於NP-Hard 雖然貪婪演算法對0/1背包問題不保證可以得到最佳解，但它卻是利用直覺方式計算出非常近似最佳解的解答 約有40%的機率可以得到最佳解，97%的機率可以跟最佳解相差在10%之內 時間複雜度只需要 Ο(nlogn)

16 拓樸排序 問題描述 範例 從一群有先後順序的任務中，找出一個包含所有任務的序列 種樹的工作可分成挖土、放樹苗、填土，具有先後順序
演算法導論，探矽工作室 拓樸排序 問題描述 從一群有先後順序的任務中，找出一個包含所有任務的序列 範例 種樹的工作可分成挖土、放樹苗、填土，具有先後順序 順序<挖土,放樹苗,填土>代表成功 順序<挖土,填土,放樹苗>, 以及<填土,挖土>代表失敗

17 頂點作業網路(AOV網路) 用一有向圖代表這類問題 根據有向圖來找出先後順序之過程，即稱為拓樸排序（topological sorting）
演算法導論，探矽工作室 頂點作業網路(AOV網路) 用一有向圖代表這類問題 頂點代表任務 有向邊代表任務間的先後順序 根據有向圖來找出先後順序之過程，即稱為拓樸排序（topological sorting） 找出包含所有頂點先後順序的序列，則稱為拓樸序列（topological orders ）

18 代表有執行先後順序的任務之有向圖 （AOV網路）
演算法導論，探矽工作室 代表有執行先後順序的任務之有向圖 （AOV網路）

19 貪婪準則 由左到右逐步建立先後順序的序列S 每一步驟都在排好的序列S中加入一個頂點w 用來選擇頂點的貪婪準則
演算法導論，探矽工作室 貪婪準則 由左到右逐步建立先後順序的序列S 每一步驟都在排好的序列S中加入一個頂點w 用來選擇頂點的貪婪準則 從剩下的頂點中選擇頂點w，其中不存在有向邊(u,w)，而且頂點u不在已經排好的序列S中

20 搭配的資料結構 一個一維陣列S來記錄拓樸序列 一個堆疊或佇列Candidate（可稱為候選表）來記錄每一步驟中的候選頂點
演算法導論，探矽工作室 搭配的資料結構 一個一維陣列S來記錄拓樸序列 一個堆疊或佇列Candidate（可稱為候選表）來記錄每一步驟中的候選頂點 一個一維陣列InDegree來記錄每一步驟中每個頂點進入邊的個數 InDegree[i]表示有向邊(u,i)的個數，即頂點i進入邊的個數，其中u頂點還沒放入拓樸序列S中 當InDegree[i]為0時，表示要在頂點i之前完成的頂點工作都完成了，因此頂點i就可成為候選頂點以放入候選表序列Candidate中。

21 貪婪演算法 先統計每個頂點的進入邊個數InDegree，並將沒有進入邊的候選頂點放入Candidate中。
演算法導論，探矽工作室 貪婪演算法 先統計每個頂點的進入邊個數InDegree，並將沒有進入邊的候選頂點放入Candidate中。 當還有候選頂點的時候，從Candidate中取出一候選頂點w放入序列S，調整拿掉頂點w後有向圖之狀況，包括InDegree以及Candidate之改變。 重複步驟2，直到沒有候選頂點為止。 序列S中包含的頂點個數，若等於有向圖的頂點個數，即表示成功，否則為失敗。 時間複雜度 用相鄰矩陣來表示有向圖：Ο(n2) 用鏈結串列來表示有向圖：Ο(n+e)

22 範例（以AOV網路圖為例） 首先有一個空的序列S=〈〉
演算法導論，探矽工作室 範例（以AOV網路圖為例） 首先有一個空的序列S=〈〉 選擇序列S的第一個頂點，此時在有向圖有兩個候選頂點A和B，若我們選擇B，則序列S=〈B〉 選擇序列S的第二個頂點，依貪婪準則可得候選頂點A和E，若選擇E，則得序列S=〈BE〉 只有一個候選頂點A，因此把頂點A加入序列S，所以序列S=〈BEA〉 頂點C是唯一的一個候選頂點，因此序列S=〈BEAC〉 加入唯一的候選頂點D，得到序列S=〈BEACD〉 最後加入頂點F，就可以得到一個序列解S=〈BEACDF〉

23 霍夫曼碼（Huffman code） 檔案的壓縮演算法分類 霍夫曼碼 可恢復性 不可恢復性
演算法導論，探矽工作室 霍夫曼碼（Huffman code） 檔案的壓縮演算法分類 可恢復性 沒有失真的問題，適合用於資料性質的一般檔案 不可恢復性 有失真的問題，但是通常其壓縮率會比較好 適合用於多媒體檔案，例如JPEG、MPEG等 霍夫曼碼 以檔案中每個字元出現的頻率（次數）多寡，作為壓縮的依據 壓縮率通常介於20%到90%之間

24 壓縮文字檔案之範例 二元字碼（binary character code）法 分類 將其中每個字元以一個唯一的二元字串來解決 固定長度碼
演算法導論，探矽工作室 壓縮文字檔案之範例 二元字碼（binary character code）法 將其中每個字元以一個唯一的二元字串來解決 分類 固定長度碼 代表每個字元的字碼（codeword）之長度相同 例如文字檔只包含a~f六個字元，22<6<23，則字碼長度為3，令字碼000代表a，字碼001代表b，…. 不固定長度碼 給予較常出現的字元較短的字碼，較不常出現的字元給予較長字碼，以此來獲得較佳的壓縮結果 例如文字檔中字元a出現的頻率最高，令字碼0代表a

25 演算法導論，探矽工作室 字元編碼範例

26 以二元樹（binary tree）模型來代表二元字碼的編碼與解碼
演算法導論，探矽工作室 以二元樹（binary tree）模型來代表二元字碼的編碼與解碼 葉子代表某個字元 而一個字元的二元字碼，可以由二元樹樹根到該字元葉子的路徑來表示 其中0代表二元樹節點的「左子節點」，1則代表「右子節點」

27 字元編碼的二元樹範例：(a)固定長度字碼方式，(b)可變長度字碼方式
演算法導論，探矽工作室 字元編碼的二元樹範例：(a)固定長度字碼方式，(b)可變長度字碼方式

28 演算法導論，探矽工作室 壓縮檔的最佳碼 一個檔案的一個最佳碼永遠使用一棵接近完整二元樹（almost complete binary tree）來表示，即每個內部節點都剛好有兩個子節點 若一棵接近完整二元樹有N個葉子，則表示它有N-1個內部節點。 對於字元表C中的每個字元c而言，假設f(c)代表在檔案內c的頻率，d(c)代表在二元樹內葉子c的深度，也就是字元c的字碼之長度，則對該檔案編碼後所需的位元數目為：

29 貪婪準則 霍夫曼碼是以建立霍夫曼二元樹的方法得到 準則 相對於二元樹的觀點 字元發生頻率越高者，以越短的二元字串來表示之
演算法導論，探矽工作室 貪婪準則 霍夫曼碼是以建立霍夫曼二元樹的方法得到 準則 字元發生頻率越高者，以越短的二元字串來表示之 相對於二元樹的觀點 頻率越高的字元其相對應之葉子，離樹根越近，頻率越低的則越遠。 二元樹的建立步驟，就是先合併頻率越低的字元

30 貪婪演算法(霍夫曼演算法) 依照每個字元出現的頻率，建立一個最小優先權佇列Q。
演算法導論，探矽工作室 貪婪演算法(霍夫曼演算法) 依照每個字元出現的頻率，建立一個最小優先權佇列Q。 從Q中取出頻率最小的兩個節點（包括葉子），分別當作新節點的左邊和右邊的子節點，並將兩個子節點代表的頻率加起來，作為新節點的頻率，最後再將新節點加入Q中。 重複步驟2，直到Q中只有一個節點，即二元樹的樹根。 尋訪二元樹（binary tree traversal），並依照經過的路徑，建立每個字元代表之字碼。 時間複雜度:Ο(nlogn) 步驟1:Ο(n) 步驟2,3: Ο(logn) × (n-1) 步驟4:Ο(n)

31 演算法導論，探矽工作室 霍夫曼貪婪演算法的步驟範例(1/2)

32 演算法導論，探矽工作室 霍夫曼貪婪演算法的步驟範例(2/2)

33 結論 瞭解機械排程、0/1背包問題、拓樸排序、霍夫曼碼等問題，及相對應的貪婪演算法
演算法導論，探矽工作室 結論 瞭解機械排程、0/1背包問題、拓樸排序、霍夫曼碼等問題，及相對應的貪婪演算法 貪婪演算法並不保證永遠可以得到最佳解，但是它仍是一個有效率的演算法，而且在很多時候也可以得到最佳解，或者得到跟最佳解相去不遠的解。