貪心演算法：短視的獵人

演算法背後的故事：找零錢

想像妳是一名收銀員。一個顧客需要 41 美分的零錢。妳手裡有 25、10、5 和 1 美分的硬幣。 妳如何用最少數量的硬幣湊齊零錢？

很自然地，妳會先拿最大的硬幣：

1. 拿一個 25¢ 硬幣 (還剩: 16¢)
2. 拿一個 10¢ 硬幣 (還剩: 6¢)
3. 拿一個 5¢ 硬幣 (還剩: 1¢)
4. 拿一個 1¢ 硬幣 (還剩: 0¢)

總計：4 枚硬幣。 這種「先拿最大的」策略就是 貪心演算法。妳沒有考慮未來；妳只是抓住了眼下最好的東西。對於許多貨幣體系來說，這種貪心選擇確實就是最優解。

為什麼需要它？

• 速度： 貪心演算法通常是 $O(N)$ 或 $O(N \log N)$。她們比動態規劃快得多。
• 網絡： Dijkstra 演算法（最短路徑）和 Prim 演算法（最小生成樹）都是貪心策略。
• 壓縮： 哈夫曼編碼使用貪心策略來構建最優樹。
• 調度： 在一個房間裡安排儘可能多的會議。

演算法是如何「思考」的

該演算法是一個順序決策者。

1. 選擇： 從當前集合中挑選「最佳」候選者。
2. 可行性： 檢查這個候選者是否違反了任何規則。
3. 不可逆性： 一旦選定，絕不回頭。貪心演算法沒有「撤銷」按鈕。

貪心選擇性質： 貪心演算法僅在「局部最優解能導致全局最優解」時有效。

• 陷阱： 如果妳有 25、20 和 1 美分的硬幣，而妳需要找 40 美分的零錢……
  • 貪心策略：25 + 1 + 1… (需要 16 枚硬幣)
  • 實際最優：20 + 20 (只需要 2 枚硬幣) 在這種情況下，短視的獵人就翻車了。

工程決策：「足夠好」的方案

在許多複雜的工程問題中（如旅行商問題），尋找完美答案可能需要幾年的計算。

• 工程師通常使用 貪心啟發式演算法 (Greedy Heuristics) 在 10 毫秒內找到一個「95% 完美」的答案。
• 在生產環境中，一個快速且還不錯的答案往往優於一個緩慢但完美的答案。

實作參考 (Python)

# 區間調度問題：在一個房間內安排最多的會議
def schedule_meetings(meetings):
    # meetings = [(開始時間, 結束時間), ...]
    
    # 1. 貪心選擇：按「結束時間」排序
    # 一個會議結束得越早，留給後面會議的空間就越大
    meetings.sort(key=lambda x: x[1])
    
    count = 0
    last_end_time = 0
    selected = []

    for start, end in meetings:
        if start >= last_end_time:
            # 2. 可行性檢查：不重疊？是的。
            count += 1
            last_end_time = end
            selected.append((start, end))
            
    return count, selected

# 使用範例
mtgs = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11)]
print(f"最大會議數: {schedule_meetings(mtgs)}")

小結

貪心演算法教會我們：有時候，專注比規劃更重要。 透過無情地追求眼前的最優方案，我們可以用最小的代價解決複雜問題。它提醒我們，雖然我們應該追求最好的結果，但我們也必須尊重時間和複雜性的成本。