貪婪演算法

零錢換整問題

問題: 要把 n 個 1 元硬幣兌換成 50 元, 10 元, 5 元, 1 元硬幣, 如何兌換可以讓最終的硬幣數最少?

愚公移山的想法 (exhaustive search): 把各種硬幣的各種組合都試過一次, 逐一檢查其和是否為 n, 並記錄符合條件的組合各用了多少個硬幣, 再找出最佳答案。

動態規劃的想法: 用愚公移山法解的過程中, 不同的子問題是否用到共同的孫問題答案?

Greedy algorithm -- 短視/近利/偷懶/貪婪的想法: 每一步都不管大局, 只求這一步換掉越多 1 元硬幣越好。

  1. x0 = floor(n / 50); n = n % 50;
  2. x1 = floor(n / 10); n = n % 10;
  3. x2 = floor(n / 5) ; x3 =n % 5 ;

則 "x0 個 50 元, x1 個 10 元, x2 個 5 元, x3 個 1 元" 即為答案。

同樣是零錢換整問題, 如果可換硬幣的面額改成 25 元, 18 元, 5 元, 1 元, 則 greedy algorithm 所求出的就不是最佳解了。 例: n = 41, 用 greedy algorithm 解得 1 個 25 元, 0 個 18 元, 3 個 5 元, 1 個 1 元; 但最佳解其實是 0 個 25 元, 2 個 18 元, 1 個 5 元, 0 個 1 元。 (真的有學者 做類似的建議。) Q: 有沒有什麼規則可以看出 "零錢換整問題" 何時可以用 greedy algorithm?

Huffman Encoding

問題: 如何壓縮檔案?

想法: 用 ASCII 碼儲存檔案很浪費空間, 因為有些字母 (例如 e, s, t) 出現頻率很高, 有些字母出現頻率很低, 但卻使用相同的 bit 數。 如果能對所有字母重新編碼, 用比較少的 bit 表示出現次數高的字母, 用比較多的 bit 表示出現次數低的字母, 應該可以用比較小的檔案儲存相同豐富的資訊。

但這會遇到一個問題: 如果每個字母的編碼數不固定, 到時解碼如何知道應斷在何處? 如果採用的是 prefix code 就不會有困擾了。 所謂 prefix code, 指編碼必須滿足下列特性: 任何兩字元的編碼, 必然不會出現其中一者是另一者前段的狀況。 例如有 "0110" 就不會有 "011" 也不會有 "011010" (有 "洪朝貴" 就不會有 "洪朝" 也不會有 "洪朝貴仔" -- 比方啦。) 這類編碼其實應該稱為 prefix-free code 這裡的 free, 既不是 「免費」, 也不是 「自由」, 而是 「沒有」 的意思。 但一般書籍大多稱之為 prefix code。

演算法: 把所有字母視為一棵 binary tree 的 leaves (external nodes), 根據下列步驟建出完整的樹。

  1. 每次取出出現頻率最低的兩個 nodes, 為它們加上一個共同的 parent node。 這個 parent node 的頻率就以兩個 children 的頻率之和來表示。
  2. 把這個 parent node 放回去, 重複以上步驟。 因為每次取走兩個 nodes, 放回一個 node, 所以執行 n-1 次 (n 為字母個數) 後, 只剩一棵大樹, 包含所有的 nodes。
  3. 每個分支的左右各以 0 與 1 表示其編碼; 每個字母 x (皆為 external nodes) 的編碼可從 root 到 x 的路徑上所遇到的樹枝編碼讀出。

「取出頻率最低的兩個 nodes」這個動作, 最適合用 heap 來實作。 請見 程式 與 執行結果。

正確性:

  1. Greedy Choice Property: 確實存在 "以最少見兩碼為兄弟" 的最佳編碼。 注意此處的邏輯。 同一個問題, 可能可以有很多組不同的最佳編碼。 我們只需要證明 Huffman Encoding 編出來的是其中之一即可。
  2. Optimal Substructure Property: 從 "小心挑選的小一號問題的最佳編碼" 適當修改來的編碼, 必為原問題的最佳編碼。 注意此處的邏輯。 這樣的方向, 等一下才能用數學規納法。 有些講義寫顛倒了...

GCP 的證明, 請見: Rashid Bin Muhammad 與 Michael Mascagni; OSP 的證明, 請見: Leila Kalantari 或參考書目當中的 C.L.R.S. 。

結論

Greedy algorithm 貪婪演算法 的精神: "今朝有酒今朝醉" 每一步面臨選擇時, 都做眼前最有利的選擇, 不考慮對將來是否有不良的影響。

當然很多 combinatorial optimization problems 都可以試著用 greedy algorithm 去解; 但最大的問題在於: 這樣子找出來的解是否真的是最佳解? 大部分時候, 眼前的利益與長遠的利益並不相等; 但有少數問題可以經由證明顯示 「每一步都選眼前最有利的部分解答, 則最後所得的結果正是全盤考慮下最有利的解答」。

我的心得: 有很多問題都可以用蠻力解決。 特別是計算量大的問題, 通常用遞迴的方式寫, 程式看起來會很簡單。 (雖然執行起來可能要很久) 如果你發現遞迴過程當中, 有很多子問題根本在重複計算相同的東西, 浪費時間, 那麼這個問題可能可以用動態規劃來解。 這樣的程式, 速度會快很多, 但稍微難想。 如果你運氣好, 遇到的問題具有某些特性, 不必把所有可能性嘗試一遍, 只需要在每一步都做當下最有利的選擇, 那麼就可以用貪婪演算法解決。 這樣的程式, 速度最快, 寫起來也很簡單; 但是 「每一步都短視近利, 最後會得到整體的最佳解」 這件事是需要證明的, 通常不見得很好想。 所以本講義的編排, 先談遞迴, 次談動態規劃, 最後才談貪婪演算法; 可能和一般演算法書籍的順序不太一樣。

作業

  1. 上題可否用 dynamic programming 解?
  2. 試用 greedy algorithm 解上個單元的 fractional knapsack problem。

更多參考資料

  1. CCS3 at Los Alamos National Lab
  2. Graham Gough
  3. Michael Mascagni
  4. Eitan Gurari
  5. Steven Halim