貪婪演算法核心思想與經典案例解析

貪婪演算法核心思想與經典案例解析

貪婪演算法 是一種在每一步決策中都選擇當前狀態下**局部最優**選擇，期望最終達到**全域最優**的演算法策略。本文系統闡述貪婪準則、適用條件、三大經典案例 (找零錢、機器排程、最短路徑) 與霍夫曼編碼、LPT 排程等延伸應用，並探討啟發式與近似演算法的邊界。

核心定義

• 貪婪準則：每階段決策的評估標準 (如「最大化當前增益」、「最小化當前成本」)。
• 不可回溯：決策一旦做出不再更改，這是貪婪法與動態規劃/回溯法的根本差異。
• 最優子結構：問題的最優解包含子問題的最優解 (必要條件)。
• 貪婪選擇性質：全域最優解可透過一系列局部最優選擇達成 (充分條件)。

案例一：找零錢 — 典型最優解

問題：用最少硬幣找零 n 分，幣值集合 {25, 10, 5, 1}。

貪婪策略：每次選擇**不超過剩餘金額的最大面額**。

範例：67 分 → 25+25+10+5+1+1 (6 枚)。

證明關鍵：對標準幣制系統 ( canonical coin system )，貪婪法保證最優。若幣值為 {25, 20, 1, 1} 找 40 分，貪婪給 25+1+1+1+1+1+1+1+1+1 (10 枚)，最優為 20+20 (2 枚) — **非標準幣制會失效**。

案例二：機器排程 (區間圖著色) — 最優解

問題：n 項任務，各有開始/結束時間 [s_i, f_i]，重疊任務不可分派同一機器，求最少機器數。

貪婪策略：

1. 任務按 s_i 遞增排序。
2. 依序處理每任務：若有機器在 s_i 時閒置 (上一任務 f_j ≤ s_i)，分派該機器；否則啟用新機器。
3. 用**最小堆**維護各機器下次可用時間，複雜度 O(n log n)。

正確性**證明**：屬於區間圖著色問題，貪婪法等價於計算區間圖的色數 (clique number)，故最優。

案例三：單源最短路徑 (Dijkstra) — 貪婪法典範

問題**：有向圖、非負邊權，求源點 s 到所有頂點的最短路徑。

貪婪準則**：每步從未確定最短路徑的頂點中，選擇當前估計距離 d[v] **最小**者確定。

關鍵不變量**：被選出的頂點其 d[v] 已是真實最短距離 (證明依賴非負邊權)。

實作**：優先佇列 (最小堆) 維護 d[v]，複雜度 O((V+E) log V)。

反例**：若含負邊權，貪婪法失效 (需 Bellman-Ford)。

延伸應用：霍夫曼編碼與 LPT 排程

啟發式與近似演算法邊界

• 啟發式：無最優保證，但通常接近最優 (如 LPT)。
• 近似演算法**：有**可證明誤差界**的啟發式 (LPT 屬此類)。
• 貪婪法不保證最優**的問題：0/1 背包、集合覆蓋、旅行推銷員 (TSP) 等 NP-hard 問題，貪婪法常作為基準啟發式或近似演算法核心。

何時適用貪婪法？檢核清單

1. 問題可分解為階段決策？
2. 存在明確的局部評估函數 (貪婪準則)？
3. 局部最優選擇不排除未來更好解？ (無後悔性質)
4. 能否證明「貪婪選擇性質」與「最優子結構」？
5. 若無法證明最優，是否可接受近似解並有誤差界分析？

結語：貪婪演算法以「簡單、高效、直覺」著稱，適用於具備**馬特羅伊德**或**贏家結構**的問題。掌握其適用邊界、證明技巧 (交換論證、歸納法) 與近似比分析，是演算法工程師的核心素養。