Quartz 5

貪婪演算法

Properties1
tagsalgorithm, clrs, paradigm, greedy

7 min read

🎯 什麼情境該想到我

當你「覺得『每步都選當下最好的』應該就對了」的時候。
★ 這個直覺經常是錯的，而且錯得很安靜。 所以這頁一半的篇幅在講怎麼證明它是對的。

⚙️ 怎麼用（兩個條件與兩種證明）

★ 兩個必要條件

條件意思
① 貪婪選擇性質局部最佳的選擇，可以導向全域最佳解（不需要回頭考慮其他選擇）
② 最佳子結構做完一個選擇後，剩下的仍是同型的子問題（與 動態規劃 共用這一條）

和 DP 的關係：

貪婪 ⊂ DP 能解的問題。
DP 在每一步考慮所有選擇再取最佳；貪婪直接鎖定一個選擇不回頭。
所以貪婪更快更省，但需要更強的條件——而那個條件必須被證明。

★ 怎麼證明貪婪是對的（這才是重點）

方法一：交換論證（exchange argument）—— 最常用

假設存在一個最佳解 OPT，它和貪婪解 G 在第一個不同的地方是位置 k。
證明：可以把 OPT 在位置 k 的選擇「換成」G 的選擇，
     而解的品質不會變差。
→ 反覆交換，把 OPT 變成 G，且品質始終不變
→ ★ 所以 G 也是最佳解。

方法二：歸納法 / 「貪婪保持領先」
證明貪婪在每一步都不劣於任何其他解。

★ 沒有證明就不要用貪婪。
「看起來很合理」在貪婪問題上失敗率極高——見下面的反例。

★ 經典正例與它們的證明關鍵

問題貪婪策略為什麼對
活動選擇／區間排程按結束時間排序，能選就選交換論證：最早結束者留給後面最多空間，換進來不會更差
Huffman 編碼每次合併頻率最小的兩個交換論證：最小的兩個必定在最深層且互為兄弟
Kruskal 最小生成樹按邊權排序，不成環就加割性質（cut property）：任一割的最小邊必在某棵 MST 中
Prim 最小生成樹從樹長出去，取最小的跨邊同上
Dijkstra 最短路徑每次取距離最小的未訪點★ 非負權保證「取出即最終」
分數背包按單位價值排序，裝滿為止可以切割 → 交換論證成立

★ 經典反例（貪婪失敗的地方）

① 0-1 背包（不能切割）

容量 10
物品 A: 重 6, 值 30   → 單位價值 5.0
物品 B: 重 5, 值 20   → 單位價值 4.0
物品 C: 重 5, 值 20   → 單位價值 4.0

貪婪（按單位價值）：先拿 A（重 6）→ 剩 4，B、C 都放不下 → 總值 30
★ 最佳解        ：B + C（重 10）                      → 總值 40

「可以切割」與「不能切割」差一個字，就從貪婪可解變成必須 DP。

② 硬幣找零

幣值 {1, 3, 4}，要湊 6
貪婪：4 + 1 + 1 = 3 枚
★ 最佳：3 + 3     = 2 枚

⚠️ 台幣與美元的幣值系統剛好讓貪婪成立（它們是「正則」幣值系統），
所以日常經驗會誤導你以為貪婪永遠對。 換一組幣值就錯。

③ 有負權時的 Dijkstra 最短路徑 —— 見該頁的反例。

實務上的貪婪

場景說明
排程最短作業優先（SJF）最小化平均等待時間
快取淘汰LRU / LFU 是貪婪啟發式（不保證最佳，最佳需要未來資訊）
資源分配裝箱問題的 first-fit / best-fit —— 是 近似演算法，不是最佳解
壓縮Huffman

★ 實務上很多「貪婪」其實是啟發式（heuristic），不保證最佳。
這沒關係——但你要知道它不保證，而不是以為它最佳。

🧪 我實際套用的紀錄

  • （待填）

⚠️ 注意 / 什麼時候不適用

  • ★ 最大的風險是「錯了不會報錯」。貪婪會給你一個看起來合理的答案，你可能永遠不知道它不是最佳。
    → 驗證方法：小規模時用暴力搜尋或 DP 算出真正的最佳解，比對。
  • ★ 排序的依據是關鍵。區間排程按「結束時間」對、按「開始時間」或「長度」都錯。換一個排序鍵就是完全不同的演算法。
  • 「不能切割」通常會讓貪婪失效 → 改 動態規劃。
  • 貪婪對輸入順序敏感時就是警訊——正確的貪婪應該在排序後有確定的結果。
  • NP-hard 問題上的貪婪是近似不是最佳，要講清楚近似比（見 近似演算法）。
  • 面試時一定要說明「為什麼貪婪是對的」，直接給演算法不給論證是扣分的。

🔗 相關工具

Graph View

Backlinks