【学习】《算法图解》第十章学习笔记：贪婪算法

# 一、贪婪算法概述 贪婪算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是最好或最优的算法。贪婪算法不从整体最优上加以考虑，它所做出的选择只是在某种意义上的局部最优选择。 ## （一）算法适用场景 贪婪算法适用于具有"贪心选择性质"的问题，即局部最优选择能导致全局最优解的问题。主要应用于： - 需要求解最优化问题 - 问题具有贪心选择性质 - 问题具有最优子结构性质 ## （二）算法基本特点 1. **简单直接**：思路简单，容易实现 2. **局部最优选择**：每步都选择当前看起来最优的解 3. **不可回退**：一旦做出选择，不再更改 4. **不保证全局最优**：在某些问题上可能无法得到全局最优解 # 二、算法步骤详解 ## （一）算法流程 贪婪算法的一般流程如下： 1. 建立数学模型，定义最优化目标 2. 将问题分解为若干个子问题 3. 对每个子问题做出贪心选择（局部最优） 4. 将贪心选择合并成最终解决方案 ## （二）图示说明 贪婪算法通常按照以下流程执行： 1. 创建一个空结果集 2. 按照某种顺序遍历所有可能的选择 3. 对于每个选择，检查是否可以加入结果集 4. 如果可以，则加入结果集 5. 重复步骤2-4，直到问题解决 # 三、经典贪婪算法问题 ## （一）教室调度问题 ### 1. 问题描述 有一系列的课程，每个课程都有开始时间和结束时间，如何安排才能使用同一个教室上最多的课？ ### 2. 贪婪策略 按照课程的**结束时间**进行排序，每次选择结束最早且与已选课程不冲突的课程。 ### 3. 代码实现 ```python 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 scheduled ``` ### 4. 正确性分析 这个贪婪策略能得到最优解，因为选择结束时间最早的课程，可以为后面的课程留出更多的时间。 ## （二）背包问题 ### 1. 问题描述 有一个背包，最多能承受重量为W的物品。现在有n个物品，每个物品有重量和价值两个属性。如何选择物品放入背包，使得背包中物品的总价值最大？ ### 2. 分数背包问题（可分割物品） 对于可分割的物品，贪婪算法可以得到最优解： - 计算每个物品的单位价值（价值/重量） - 按单位价值从高到低排序 - 尽可能多地装入单位价值最高的物品 ```python 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_value ``` ### 3. 0-1背包问题（不可分割物品） 对于0-1背包问题（物品不可分割），贪婪算法通常不能得到最优解，需要使用动态规划。 ## （三）集合覆盖问题 ### 1. 问题描述 给定一个集合S和若干子集，选择尽可能少的子集，使得这些子集的并集等于S。 ### 2. 贪婪策略 每次选择能覆盖最多尚未覆盖元素的子集。 ```python 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_subsets ``` ### 3. 近似比 集合覆盖问题是NP完全问题，贪婪算法提供的是近似解，其近似比为ln(n)，其中n是集合S的大小。 # 四、算法分析 ## （一）时间复杂度 贪婪算法的时间复杂度取决于具体问题和实现方式： - 教室调度问题：O(n log n)，主要是排序的复杂度 - 分数背包问题：O(n log n)，主要是排序的复杂度 - 集合覆盖问题：O(n × m)，其中n是集合大小，m是子集数量 ## （二）空间复杂度 贪婪算法通常具有较低的空间复杂度，主要用于存储中间结果和最终解决方案： - 大多数情况下为O(n) - 有时可以优化到O(1)，通过就地修改输入数据 ## （三）算法优缺点 优点： - 实现简单，思路直观 - 计算速度快，效率高 - 部分问题能得到最优解 缺点： - 不保证得到全局最优解 - 适用范围有限 - 有时难以证明算法正确性 # 五、贪婪算法与动态规划的比较 ## （一）相同点 1. 都是通过组合子问题的解来构造原问题的解 2. 都是求解最优化问题的方法 3. 都需要问题具有最优子结构性质 ## （二）不同点 | 特性 | 贪婪算法 | 动态规划 | |------|----------|----------| | 子问题处理 | 每步只解决一个子问题 | 解决所有子问题 | | 决策过程 | 做出选择后不再更改 | 根据之前所有结果做出选择 | | 适用范围 | 具有贪心选择性质的问题 | 具有重叠子问题和最优子结构的问题 | | 效率 | 通常效率更高，复杂度更低 | 通常需要更多的时间和空间 | | 正确性 | 不总是得到最优解 | 保证得到最优解 | # 六、贪婪算法的应用 ## （一）实际应用场景 1. **Huffman编码**：构建最优前缀码，用于数据压缩 2. **Prim和Kruskal算法**：寻找最小生成树 3. **Dijkstra算法**：寻找单源最短路径 4. **任务调度问题**：最优分配资源 5. **网络流量控制**：最大化网络吞吐量 ## （二）算法变种和改进 1. **随机贪心算法**：引入随机性，避免陷入局部最优 2. **启发式贪心算法**：结合启发信息，提高解的质量 3. **多阶段贪心算法**：在不同阶段使用不同的贪心策略 # 七、如何判断问题是否适合使用贪婪算法 ## （一）贪心选择性质 问题的整体最优解可以通过一系列局部最优的选择来达到。换句话说，每一步的最优选择最终会导致全局最优解。 ## （二）最优子结构性质 问题的最优解包含其子问题的最优解。这意味着，一旦我们知道了子问题的最优解，就可以直接构造出原问题的最优解。 ## （三）验证方法 1. 尝试使用反证法证明贪婪选择是安全的 2. 尝试构造反例，看贪婪算法是否能得到最优解 3. 与其他算法（如动态规划）的结果进行比较 # 八、总结 贪婪算法是一种简单而强大的算法设计范式，它在每一步都做出当前看起来最好的选择。虽然不能保证在所有问题上都能得到最优解，但在具有贪心选择性质的问题上，它能高效地得到最优解或接近最优的解。 理解贪婪算法的关键在于： 1. 识别问题是否具有贪心选择性质 2. 设计合适的贪心策略 3. 证明贪心策略的正确性 贪婪算法的简单性和效率使其成为算法设计中的重要工具，尤其是在处理优化问题时。通过与动态规划、回溯等算法相结合，可以解决更加复杂的问题。 # 参考资料 1. 《算法图解》第十章，Aditya Bhargava 著 2. Introduction to Algorithms, Thomas H. Cormen et al. 3. Algorithm Design Manual, Steven S. Skiena 4. [维基百科：贪心算法](https://en.wikipedia.org/wiki/Greedy_algorithm) 5. [Khan Academy: Greedy Algorithms](https://www.khanacademy.org/computing/computer-science/algorithms) 本文由[mdnice](https://mdnice.com/?platform=6)多平台发布
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容