【算法笔记】贪心法--介绍
2021-02-21
1 min read
- 优化子结构
若一个优化问题的优化解包含它的 子问题的优化解，则称其具有优化子结构
- 贪心选择性
若一个优化问题的全局优化解可以通过 局部优化选择得到，则该问题称为具有 贪心选择性.
使用贪心算法解决问题时：
-
设计贪心方法
-
证明贪心法的正确性（有时比设计算法更重要）
例：活动最大相容问题
（1） 证明优化子结构
活动按照结束时间已经排好序
即证明：设A是问题S的一个优化解且包含活动1，则A-{1}是问题S’（S’中最早的开始时间晚于f1）的优化解
反证法（略）
（2）证明贪心选择性
归纳法（略）