貪婪演算法

抓住最好的，繼續往前

一個[[greedy-algorithm|貪婪演算法]]一步一步地構建解，而每一步它都做出*此刻*看起來最好的選擇——最大的硬幣、最早結束的會議、最便宜的邊——而且從不反悔。它既不向前看，也不往回退。它是全部計算中最樂觀的策略：它只是一味相信，一連串局部最優的選擇，加起來就能湊成一個全局最優的答案。

當這份信任站得住腳時，回報是巨大的。貪婪演算法通常很短、通常很快——往往就是*把輸入排個序，再掃一遍*——而且它完全繞開了動態規劃那套笨重的機器。你會遇到兩個你已經認識、卻正是建立在貪婪選擇之上的結構：最小生成樹（總是加入最便宜的安全邊）和 Dijkstra 的最短路徑（總是下一個敲定離起點最近的未完成節點）。

貪婪何時奏效：區間調度

這是經典的勝局。你有一間會議室和一堆會議，每場都有開始與結束時間；你想塞進盡可能多、互不重疊的會議。奏效的貪婪規則出人意料：*在還塞得下的會議裡，永遠挑結束得最早的那一場。*早早結束，就給它之後的一切留下了最多空間。按結束時間排序，然後掃一遍。

#include <vector>
#include <algorithm>
struct Meeting { int start, end; };

int maxMeetings(std::vector<Meeting> v) {
    // Greedy: sort by EARLIEST finishing time.
    std::sort(v.begin(), v.end(),
              [](const Meeting& a, const Meeting& b){ return a.end < b.end; });

    int count = 0, lastEnd = -1;
    for (const Meeting& m : v) {
        if (m.start >= lastEnd) {   // doesn't overlap what we kept
            count++;
            lastEnd = m.end;        // commit; never reconsider
        }
    }
    return count;
}

為什麼這能*被證明*是最優的？直覺是一個交換論證：取任意一個最佳的安排，看它的第一場會議。如果它結束得不如貪婪首選那麼早，你就可以把貪婪那場換進去——它結束得不會更晚，所以不會破壞它之後的任何安排。沿著序列不斷重複這個交換，你就把一個最優安排變成了貪婪的那個，且一場會議都沒少。於是貪婪至少不比最佳差——也就是說，它*就是*最佳。

貪婪何時失敗：硬幣反例

現在來看陷阱。要用最少的硬幣湊出一個金額，顯而易見的貪婪規則是*抓住塞得下的最大面額，重複。*用日常面額 {1, 5, 10, 25} 它總能行。但換一套硬幣它就崩了。假設你的硬幣是 {1, 3, 4}，而你必須湊出 6：

Coins available: { 1, 3, 4 }     Target: 6

GREEDY (take biggest first):        OPTIMAL:
    take 4   ->  remaining 2            take 3   ->  remaining 3
    take 1   ->  remaining 1            take 3   ->  remaining 0
    take 1   ->  remaining 0
    -----------------------             -----------------------
    4 + 1 + 1  =  THREE coins           3 + 3  =  TWO coins   (better!)

第二個勝局：霍夫曼編碼

貪婪再露鋒芒的一處：霍夫曼編碼，是許多檔案壓縮背後的思路。你想給高頻字母短的位碼、給罕見字母長的位碼。貪婪的招法：反覆取出頻率最低的兩個條目，合併成一個頻率為兩者之和的節點，再放回去。如此進行，直到只剩一棵樹——這棵樹給出可證明為最優的編碼。

1. 把每個符號連同它的頻率，放進一個最小優先佇列（頻率最小的在頂）。
2. 彈出最小的兩個。造一個新節點，其頻率為兩者之和，其左右子節點正是這兩個。
3. 把這個合併後的節點壓回佇列。
4. 重複到只剩一個節點——霍夫曼樹的根。左走 0、右走 1，就給了每個符號它的編碼。

留意它的引擎：一個由最小堆支撐的優先佇列，正是上一級台階裡的那個結構。貪婪演算法時時刻刻倚賴排序和優先佇列，因為這兩者都能廉價地回答「此刻最好的選擇是什麼？」——而這正是貪婪唯一會問的問題。