贪心算法
概述
贪心算法是一种在每一步做出局部最优选择的算法设计范式，期望通过一系列局部最优选择达到全局最优解。贪心算法的有效性依赖于两个核心性质：贪心选择性质和最优子结构。与动态规划的”先求解后选择”不同，贪心算法采用"先选择后求解"的策略，通常效率更高但适用范围更窄。
定义
贪心算法（Greedy Algorithm）
贪心算法是一种通过一系列局部最优（贪心）选择来构造全局最优解的算法。在每一步决策中，贪心算法做出当前看来最好的选择，而不考虑未来的后果。这种”短视”策略之所以有效，是因为问题本身具有贪心选择性质——局部最优选择可以导向全局最优解。
核心性质
1. 贪心算法的两个核心前提
贪心算法的正确性依赖于以下两个性质：
- 贪心选择性质：可以通过做出局部最优选择来产生全局最优解。这意味着贪心选择总是安全的——做出贪心选择后，剩余的子问题仍然有最优解，且贪心选择与子问题的最优解组合在一起构成原问题的全局最优解。
- 最优子结构：原问题的最优解包含子问题的最优解。做出贪心选择后，剩余的子问题本身也必须是最优求解的。
2. 与动态规划的本质区别
| 特征 | 贪心算法 | 动态规划 |
|---|---|---|
| 决策方式 | 先选择后求解 | 先求解后选择 |
| 子问题依赖 | 做出选择后只剩一个子问题 | 需要考虑所有子问题 |
| 核心性质 | 贪心选择性质 + 最优子结构 | 最优子结构 + 重叠子问题 |
| 适用条件 | 更严格（需要贪心选择性质） | 较宽松（只需最优子结构） |
| 典型复杂度 | 或更低 | 或更高 |
| 全局最优性 | 不一定保证（需严格证明） | 保证（在最优子结构成立时） |
3. 0-1背包 vs. 分数背包的经典对比
这两个问题是说明贪心与动态规划区别的最佳例子：
- 0-1背包：物品不可分割，贪心策略（选单位价值最高的）不保证最优，必须用动态规划
- 分数背包：物品可以分割，贪心策略（选单位价值最高的）保证最优
0-1背包反例：
背包容量 W = 50
物品1: 重量 10, 价值 60 (单位价值 6)
物品2: 重量 20, 价值 100 (单位价值 5)
物品3: 重量 30, 价值 120 (单位价值 4)
贪心（选单位价值最高）：选物品1(10,60) + 物品2(20,100) = 30/50, 价值 160
最优解：选物品2(20,100) + 物品3(30,120) = 50/50, 价值 220
分数背包（同一实例）：
贪心：选物品1全部(10,60) + 物品2全部(20,100) + 物品3的20/30(20,80) = 50/50, 价值 240
这就是最优解
4. 贪心算法的六步设计法
- 确定问题的最优子结构
- 设计一个递归算法（基于最优子结构）
- 证明贪心选择性质：如果在每一步做出贪心选择，则只剩下一个子问题
- 证明最优子结构：做出贪心选择后，与子问题的最优解组合得到原问题的最优解
- 开发递归贪心算法
- 转化为迭代算法（如果可能）
5. 贪心正确性证明的核心技术
- 替换论证（Exchange Argument）：取最优解，逐步替换为贪心选择，证明替换后仍然最优
- 本章中的三个应用：
- Theorem 15.1（活动选择）：替换最优解中最早结束的活动
- Lemma 15.2（Huffman编码）：替换最优编码树中最深层的叶节点
- Theorem 15.5（离线缓存）：四性质归纳构造，逐步对齐贪心解和最优解
经典问题汇总
| 问题 | 贪心策略 | 时间复杂度 | 正确性证明 |
|---|---|---|---|
| 活动选择问题 | 选最早结束的活动 | 替换论证 (Thm 15.1) | |
| 哈夫曼编码 | 合并频率最低的两个节点 | 替换论证 (Lem 15.2) | |
| 离线缓存 | 替换最远将来使用的项 | 四性质归纳 (Thm 15.5) | |
| 分数背包 | 选单位价值最高的物品 | 贪心选择性质 | |
| Dijkstra最短路 | 选距离最近的未访问节点 | 贪心选择性质 | |
| 最小生成树 | 选权值最小的安全边 | 剪切性质 |
章节扩展
- 15.1 活动选择问题 — 贪心算法的入门示例
- 15.2 贪心策略要素 — 贪心算法设计要素的系统总结
- 15.3 哈夫曼编码 — 贪心算法的经典应用
- 15.4 离线缓存 — 缓存替换中的贪心策略
第21章：最小生成树
MST问题是贪心策略的经典应用。安全边定理（定理21.1）充当贪心选择性质：横跨割的轻边一定是某棵MST的安全边。GENERIC-MST循环选择安全边加入A，保证A始终是某MST的子集。Kruskal按全局边权排序贪心选择，Prim按局部最小key贪心扩展。
第22章：单源最短路径
Dijkstra算法具有贪心性质：每次从优先队列中取出 d 值最小的顶点 u，其最短距离已确定（不会再被更新）。这一”贪心选择”的正确性依赖于所有边权非负——保证已确定的距离不会被后续松弛减小。