【学习】《算法图解》第十章学习笔记：贪婪算法
一、贪婪算法概述
贪婪算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是最好或最优的算法。贪婪算法不从整体最优上加以考虑，它所做出的选择只是在某种意义上的局部最优选择。
（一）算法适用场景
贪婪算法适用于具有”贪心选择性质”的问题，即局部最优选择能导致全局最优解的问题。主要应用于：
- 需要求解最优化问题
- 问题具有贪心选择性质
- 问题具有最优子结构性质
（二）算法基本特点
- 简单直接：思路简单，容易实现
- 局部最优选择：每步都选择当前看起来最优的解
- 不可回退：一旦做出选择，不再更改
- 不保证全局最优：在某些问题上可能无法得到全局最优解
二、算法步骤详解
（一）算法流程
贪婪算法的一般流程如下：
- 建立数学模型，定义最优化目标
- 将问题分解为若干个子问题
- 对每个子问题做出贪心选择（局部最优）
- 将贪心选择合并成最终解决方案
（二）图示说明
贪婪算法通常按照以下流程执行：
- 创建一个空结果集
- 按照某种顺序遍历所有可能的选择
- 对于每个选择，检查是否可以加入结果集
- 如果可以，则加入结果集
- 重复步骤2-4，直到问题解决
三、经典贪婪算法问题
（一）教室调度问题
1. 问题描述
有一系列的课程，每个课程都有开始时间和结束时间，如何安排才能使用同一个教室上最多的课？
2. 贪婪策略
按照课程的结束时间进行排序，每次选择结束最早且与已选课程不冲突的课程。
3. 代码实现
def schedule_classes(classes):
# 按结束时间排序
scheduled = []
classes.sort(key=lambda x: x[1]) # 按结束时间排序
# 选择第一个课程
scheduled.append(classes[0])
last_end_time = classes[0][1]
# 遍历剩余课程
for i in range(1, len(classes)):
if classes[i][0] >= last_end_time: # 如果开始时间晚于上一个结束时间
scheduled.append(classes[i])
last_end_time = classes[i][1]
return scheduled4. 正确性分析
这个贪婪策略能得到最优解，因为选择结束时间最早的课程，可以为后面的课程留出更多的时间。
（二）背包问题
1. 问题描述
有一个背包，最多能承受重量为W的物品。现在有n个物品，每个物品有重量和价值两个属性。如何选择物品放入背包，使得背包中物品的总价值最大？
2. 分数背包问题（可分割物品）
对于可分割的物品，贪婪算法可以得到最优解：
- 计算每个物品的单位价值（价值/重量）
- 按单位价值从高到低排序
- 尽可能多地装入单位价值最高的物品
def fractional_knapsack(items, capacity):
# 计算每个物品的单位价值
for item in items:
item['value_per_weight'] = item['value'] / item['weight']
# 按单位价值排序
items.sort(key=lambda x: x['value_per_weight'], reverse=True)
total_value = 0
remaining_capacity = capacity
for item in items:
if remaining_capacity >= item['weight']:
# 可以完全装入
total_value += item['value']
remaining_capacity -= item['weight']
else:
# 只能装入一部分
fraction = remaining_capacity / item['weight']
total_value += item['value'] * fraction
break
return total_value3. 0-1背包问题（不可分割物品）
对于0-1背包问题（物品不可分割），贪婪算法通常不能得到最优解，需要使用动态规划。
（三）集合覆盖问题
1. 问题描述
给定一个集合S和若干子集，选择尽可能少的子集，使得这些子集的并集等于S。
2. 贪婪策略
每次选择能覆盖最多尚未覆盖元素的子集。
def set_covering(universe, subsets):
# 需要覆盖的元素
elements_to_cover = set(universe)
# 已选择的子集
selected_subsets = []
# 当还有元素未被覆盖时
while elements_to_cover:
# 选择能覆盖最多未覆盖元素的子集
best_subset = None
covered_elements = set()
for subset in subsets:
# 计算该子集能新覆盖的元素
new_covered = set(subset) & elements_to_cover
if len(new_covered) > len(covered_elements):
best_subset = subset
covered_elements = new_covered
# 如果找不到能覆盖新元素的子集，则退出
if not best_subset:
break
# 选择这个子集
selected_subsets.append(best_subset)
# 更新未覆盖元素
elements_to_cover -= set(best_subset)
return selected_subsets3. 近似比
集合覆盖问题是NP完全问题，贪婪算法提供的是近似解，其近似比为ln(n)，其中n是集合S的大小。
四、算法分析
（一）时间复杂度
贪婪算法的时间复杂度取决于具体问题和实现方式：
- 教室调度问题：O(n log n)，主要是排序的复杂度
- 分数背包问题：O(n log n)，主要是排序的复杂度
- 集合覆盖问题：O(n × m)，其中n是集合大小，m是子集数量
（二）空间复杂度
贪婪算法通常具有较低的空间复杂度，主要用于存储中间结果和最终解决方案：
- 大多数情况下为O(n)
- 有时可以优化到O(1)，通过就地修改输入数据
（三）算法优缺点
优点：
- 实现简单，思路直观
- 计算速度快，效率高
- 部分问题能得到最优解
缺点：
- 不保证得到全局最优解
- 适用范围有限
- 有时难以证明算法正确性
五、贪婪算法与动态规划的比较
（一）相同点
- 都是通过组合子问题的解来构造原问题的解
- 都是求解最优化问题的方法
- 都需要问题具有最优子结构性质
（二）不同点
| 特性 | 贪婪算法 | 动态规划 |
|---|---|---|
| 子问题处理 | 每步只解决一个子问题 | 解决所有子问题 |
| 决策过程 | 做出选择后不再更改 | 根据之前所有结果做出选择 |
| 适用范围 | 具有贪心选择性质的问题 | 具有重叠子问题和最优子结构的问题 |
| 效率 | 通常效率更高，复杂度更低 | 通常需要更多的时间和空间 |
| 正确性 | 不总是得到最优解 | 保证得到最优解 |
六、贪婪算法的应用
（一）实际应用场景
- Huffman编码：构建最优前缀码，用于数据压缩
- Prim和Kruskal算法：寻找最小生成树
- Dijkstra算法：寻找单源最短路径
- 任务调度问题：最优分配资源
- 网络流量控制：最大化网络吞吐量
（二）算法变种和改进
- 随机贪心算法：引入随机性，避免陷入局部最优
- 启发式贪心算法：结合启发信息，提高解的质量
- 多阶段贪心算法：在不同阶段使用不同的贪心策略
七、如何判断问题是否适合使用贪婪算法
（一）贪心选择性质
问题的整体最优解可以通过一系列局部最优的选择来达到。换句话说，每一步的最优选择最终会导致全局最优解。
（二）最优子结构性质
问题的最优解包含其子问题的最优解。这意味着，一旦我们知道了子问题的最优解，就可以直接构造出原问题的最优解。
（三）验证方法
- 尝试使用反证法证明贪婪选择是安全的
- 尝试构造反例，看贪婪算法是否能得到最优解
- 与其他算法（如动态规划）的结果进行比较
八、总结
贪婪算法是一种简单而强大的算法设计范式，它在每一步都做出当前看起来最好的选择。虽然不能保证在所有问题上都能得到最优解，但在具有贪心选择性质的问题上，它能高效地得到最优解或接近最优的解。
理解贪婪算法的关键在于：
- 识别问题是否具有贪心选择性质
- 设计合适的贪心策略
- 证明贪心策略的正确性
贪婪算法的简单性和效率使其成为算法设计中的重要工具，尤其是在处理优化问题时。通过与动态规划、回溯等算法相结合，可以解决更加复杂的问题。
参考资料
- 《算法图解》第十章，Aditya Bhargava 著
- Introduction to Algorithms, Thomas H. Cormen et al.
- Algorithm Design Manual, Steven S. Skiena
- 维基百科：贪心算法
- Khan Academy: Greedy Algorithms