追求極致的效率：淺談「貪婪演算法」 (Greedy Algorithm)

當面臨眾多問題紛擾而至，你能冷靜的一一處理嗎？管理學上有一個木桶理論，提醒我們補齊短板；也有 80/20 法則，提醒我們把視角放在大且重要的事物上。而在演算法的世界裡，有一種思維叫「貪婪」，它主張：「既然無法預見未來，那就把當下做到最好。」

在許多實務情境裡，我們不一定有時間把所有可能都試過一遍，再找出絕對最佳答案。這時，一種看似直接卻非常有力量的策略就會登場，那就是貪婪演算法。它的核心精神很簡單：每一步都先選當下看起來最好的選項，盡快往目標推進。

這種方法之所以迷人，不只是因為它快，更因為它在某些問題上真的能得到最佳解。像是找零問題、活動選擇、最小生成樹、霍夫曼編碼，都能看到貪婪策略大放異彩。不過它也不是萬能的，理解它何時有效、何時失效，才是真正掌握這個方法的關鍵。

1. 什麼是貪婪演算法？

貪婪演算法是一種逐步決策的方法。每到一個新的步驟，它都不回頭看整體的所有可能，而是直接選擇眼前最有利的方案。這種決策方式強調局部最佳，希望透過一連串的局部最佳選擇，最終走到整體最佳解。

它的特色在於規則通常很明確，也很容易實作。你不需要保存大量狀態，也不需要枚舉所有組合，因此常常能在時間效率上表現得很出色。

也因為這種「先做再說」的風格，貪婪演算法常被視為效率導向非常強烈的一種思考方式。

不是所有問題都適合貪婪法，但適合的那一類問題，通常具備兩個重要特性：貪婪選擇性質與最佳子結構。前者表示你在當下做出的最佳選擇，不會破壞未來得到全域最佳解的可能；後者表示整體問題的最佳解，可以拆成子問題的最佳解組合而成。

以活動選擇問題為例，如果我們每次都優先挑選最早結束的活動，反而能保留更多後續空間，讓整體安排更多活動。這裡看似只是做了一個局部決策，但它剛好符合整體最優的方向。

貪婪法不是亂選最快的，而是建立在問題結構允許的前提下，做出最有效率的選擇。

貪婪演算法最常見的陷阱，就是把「當下最好」誤以為一定等於「整體最好」。在某些問題裡，眼前最划算的選擇，反而可能讓你失去更好的長期結果。

例如背包問題中的 0/1 背包，如果每次都只挑價值最高或單位價值最高的物品，未必能組成整體最大價值。因為每個物品不是拿一部分，而是只能整個拿或整個不拿，這種限制會讓局部最佳不一定通往全域最佳。

所以面對一個新問題時，不能只因為它看起來能「先挑最好的」就直接使用貪婪法，還需要先驗證這個策略是否真的成立。

很多學習者在接觸演算法時，常會把貪婪演算法和動態規劃放在一起比較。兩者都可能處理最佳化問題，但思路很不一樣。貪婪演算法每一步只根據當下做選擇，不保留太多備案；動態規劃則會系統性地比較多種子問題結果，再從中拼出最佳解。

簡單來說，貪婪法比較像是快速、果斷地前進；動態規劃比較像是把可能性整理清楚後，再做更穩健的選擇。前者通常更省時間與空間，後者通常更有機會保證答案正確。

如果問題允許貪婪法成立，那它往往會是非常漂亮的解法；但如果結構不支持，動態規劃通常會更可靠。

學貪婪演算法，不只是背哪些題目能用，更重要的是練習辨認問題結構。你可以先問自己：這個問題能不能在每一步定義「當下最好的選擇」？這個選擇做下去之後，會不會破壞整體最佳解？如果不會，那就有機會往貪婪法靠近。

另一個很重要的能力，是學會證明。真正成熟的貪婪解法，通常需要透過交換論證、反證法或結構推導，來說明為什麼局部最佳可以導向整體最佳。這也是演算法學習從「會寫」走向「真的理解」的重要一步。

貪婪演算法的迷人之處，在於它讓我們看到一種非常務實的解題哲學：不是每次都追求最複雜的策略，而是在對的條件下，用最直接的方法做出高效率的判斷。這份對效率的敏感，正是演算法思維很有價值的一部分。