作者：劉子韜
核心方法：Exchange Argument（交換論證）
證明貪心算法最優的經典技巧：假設存在最優解 O 與貪心算法 A 最接近，通過交換一個步驟/元素構造新最優解 O'，使 O' 更接近 A，產生矛盾，證 A 最優。
標準證明框架（版本 1）
- 給出貪心算法 A 描述
- 假設 O 是與 A 最相似的最優解（前 k-1 步相同，第 k 步不同）
- 關鍵步驟：交換 A 和 O 中的某元素，構造 O'
- 證明 O' 可行（滿足約束條件）
- 證明 O' 至少與 O 一樣優（目標值不劣）
- 得出矛盾：O' 比 O 更接近 A，違背「最相似」假設 → A 最優
變體框架（版本 2）
- 給出貪心算法 A
- 任意選一最優解 O
- 找出 O 和 A 的一處不同（元素歸屬或順序）
- Exchange 該差異，論證新解不劣於 O
- 論證此類不同只有多項式個，多項式次交換後消除所有差異，得 A 最優
經典例題演示
例 1：最大基數不相交區間問題
問題：給定區間集合 T={(a₁,b₁)...(aₙ,bₙ)}，找最大子集 S 使區間互不重疊。
貪心策略：每次選右端點 b 最小的區間加入 S，刪除其與所有重疊區間，重複。
證明：
- 設 A 第 k 步選 (aᵢ,bᵢ)，O 第 k 步選 (aⱼ,bⱼ)，由貪心性質 bᵢ ≤ bⱼ
- 構造 O' = O - (aⱼ,bⱼ) + (aᵢ,bᵢ)
- 可行性：前 k-1 同 A 無重疊；bᵢ ≤ bⱼ 保證不與後續重疊
- 最優性：|O'| = |O|，同為最優
- 矛盾：O' 與 A 共同區間數為 k，違背假設 → A 最優
例 2：帶截止時間的調度問題
問題：n 個任務，執行時間 pᵢ，CPU 非搶佔，所有任務同時釋放，最小化平均完成時間 (Σcᵢ)/n。
貪心策略：每次選剩餘執行時間最短的任務（SPT 原則）。
證明：
- 設 A、O 前 k-1 相同，A 第 k 選任務 i，O 第 k 選任務 j，知 pᵢ ≤ pⱼ
- O 中任務 i 位於第 t 位（t > k）
- 構造 O'：交換 O 中位置 k 和 t 的任務
- 計算總完成時間差：Time(O) - Time(O') = (pᵢ - pⱼ)(k - t) ≥ 0
- 故 O' 不劣於 O，且與 A 共同前綴長度為 k → 矛盾 → A 最優
例 3：Kruskal 最小生成樹算法
問題：邊按權重排序，依序加入不形成環的邊。
證明（版本 2 框架）：
- 設 Kruskal 生成樹 T₂，任意最優解 T₁，T₁ ≠ T₂
- 存在邊 e ∈ T₁ 但 e ∉ T₂
- 刪除 e 將 T₁ 分為 Tₐ, T_b；T₂ 中必有邊 f 連接 Tₐ, T_b（f ≠ e）
- Kruskal 未選 e 因形成環，且先選了 f → w(f) ≤ w(e)
- 構造 T₃ = T₁ - e + f
- T₃ 為生成樹（f 連通兩分量），權重 ≤ T₁（因 w(f) ≤ w(e)） → T₃ 也是 MST
- T₃ 比 T₁ 多一條與 T₂ 相同的邊
- 重複 n 次交換可將 T₁ 轉化為 T₂，權重不增 → T₂ 是 MST
總結
Exchange Argument 是證明貪心算法最優性的利器。核心邏輯：構造反例最優解 → 局部交換 → 保持可行性與最優性 → 逼近貪心解 → 產生矛盾。三個經典例題展示了從區間調度、任務調度到圖論的廣泛適用性。掌握此法，貪心算法證明不再是難題。
