贪心算法

概述

1. 贪心算法（Greedy Algorithm）是一种构造性算法，用于解决最优化问题
2. 其核心思想是在每一步选择中，都采取当前状态下最优的选择，期望通过一系列局部最优的选择达到全局最优
3. 贪心算法在许多实际问题中非常有效，但并不是所有问题都适用

特点

1. 局部最优选择
   1. 每一步都选择当前状态下的最佳解决方案，不考虑未来可能的后果
2. 全局最优性
   1. 在某些问题中，局部最优选择能够确保全局最优解决方案，但并不是所有问题都满足这一条件
3. 无需回溯
   1. 一旦做出选择，不需要回退或修改之前的选择

适用场景

1. 贪心选择性质：
   1. 问题在每一步选择时，局部最优选择不会影响全局最优解的正确性
2. 最优子结构性质：
   1. 问题能够分解为子问题，并且子问题的最优解可以递归地构建成全局最优解

优缺点

优点

1. 简单易行：
   1. 贪心算法通常比较简单，容易实现
2. 高效：
   1. 大多数情况下，贪心算法的时间复杂度较低，能够在较短时间内得到结果

缺点

1. 局限性：
   1. 贪心算法并不总是能保证得到全局最优解，尤其是当问题不满足贪心选择性质和最优子结构性质时
2. 适用性有限：
   1. 只有部分优化问题适合使用贪心算法

应用实例

1. 活动选择问题
   1. 选择最多的活动在不重叠的情况下
2. 背包问题
   1. 选择物品放入背包，以达到最大价值（适用于分数背包问题）
3. 哈弗曼编码
   1. 最优编码树的构建，用于数据压缩
4. 最小生成树问题
   1. Kruskal 和 Prim 算法
5. 单源最短路径问题
   1. 狄克斯特拉Dijkstra 算法（适用于非负权重的图）

算法示例

活动选择问题

1. 给定一组活动，每个活动有一个开始时间和结束时间，选择尽可能多的活动使它们不重叠
2. 代码：

3. return a1.end < a2.end;
   1. 这个比较的效果，就是把所有活动按活动结束时间进行排序
   2. 选择最早结束的活动一方面可以给剩下的活动留出更多可选的时间
   3. 一方面可以最大限度地避免活动之间的重叠冲突

背包问题

1. 给定一组物品，每个物品有一个重量和价值，选择放入背包中的物品使得总价值最大化，允许分割物品
2. 代码：