贪心算法的正确性
大约 2 分钟
贪心算法的正确性
贪心算法(Greedy Algorithm)是一类在每一步都做出当前最优选择,期望通过局部最优达到全局最优的算法。
正确性判定的核心思想
贪心算法并不总是正确,只有满足特定条件时才可用。判断贪心算法正确性的常用方法有:
1. 最优子结构
- 问题的最优解包含其子问题的最优解。
- 例:最短路径、区间调度。
2. 无后效性
- 某一步的选择不会影响后续状态,只与当前状态有关。
- 例:活动选择问题。
3. 贪心选择性质
- 通过局部最优选择能得到全局最优解。
- 例:找零问题、哈夫曼编码。
常见证明方法
- 反证法:假设贪心解不是最优解,构造矛盾。
- 归纳法:证明每一步贪心选择后,剩下的子问题仍满足贪心性质。
- 交换法:将最优解中的非贪心选择与贪心选择交换,最终可变为贪心解且不劣于原解。
典型例题
1. 区间选点/区间调度
- 每次选择右端点最小的区间,能保证全局最优。
- 证明:交换法或反证法。
2. 找零问题
- 每次优先用面值最大的硬币。
- 只有当硬币面值满足特定条件(如完全背包、标准币种)时贪心才正确。
3. 哈夫曼编码
- 每次合并权值最小的两个节点。
- 归纳法证明其最优性。
反例:贪心不正确的情况
- 有些问题贪心不能保证最优,如背包问题(0-1背包)、部分图最短路等。
总结
- 贪心算法正确性需严格证明,不能凭直觉。
- 常用最优子结构、无后效性、贪心选择性质三大标准。
- 证明方法以反证法、归纳法、交换法为主。
参考: