第 16 章 贪心算法 (Greedy Algorithms)
核心结论
-
贪心算法定义：每一步做局部最优选择，期望得到全局最优；区别于动态规划——动态规划先求解子问题再做选择，贪心算法在子问题求解之前就做出选择且不可回溯。
-
贪心选择性质 (Greedy-Choice Property)：通过局部最优（贪心）选择可以构造全局最优解；必须在求解子问题之前证明存在一个最优解包含此贪心选择。
-
最优子结构 (Optimal Substructure)：问题的最优解包含子问题的最优解；这是贪心和动态规划共同的基础。
-
贪心不一定最优：0/1 背包问题不能用贪心求解（要用 DP），但分数背包可以；活动选择、Huffman 编码、最小生成树 (Kruskal/Prim)、单源最短路径 (Dijkstra)、集合覆盖启发式是贪心有效的经典案例。
-
拟阵 (Matroid)：当问题可形式化为加权拟阵的最大权独立子集时，贪心必最优；图的生成森林构成「图拟阵」，这解释了 MST 类算法为何有效。
-
与分治、动态规划对比：贪心不分解为多个子问题（只一个），不依赖子问题结果，且每步不存储中间表；动态规划处理子问题重叠，贪心适用于每步唯一选择的情况。
|
本章主旨
本章是算法设计范式之一「贪心」的集中论述。5 节内容依次展开：从活动选择展示「贪心选择性质 + 最优子结构」的证明模式，到 Huffman 编码给出工程级应用，再用拟阵理论统一刻画「何时贪心有效」，最后以单位时间任务调度作收束。整章贯彻一条主线：贪心算法看起来「盲目」，但只要满足两个性质，就能严格证明最优。第 23 章 MST、第 24 章 Dijkstra、第 35 章集合覆盖启发式都建立在贪心之上——本章是为这些后续算法铺垫的。 |
一、核心概念
本章围绕 5 个核心概念展开：先建立贪心方法的两个判定条件（16.1 + 16.2），再用 Huffman 编码作应用（16.3），通过拟阵理论统一刻画适用范围（16.4），最后落实到单位时间任务调度（16.5）。
| 概念 | 定义 + 重要性 | 实现提示 |
|---|---|---|
贪心选择性质 |
一个全局最优解包含当前贪心选择；意味着「只看眼前」不会错失最优。 |
§16.1 活动选择 (定理 16.1);证明用「cut-and-paste」把贪心选项替换原最优解中的某选项。 |
最优子结构 |
问题最优解包含子问题最优解；与 DP 共用，本章特化为「贪心选择后只剩一个子问题」。 |
§16.2 给出与 DP 的对比 (0/1 背包 vs. 分数背包);活动选择把动态规划式 16.2 化简为贪心。 |
Huffman 编码 |
用字符频率构造最优前缀码；按频率合并两个最小节点建立二叉树，最小化 B(T)=Σ c.freq·d(c)。 |
§16.3;HUFFMAN 用最小堆 Q 选出 x、y 合并;运行时间 O(n lg n) (或 O(n lg lg n) 用 vEB 树)。 |
拟阵与最大权独立集 |
加权拟阵 M=(S,ℐ,w) 上贪心按权重降序、跳过破坏独立性的元素 → 必得最大权独立子集；图拟阵 M_G 给出 MST。 |
§16.4 证明 (定理 16.7-16.11);χ(S)=t(S)+2m(S) 势函数;GREEDY 时间 O(n lg n + n·f(n))。 |
任务调度拟阵 |
单机单位时间任务 + 截止期 + 罚金的最小罚金调度，可形式化为拟阵 (S, ℐ)，其中 ℐ 是可按时完成的任务集。 |
§16.5 定理 16.13 给出独立性定义 Nt(A)≤t;按罚金降序贪心 + 拟阵定理 → 最优。单位优先级排序得 O(n²)。 |
二、详细笔记
2.1 活动选择问题 (Activity-Selection Problem)
What：给定 n 个活动，每个有开始时间 \(s_i\) 和结束时间 \(f_i\)（\(s_i < f_i\)，已按 \(f_i\) 升序排好），求最大规模的相互兼容（不重叠）活动子集。
Why：活动选择是贪心算法的「教科书级例子」——动态规划给出 O(n²) 公式（式 16.2），贪心简化为 O(n)；它清晰演示「DP 子问题可以删掉一半」后如何改写为贪心递归。
How：
-
设 \(S_k = \{a_i \in S : s_i \geq f_k\}\) 为「在 a_k 结束后开始的活动」。
-
贪心选择：选 \(S_k\) 中最早结束的活动 \(a_m\)（即 \(m = \min\{i : f_i \text{ 最小的 } a_i \in S_k\}\)）。
-
最优子结构：选 \(a_m\) 后，问题化归为 \(S_m\) 的同一子问题（只需一个递归调用，而不是 DP 的 max）。
贪心递归（伪代码）：
When：当候选解空间巨大（指数级）但每步能做「局部最优」且能严格证明该选择进入某个最优解时，活动选择这种「区间调度」即典型场景。
Example：n=11 活动（CLRS 图 16.1）中，贪心按 \(f_i\) 选 \(\{a_1, a_4, a_8, a_{11}\}\)，4 个活动为最大相容集。
2.2 贪心策略的两个性质
What：贪心方法 (Generic) 由两步构成——(1) 做出贪心选择；(2) 求解「剩下」的子问题；要求满足「贪心选择性质」与「最优子结构」。
Why：贪心算法的不严格性使其容易被误用（如 0/1 背包）；明确两个性质提供「贪心是否适用」的判据。第 16 章的其余小节都围绕建立这两条性质。
How：
| 性质 | 形式化 |
|---|---|
贪心选择性质 |
对每步子问题，存在某个最优解包含当前「看似最优」的选择（无需看未来）。 |
最优子结构 |
问题的最优解包含子问题的最优解。 |
贪心 vs. DP：
| 问题 | 贪心？ | 替代 |
|---|---|---|
活动选择 |
是（每步最早结束） |
DP O(n²)（式 16.2） |
分数背包 |
是（按 value/weight 降序） |
— |
0/1 背包 |
否（整数约束导致子问题重叠） |
DP，O(nW) |
Huffman 编码 |
是（每次合并最小两频率） |
— |
When：拿到一个优化问题时，先检验两个性质；若证明贪心性质 + 最优子结构都能成立，可用贪心得到最快的多项式解。
Example：0/1 背包反例（CLRS 图 16.2）——物品 1（60/10=6）、物品 2（100/20=5）、物品 3（120/30=4），W=50。贪心先选物品 1 后剩 40 磅放不下物品 2+3（需 50），总价值 160；最优是物品 2+3 = 220。贪心失败因为「跳不出已选的子集」。
2.3 Huffman 编码
What：Huffman 编码是一种最优前缀码 (prefix code)——给定字符频率，把每个字符表示为 0/1 串，使编码长度加权和最小 \(B(T) = \sum_{c \in C} c.\text{freq} \cdot d_T(c)\)。
Why：Huffman 是数据压缩的核心算法（典型压缩率 20%-90%）。它把「压缩比优化」转化为「带权二叉树的合并问题」，是贪心算法在工程上最重要的应用之一。
How：
-
HUFFMAN 算法（CLRS 伪代码）：
-
初始化最小堆 Q ← C。
-
循环 \(n-1\) 次：取 x = EXTRACT-MIN(Q)，取 y = EXTRACT-MIN(Q)，合并 z（z.freq = x.freq + y.freq），z.left = x，z.right = y，INSERT(Q, z)。
-
返回 Q 中唯一节点（根）。
-
-
正确性：引理 16.2（贪心性质——最小两频率 x、y 必在最优前缀码中互为兄弟）、引理 16.3（最优子结构——合并后的子问题独立）。定理 16.4：「HUFFMAN 产生最优前缀码」。
-
复杂度：O(n lg n)（用二叉堆）或 O(n lg lg n)（用 van Emde Boas 树，第 20 章）。
When：需要压缩的字符集 + 已知频率；字符数 n 不太大；解码端可拿到码表（通常发送码表只占 O(n) 比特）。
Example：CLRS 图 16.3 中 6 字符，频率 {a=45, b=13, c=12, d=16, e=9, f=5}。定长码需 3×100000=300000 比特；Huffman 可压到 45·1+13·3+12·3+16·3+9·4+5·4 = 224000 比特。
2.4 拟阵与贪心方法
What：拟阵 M = (S, ℐ) 是满足 (1) 遗传性 (ℐ 在子集下封闭)、(2) 交换性 (|A|<|B| 时 ∃ x ∈ B\A 使 A∪{x} ∈ ℐ) 的序对；加权拟阵问题 = 在 ℐ 中找最大权独立集。
Why：拟阵理论是「贪心有效」的精确刻画——图拟阵 M_G（独立集 = 无环边集）解释了为何 MST 类算法用贪心有效；任务调度拟阵解释了 §16.5 的正确性。
How：
| 拟阵元素 | 定义 / 性质 | 备注 |
|---|---|---|
S |
有限「元素集」 |
加权问题里是边集 / 任务集 |
ℐ |
独立子集族，满足遗传性 + 交换性 |
例：图 G = (V,E) 的无环边集 |
最大独立子集 |
极大（不可再扩）独立子集 |
定理 16.6：所有最大独立子集大小相同 |
加权 |
w: S → ℝ⁺ |
最大权独立子集 = 拟阵贪心目标 |
收缩 M/x |
移除 x 后，所有与 {x} 仍独立的子集 |
引理 16.10：子问题结构 |
贪心算法 (CLRS 伪代码 GREEDY)：
按 w 降序排序 → 依次试每个元素 → 加入当且仅当保持独立性。
势函数 χ(H) = t(H) + 2·m(H) 用于复杂度分析。
When：当问题可建模为加权拟阵（如 MST、单位时间任务调度、最大权森林、线性代数中的向量独立）时，贪心可证明最优。
Example：图拟阵 M_G = (E, {无环边集})，加权即为 MST 问题（贪心选最小权边 + 不形成环 = Kruskal）。
2.5 任务调度问题 (Task Scheduling)
What：n 个单位时间任务 \(a_i\)，截止期 \(d_i\)，罚金 \(w_i\)；单机调度使「逾截止期任务的总罚金」最小。
Why：看似复杂的优化问题可形式化为拟阵（定理 16.13），贪心按罚金降序即可最优——这是「先把 NP-hard / hard 问题识别出来再用特定结构」的范例。
How：
-
集合 A 独立（定义 16.5 节）：A 中任务按截止期升序排列可全按时完成 ⟺ \(\forall t,\, N_t(A) := |\{a_i \in A : d_i \leq t\}| \leq t\)。
-
拟阵结构：定理 16.13 证明 (S, ℐ) 满足遗传性 + 交换性，故 GREEDY 给出最优独立集。
-
贪心步骤：按 \(w_i\) 降序排任务；若加入 A 后仍独立就加入；否则跳过（A 中元素即为「按时完成」子集）。
-
复杂度：每次独立性检查 O(n)，共 O(n²)；用第 21 章 disjoint-set 森林可优化（问题 16-4）。
When：单位时间 + 单机 + 截止期 + 罚金 = 「应做」而非「应拒」的二元决策；超出范围（多机 / 非单位时间）需其他算法。
Example：CLRS 图 16.7 — 7 任务，贪心选 {a1(70),a2(60),a3(50),a4(40),a7(10)} 按时完成，剩余 {a5, a6} 罚金 50。最优调度 ⟨a2,a4,a1,a3,a7,a5,a6⟩ 总罚金 50。
三、关键图表
|
核心公式对照表
|
四、思维导图
mindmap
root((第 16 章 贪心算法))
贪心选择性质
局部即全局
cut-and-paste 证法
最优子结构
与DP共用
只剩一个子问题
活动选择
按f_i排序
最早结束优先
Huffman编码
最小堆合并
前缀码
拟阵理论
遗传性交换性
图拟阵M_G
最大权独立集
任务调度
单位时间任务
截止期罚金
罚金降序贪心
与DP分治对比
DP重叠子问题
分治独立子问题
贪心唯一选择五、重点与易错点
-
贪心 vs. DP：贪心在「子问题求解之前」做选择；DP 是先解子问题再选。若每步只有 1 个子问题 ⟹ 通常贪心快；若有多子问题重叠 ⟹ DP。
-
0/1 背包不能用贪心，分数背包可以——经典反例：取最大 value/weight 可能占满空间，反而失去可容纳的大件。
-
证明贪心算法要证 2 件事：(1) 存在某个最优解含贪心选择（cut-and-paste）；(2) 剩下的问题仍具最优子结构。两者缺一不可。
-
Huffman 必须用最小堆合并最大两频率吗？——最小两频率合并；引理 16.2 是「存在最优码」使最小两频率互为兄弟，因此合并无妨。
-
拟阵并不覆盖所有贪心问题——活动选择和 Huffman 都不构成拟阵（活动选择：独立集 = 任何兼容子集；MST 和任务调度才是）。
-
任务调度中「独立性」不是「两两不冲突」，而是「存在按时完成的次序」——式 16.5 节中表述为 \(N_t(A) \leq t\)。
-
贪心算法的代价：找到「贪心选择后只剩一个子问题」的等式，并说明其规模严格变小——否则会因子问题不缩而失败。
-
Kruskal 算法在加权图、无负权、连通假设下总能给出 MST；若有权为负，则需变号处理或加常数偏移（参见 §16.4）。
-
复杂度统计：Huffman 用二叉堆是 O(n lg n)；用 Fibonacci 堆仍是 O(n lg n) 但常数大；用 van Emde Boas 树可改进到 O(n lg lg n)。
-
集合覆盖的贪心（Chvátal 算法，见第 35 章）是「贪心给出 \(H_n\) 近似」的经典案例；本章强调「贪心最优」而第 35 章讨论「贪心近似」。
-
在 CLRS 第 4 章分治、第 15 章 DP、第 16 章贪心、第 17 章摊还之间，贪心是最「脆弱」但通常最「快」的——必须先证两个性质再使用。
-
引理 16.2 的交换论证（cut-and-paste）：取任意最优树 T，把最大深的兄弟 (a,b) 与最小频率 (x,y) 交换；因 x.freq ≤ a.freq、y.freq ≤ b.freq，交换不增代价，故最优码可在「x,y 兄弟」中选取。