貪婪算法核心思想與經典最優化問題建模指南

貪婪算法核心思想與經典最優化問題建模指南

演算法設計雖似藝術，但存在行之有效的通用設計範式。貪婪算法是其中最直觀、最常用的一類——**每步做當下最優選擇，期望推導出全局最優解** 。本文建立最優化問題統一形式化框架，並解析貨箱裝載、渴嬰問題、最小代價通訊網絡三大經典模型。

最優化問題統一形式化定義

每個最優化問題包含三要素：

1. 決策變量：x = (x₁, x₂, ..., xₙ)
2. 約束條件：g(x) ≤ 0, h(x) = 0 (定義可行域)
3. 優化目標：最大化/最小化 f(x)

可行解：滿足所有約束的決策向量。
最優解：在可行域內使目標函數達到極值的可行解。

經典建模三例

例 1：渴嬰問題 (連續決策、線性規劃原型)

場景：嬰兒需飲 t 盎司飲料解渴，有 n 種飲料，第 i 種總量 aᵢ，單位滿意度 sᵢ。決定飲用量 xᵢ 最大化總滿意度。

• 決策變量：xᵢ ≥ 0 (實數)
• 約束：Σ xᵢ = t, 0 ≤ xᵢ ≤ aᵢ
• 目標：最大化 Σ sᵢ xᵢ
• 可行性條件：Σ aᵢ ≥ t

貪婪策略：按 sᵢ 降序飲用，滿意度最高者優先喝完，直到解渴。此為分數背包問題，貪婪最優。

例 2：貨箱裝載問題 (離散決策、0-1 背包特例)

• 決策變量：xᵢ ∈ {0,1}
• 約束：Σ wᵢ xᵢ ≤ c
• 目標：最大化 Σ xᵢ (裝載數量)

貪婪策略：按 wᵢ 升序裝載。已證最優 (見 專文)。

例 3：最小代價通訊網絡 (圖論、生成樹)

• 建模：無向圖 G=(V,E)，邊權 w(e) = 建設代價
• 可行解：連通全圖的生成樹 T ⊆ E
• 目標：最小化 Σ_{e∈T} w(e)

貪婪策略：Kruskal/Prim 算法，每步選最小權邊且不成環。最優解 = 最小生成樹 (MST)。

貪婪算法適用性判斷兩大核心性質

1. 貪婪選擇性質：全局最優解可通過局部最優選擇構造 (無需回溯)。
2. 最優子結構性質：問題最優解包含子問題的最優解。

滿足兩性質者，貪婪算法通常有效；否則需動態規劃、回溯或近似算法。

貪婪算法設計模板

GreedySolve(Problem P):
    1. 將 P 的所有候選對象按某優先級規則排序
    2. 初始化解集 S = ∅, 資源/狀態 R = 初始值
    3. for 每個候選對象 c (按優先級順序):
           if c 滿足約束條件 (可行性檢查):
                S ← S ∪ {c}
                更新 R
    4. return S

常見貪婪策略分類

反例警示：貪婪失效場景

• 0-1 背包問題：按單位價值貪婪不最優 (需 DP)
• 最短路徑 (負權邊)：Dijkstra 貪婪失效 (需 Bellman-Ford)
• 旅行商問題 (TSP)：最近鄰貪婪極差 (NP-hard)
• 圖著色：最大度貪婪非最優 (NP-hard)

理解最優化問題的三要素建模、識別貪婪選擇性質與最優子結構、掌握常見貪婪策略分類，是靈活運用貪婪算法解決實際工程問題的核心內功。