貪婪演算法教學：原理、程式碼與範例

貪婪演算法解決什麼問題

貪婪演算法針對最佳化問題：選出最多的活動、用最少的硬幣、建出最便宜的網路、把檔案壓縮成最少的位元。貪婪演算法不會探索每種組合，而是把選項排序或排定優先順序，並在每一步承諾選擇最佳的那個。這通常只需 O(n log n) 時間，往往就是排序的成本。

困難之處不在程式碼，而在證明。許多看似自然的貪婪規則其實是錯的，所以你必須證明該規則正確，或拿它和暴力解法互相比對測試。

用白話說明原理

1. 找出一個能為選項排名的規則，例如「最早結束者優先」或「最輕的邊優先」。
2. 依這個規則將選項排序，或把它們放進優先佇列。
3. 逐一檢視選項，凡是仍符合限制條件的就選取。
4. 絕不撤銷已做的選擇。

貪婪演算法要正確，必須同時具備兩個性質。貪婪選擇性質：存在一個最佳解包含第一個貪婪選擇。最佳子結構：做出該選擇後，剩下的問題是同一問題的較小實例。常用的證明方式是交換論證：取任何一個最佳解，證明把其中的某個選擇換成貪婪選擇並不會使結果變差。

範例：區間排程

你有一間會議室和這些申請（開始, 結束）：A (1, 4)、B (3, 5)、C (0, 6)、D (5, 7)、E (3, 9)、F (5, 9)、G (6, 10)、H (8, 11)。要排入盡可能多的互不重疊的會議。正確的貪婪規則是：在所有於上一場已排入會議結束後才開始的會議中，永遠挑結束最早的那場。

結果：A、D、H，共三場會議，這就是最大值。為什麼有效：最早結束的會議留給其他會議的時間最多，所以把任何最佳排程的第一場會議換成它，都不會造成衝突。

Python 實作

def max_meetings(meetings):
    """meetings: list of (name, start, end). Returns the booked names."""
    booked, last_end = [], float("-inf")
    for name, start, end in sorted(meetings, key=lambda m: m[2]):
        if start >= last_end:
            booked.append(name)
            last_end = end
    return booked

requests = [("A", 1, 4), ("B", 3, 5), ("C", 0, 6), ("D", 5, 7),
            ("E", 3, 9), ("F", 5, 9), ("G", 6, 10), ("H", 8, 11)]
print(max_meetings(requests))  # ['A', 'D', 'H']

第二個經典例子是分數背包：當你可以只拿物品的一部分時，依每單位重量的價值由高到低取物品就是最佳解。

def fractional_knapsack(items, capacity):
    """items: list of (value, weight). Returns the best total value."""
    total = 0.0
    for value, weight in sorted(items, key=lambda i: i[0] / i[1], reverse=True):
        take = min(weight, capacity)
        total += value * take / weight
        capacity -= take
        if capacity == 0:
            break
    return total

print(fractional_knapsack([(60, 10), (100, 20), (120, 30)], 50))  # 240.0

貪婪失效時：反例

時間與空間複雜度

空間通常是 O(n)，用於排序後的副本或堆積。如果輸入已排序，許多貪婪演算法可在 O(n) 內完成。

何時使用貪婪演算法與實際應用

• 當你能證明貪婪選擇性質，或可以接受快速的近似答案時，請使用貪婪演算法；否則請用動態規劃或回溯法。
• 壓縮：霍夫曼編碼反覆合併出現頻率最低的兩個符號，建出最佳前綴碼；DEFLATE（ZIP、gzip、PNG）等格式內部就使用它。
• 網路：最小生成樹（Kruskal、Prim）與最短路徑路由（Dijkstra）。
• 排程：最早截止時間優先，以及預約會議室或機器。
• 近似解：對於集合覆蓋問題，貪婪規則「挑出能覆蓋最多未覆蓋元素的集合」雖然不是最佳解，但保證與最佳解相差不超過對數倍。
• 面試題目：跳躍遊戲、加油站、分配餅乾、無重疊區間、用最少箭數射爆氣球、任務排程器。