證明貪婪演算法的兩條路
在上一篇你看到「貪婪保持領先」的技巧如何在區間排程上奏效：我們追蹤一個遞進量（第 k 個工作的完成時間），並用歸納法證明貪婪在每一步都不落後於任何其他解。那個論證很有力，但它需要有個東西可以「領先」——一個能乾淨地推進的數值度量。許多貪婪問題並不會交給你這麼整齊的階梯。所以這篇要建立另一個偉大的證明技巧，那個幾乎在每個貪婪正確的地方都管用的：交換論證。
這個想法簡單得令人卸下心防。為了反證，假設存在一個與貪婪解相異的最佳解。找出它們「第一處」意見不合的地方。在那一點，貪婪做了某個選擇，而最佳解做了不同的選擇。交換論證說：我可以動手改那個最佳解——就在那一點，把它的選擇換成貪婪的選擇——而不讓它變差。如此重複，一次處理一處分歧，最佳解便逐漸蛻變成貪婪解，且品質從未下降。於是貪婪解至少和那個最佳解一樣好——這就表示貪婪也是最佳的。
一個實作交換：最小化遲到
讓我們把這技巧跑在一個具體問題上：最小化最大遲到。你有一台機器和 n 個工作；工作 i 需要處理時間 t_i，並有截止期限 d_i。你必須把所有工作背靠背地排序；若某工作在時刻 f 完成，它的遲到量是 max(0, f - d_i)。你要安排工作的順序，使所有工作中「最大」的遲到量盡可能小。貪婪規則直白得令人驚喜：完全無視處理時間，按截止期限排序，期限最早的先做。
為了證明這是最佳的，定義一個逆序對：一對排得不符期限順序的工作，意思是某個期限較晚的工作排在某個期限較早的工作之前。貪婪排程的逆序對為零——這正是「按期限排序」的意思。拿任一最佳排程。若它也沒有逆序對，那它本質上已經是貪婪排程了（先撇開平手），就完成了。否則它至少有一個逆序對，而這裡有個你可以直接驗證的關鍵事實：若一個排程有任何逆序對，它就有一個發生在兩個「相鄰」工作之間的逆序對。
現在執行交換：找出一個相鄰的對，其中排在較前的工作有較晚的期限，把這兩個對調。這就是全部的動作。美妙之處在於它對遲到量的影響。這兩個被交換的工作佔據和先前完全相同的那段時間區塊，所以每個「其他」工作的完成時間——以及它的遲到量——都沒被動到。只有這兩個被交換的工作可能改變，而簡短的檢查顯示，它們兩者遲到量的最大值不會增加。於是一次交換移除一個逆序對，而最壞情況的遲到量從不上升。持續交換；每一步都無害地移除一個逆序對，經過有限步後你抵達零逆序對的貪婪排程。它不會比你起初拿的那個最佳解差，所以貪婪是最佳的。
每個交換論證的骨架
剝掉排程的細節，同樣的骨架每次都會浮現。交換論證其實是把貪婪選擇性質——也就是「『某個』最佳解包含貪婪的第一個選擇」這個主張——一路推到底的證明。一旦有了它，最佳子結構接手其餘：固定了貪婪的第一個選擇後，剩下的是同一問題的較小實例，於是你遞迴下去。交換處理「貪婪的選擇安全嗎？」；子結構處理「然後剩下的又是同一個問題」。兩者合起來，正是讓貪婪能成立的兩個前提。
- 假設存在一個與貪婪解 G 相異的最佳解 OPT。
- 找出 OPT 與 G 第一個意見不合的決策（例如第一個工作，或第一個相鄰逆序對）。
- 把 OPT 變形：在那一點把它的選擇換成 G 的選擇，並讓每個未動到的部分凍結不變。
- 證明這次交換不會讓目標變差——新解仍是最佳的（或至少一樣好）。
- 重複：每次交換都嚴格減少分歧，所以有限步後 OPT 變成 G——而 G 是最佳的。
那個迴圈裡有兩個細節，很容易略過、卻略過不得。第一，交換必須朝貪婪做出「可度量的進展」——通常是減少某個計數，例如逆序對的數目，或多匹配一個貪婪的選擇——這樣過程才會在有限步後終止，而不會無限循環。第二，「不會變差」必須被論證、而非被斷言；這正是錯誤貪婪規則現形之處，因為本該證明它的那次交換，實際上會讓某個解變差。
第二種風味：在排序順序上交換
上面的逆序交換是經典的相鄰交換，每當貪婪是「依某個鍵排序、再依序處理」時就用得上。完全相同的想法可以證明分數背包規則的最佳性。那裡貪婪把物品依「每單位重量的價值」（也就是「每塊錢的份量」）排序，並依此順序倒進袋子，若最後一個裝不下整個就取一部分。要證明它，拿一個不是貪婪解的最佳裝法；它某處必定納入了一個比率較差的物品，卻留著本可以給比率較好物品的空間。
這次交換：從比率較差的物品削下一小片，並以相等的重量用比率較好的物品替換它。總重量相同，所以袋子仍裝得下；但因為我們把重量從低比率換到高比率，總價值會「上升」（平手時則持平）。一個嚴格最佳的解不可能再被改進，所以那個可交換的情況根本不曾存在——最佳裝法必定已經遵循貪婪的比率順序。注意這個交換倚賴物品是「可分割」的：你能在它們之間精確地移動「相等重量」的價值。
那個可分割性不是個註腳；它就是貪婪成立與貪婪失敗之間的整道分界。物品一旦變成不可分割——你必須整個拿或完全不拿——你就削不出那一小片，交換瓦解，貪婪也不再最佳。這正是分數背包（貪婪精確無誤）與 0/1 版本（貪婪可以差到任意程度）之間的鴻溝，本階的最後一篇會完整探討。眼下，就把交換這個步驟本身當成一個診斷工具：若你構造不出一個朝貪婪、保值或增值的交換，那是個響亮的暗示——你的貪婪規則可能是錯的。
誠實的界線：交換在被檢查前還不是證明
交換論證是一套食譜，不是一張保證書。只有當你真能履行兩項義務時，它才證明一個貪婪演算法正確：交換必須永不讓目標變差，且過程必須終止。少了任一項，你有的是個故事，不是證明。最常見的失敗是在「不會變差」這一步一廂情願——人們「描述」一個交換、目測一下，就宣稱大功告成。局部對全域這個區分的整個重點，就是局部上吸引人的動作可能在全域上是錯的，所以這一步正是嚴謹性發揮價值之處。
值得把話說清楚：「貪婪選擇現在看起來最好」本身從來不是證明。一個貪婪規則可以直觀、快速、而且就是錯的——對一組任意面額的硬幣找零，總是抓最大可用硬幣可能用掉比必要更多的硬幣，就是教科書裡的陷阱。交換論證正是把真正的貪婪成功從冒牌貨中分辨出來的工具，方法是逼你亮出那個交換並驗證它保住最佳性。當交換存在且通過檢查，你便有了一個滴水不漏的歸納證明；當它無法被建立，你也學到了同樣寶貴的東西。
再給一個關於範圍的誠實提醒。交換論證證明的是「正確性」——貪婪會回傳最佳答案——對「執行時間」隻字未提；貪婪方法的速度來自它的排序與單趟掃描，要用前面幾階的漸進分析另行處理。而當貪婪真的失敗時，交換的崩解不是死路，而是個路標：它通常意味著這問題沒有貪婪選擇性質，你得改用一個會重新考慮選擇的方法，例如下一階要建立的動態規劃。