跳到主要内容

贪心算法

贪心算法解决什么问题？​

  • 定义: 分步决策的算法, 在每个决策阶段选择当前看起来最优的解;
  • 期望: 局部最优的累积能导出全局最优;
  • 代价: 每步只做一次选择, 通常时间与空间都优于动态规划;
  • 风险: 局部最优不保证全局最优, 必须验证问题具备贪心性质;

贪心算法需要哪两个性质？​

  • 贪心选择性质: 全局最优解可以通过一系列局部最优选择得到;
  • 最优子结构: 问题的最优解包含其子问题的最优解;
  • 与动态规划的区别: 动态规划会保留所有子问题的解再比较, 贪心只保留当前一个选择且不回退;
  • 判定方法: 尝试用交换论证证明"任何最优解都能替换为含当前贪心选择的最优解";

贪心的解题思路分哪几步？​

  • 转换: 作出当前选择, 再把剩余部分视为同构的子问题;
  • 贪心选择性质: 定义"当前最优"的判据, 例如取最大、取最小、取差值最大;
  • 最优子结构: 说明局部最优如何合成全局最优;
  • 实现: 多数贪心只需一次线性扫描加若干变量, 不需要递归;

如何用交换论证验证贪心策略？​

  • 形式: 假设存在最优解 OO 不含贪心选择 gg;
  • 替换: 构造 O′=O−x+gO' = O - x + g, 证明 O′O' 依然可行且不劣于 OO;
  • 结论: 若替换总能成立, 则贪心选择安全;
  • 应用: 分发糖果的两次遍历、加油站的起点跳过都可用该论证说明;
  • 实例: 见 贪心的经典应用;