算法设计第 4 章：贪心算法——交换论证与拟阵，把局部最优变成全局最优

贪心是五种策略里写起来最短、错起来最隐蔽的一种。它的代码往往只有十几行，但"每一步取局部最优能否得到全局最优"这个问题，不证明就只能靠运气。这一章真正要练的不是背算法，而是两套证明工具：交换论证（把最优解逐步改造成贪心解而不变差）与拟阵（用代数结构一次性保证一整类问题的贪心正确）。学完应当能对一个新的贪心策略给出可信的正确性论证，而不是"感觉对"。

一、活动安排与区间调度

活动安排问题：n 个活动占用同一资源，第 i 个活动有起止时间 [sᵢ, fᵢ)，求最多能安排多少个互不重叠的活动。

贪心策略：按结束时间 fᵢ 升序排序，依次选取与已选集合兼容的活动。复杂度 O(n log n)，瓶颈在排序。

为什么是结束时间而不是开始时间、不是持续时间？三个反例足以说明：

策略	反例	结果
选开始最早的	[0,10)、[1,2)、[2,3)	选到 1 个，最优 2 个
选持续时间最短的	[0,5)、[5,6)、[4,7)	选到 2 个，最优 2 个但对其他实例失效
选结束最早的	任意实例	恒最优

选结束最早的直觉是：它给后续活动留下最大的时间余量，且它的结束时间不晚于任何最优解的第一个活动。

区间划分（最少教室）：把活动分配到最少的资源上使互不冲突。按开始时间排序，用小顶堆维护各教室的结束时间，若最早结束的教室已空则复用，否则新开一间。复杂度 O(n log n)，所需教室数等于任意时刻的最大重叠数——这个下界可直接由区间图着色得出。

二、贪心选择性质与最优子结构

一个贪心算法正确的充分条件有两条：

1. 贪心选择性质：存在一个最优解包含第一次贪心选择。证明套路是交换论证——设 O 是某个最优解，若 O 不含贪心选中的元素 x，则把 O 中"与 x 冲突的那个元素"替换成 x，说明替换后不劣，于是得到一个含 x 的最优解。
2. 最优子结构：做出贪心选择后，原问题化为规模更小的同类子问题，且原问题最优解 = 贪心选择 + 子问题最优解。

活动安排的交换论证：设贪心选的第一个活动是 g（结束最早），最优解 O 的第一个活动是 o。因 f_g ≤ f_o，把 o 换成 g 后剩余时间只多不少，O 中其余活动仍兼容，故存在含 g 的最优解。归纳即得。

这两条与动态规划的区别：DP 的最优解依赖所有子问题的比较，贪心只依赖一个子问题且不做回溯。贪心是"带承诺的 DP"，承诺一旦错，答案就错，且往往错得不明显。

三、Dijkstra 单源最短路径

维护已确定集合 S 与距离数组 d，每轮从 V−S 中取 d 最小的顶点加入 S，并用它松弛邻边：若 d[u] + w(u,v) < d[v] 则更新。

复杂度：邻接矩阵实现 O(n²)；邻接表 + 二叉堆 O((n+m) log n)；用斐波那契堆可到 O(m + n log n)。

正确性依赖一个前提：所有边权非负。若存在负权边，"已确定的点距离不会再变小"就不成立，后面可能出现一条负边把已定点的距离再压低。这就是 Dijkstra 不能处理负权的根本原因，也是它区别于 Bellman-Ford（O(nm)，可处理负权但不能有负环）的分界。

同属贪心的还有 Huffman 编码（每次合并权值最小的两棵子树，O(n log n)）和 多机调度（最长处理时间优先，是 4/3 近似，不是最优）。

四、Prim 与 Kruskal 最小生成树

Prim（加点）：从任一点出发，每次选连接"树内"与"树外"的最小权边，把新顶点并入。O(n²)，与边数无关，适合稠密图。

Kruskal（加边）：所有边按权升序，用并查集判环，不成环就加入，选够 n−1 条停。O(m log m)（排序主导），适合稀疏图。

两者都是贪心，正确性可由割性质统一说明：对任意割，横跨割的最小权边必属于某棵最小生成树。Prim 每次用的正是当前割的最小边，Kruskal 用的是"使两端不连通"的最小边。

注意两个结论：MST 不一定唯一（存在等权边时），但总权值唯一；MST 只保证连通无环总权最小，不保证任意两点间路径最短——那是最短路径树的事，两者常被混淆。

五、拟阵理论与正确性证明框架

拟阵是一个二元组 M = (S, I)，I 是 S 的子集族（称为独立集），满足：

1. 遗传性：若 A ∈ I 且 B ⊆ A，则 B ∈ I。
2. 交换性：若 A, B ∈ I 且 |A| < |B|，则存在 x ∈ B−A 使 A ∪ {x} ∈ I。

定理：若 (S, I) 是拟阵，w 是权函数，则"按权降序扫描，能加入就加入"的贪心算法得到最大权独立集——这正是 Kruskal 的抽象版本（图拟阵的独立集就是无环边集，即森林）。

拟阵的价值在于把正确性证明从"逐个问题论证"变成"验证两条公理"。但它只覆盖"独立集 + 线性权"这一族问题；活动安排、Huffman、Dijkstra 都不是拟阵问题，仍需交换论证。遇到新的贪心题，先试拟阵，不成就退回交换论证，这是本章最实用的判断顺序。

六、贪心与动态规划怎么选

维度	贪心	动态规划
决策方式	每步立即定死，不回头	枚举所有选择，取最优
依赖子问题	一个	多个，且重叠
时间复杂度	通常 O(n log n) 或 O(n²)	通常 O(n²)、O(n³) 或 O(nC)
正确性	需证贪心选择性质	只需证最优子结构
典型	活动安排、MST、Dijkstra、Huffman	矩阵连乘、背包、LCS

判别口诀：若每一步的最优选择不会让后续失去更优的可能，用贪心；若当前选择会影响后续可选集合的大小，用 DP。 0-1 背包就是典型反例——按单位价值贪心会因装不下而浪费容量，必须 DP。

易错点

1. 活动安排按开始时间或持续时间排序，两个都是错解。
2. Dijkstra 用于含负权边的图，结果偏大。
3. 认为 MST 唯一，或认为 MST 上两点路径就是最短路径。
4. Kruskal 不用并查集而用 DFS 判环，复杂度退化到 O(mn)。
5. 只写贪心策略不给证明，考试按"未证明"扣分。

这一章在整门课里的位置

本章的最佳搭档是第 3 章：两者都要求最优子结构，区别只在"敢不敢立即承诺"。第 5、6 章的回溯与分支限界可以看作"不敢承诺时的补救"——用搜索代替贪心。第 8 章的近似算法大量借用贪心（顶点覆盖的 2-近似、TSP 的 MST 近似），第 10 章的剪枝也常以贪心解作为初始上界。

本文是《算法设计与分析（89 讲）》第 4 章的知识点摘要。完整板书与代码见 课程页；上一章 动态规划，下一章 回溯法。