交換論證（exchange argument）

當待比較的答案多到天文數字時，你如何證明「抓局部最佳」真的給出整體最佳答案？你不去一一列舉。你改用論證：取任何一個與貪婪不一致的最佳答案，說明你能編輯它——把它的某個選擇換成貪婪選擇——而不使它變差。交換論證正是這個「換而不損」的動作。

骨架如下。令 G 為貪婪解、O 為最佳解。找它們第一個不同之處。從 O 構造新解 O'：把 O 在該處的選擇換成 G 的選擇，其餘保持不動。證明兩件事：(1) O' 仍可行（合法解）；(2) O' 不比 O 差。既然 O 最佳，O' 也最佳——而 O' 比 O 多在一處與 G 一致。重複此步，你便一步步把 O 變成 G 而從不損失最佳性，故 G 最佳。具體到「在有期限下最小化遲到」，若某最佳排程有相鄰兩個工作的期限順序顛倒，交換它們不會增加最大遲到量，故某個最佳排程依期限排序——這正是貪婪所做的。

交換論證是證明貪婪正確性的主力技巧，用於區間排程、最小化遲到、霍夫曼編碼，以及克魯斯卡最小生成樹底下的擬陣理論。要尊重兩個陷阱：你必須檢查交換後解仍可行（合法），也必須檢查它不使目標變差——略過任一步是這類證明悄悄崩壞最常見的原因。當找不到有效的交換時，往往就是貪婪對該問題出錯的訊號。