证明或推翻贪心策略
复习
- 贪心选择：每一步只选当前最优
- 算法与正确性：正确性需要论证
- 最小生成树：贪心正确的例子
TL;DR
- 贪心策略可能正确，也可能错误
- 证明常用“交换论证”
- 推翻只需给出一个反例
- 设计贪心时，先找反例，再想证明
正文
上一章说，贪心的关键不在写代码，而在判断它到底对不对。这一章就来谈两种基本手法：证明与推翻。
一个反例就够了
要推翻一个贪心策略，最省事的办法是找出一个反例：构造一组输入，让贪心选择的方案不如最优解。
比如 0/1 背包问题——每件物品要么拿、要么不拿。如果贪心地“优先拿单位价值最高的”，可能因为拿了一件“性价比高但很占容量”的物品，导致装不下另一件更合适的组合。给出这样的一个例子，贪心就被推翻了。
反例的价值在于：它不需要证明“永远错”，只要证明“至少错一次”，就足以否定这个策略。
交换论证
要证明一个贪心正确，常用的方法叫交换论证（exchange argument）。思路是：
- 假设存在一个最优解
- 如果它没有采用贪心的第一个选择，就试着把它“换”成贪心的选择
- 证明换完之后，结果不会变差
- 这样一步步替换，最优解就能变成贪心解，说明贪心也是最优的
换句话说，交换论证要说明：贪心的选择可以被“安插”进某个最优解里，而不损害最优性。 这正好对应上一章说的“最优解包含当前最优的选择”。
两个例子对照
- 活动选择问题：想安排尽可能多互不冲突的活动，贪心地“每次选结束最早的那个”是正确的，可以用交换论证证明 - 0/1 背包问题：按单位价值贪心会出错，反例就能推翻 - 但分数背包（物品可以拆开）贪心又对了——因为可以“只拿一部分”，情况不同
你看，同一个问题，条件稍变，贪心的正确性就完全不同。所以永远不要凭直觉说“贪心肯定行”，要么找到反例，要么给出证明。
当然，有些问题连贪心都不适用，需要更强的工具。下一章开始，我们进入动态规划。
思考题 1
“交换论证”想说明什么？
思考题 2
要推翻一个贪心策略，最有效的方法是什么？
小结
知识点
- 贪心的正确性需要证明或推翻
- 反例可以否定一个贪心策略
- 交换论证通过“替换不变差”来证明贪心正确
- 条件变化可能改变贪心的正确性
参考资料
- Wikipedia(zh)：贪心算法：包含正确性论证
- Wikipedia(zh)：活动选择问题：贪心正确的经典例子
思考题答案（仅供参考）
思考题 1
它想说明贪心的选择不会损害最优性：从任意一个最优解出发，若它没选贪心的那一步，就可以把某个选择替换成贪心的选择，且结果不变差。反复替换即可得到贪心解，从而证明贪心也是最优的。
思考题 2
构造一个反例：找一组具体输入，使贪心的结果不如最优解。只要存在这样一个反例，就足以推翻该贪心策略，无需证明它“永远错”。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪