数据结构与算法 / 系统课时
交换论证
交换论证
交换论证用于回答一个关键问题:贪心算法只做眼前最优选择,为什么不会错过全局最优解?本课将把“局部替换不变差”写成可复用的证明结构,并用最小化总完成时间说明如何从一次交换推导整体最优。
学习目标
- 识别最优解中与贪心选择冲突的局部结构。
- 证明一次交换保持可行性,且目标值不会变差。
- 使用连续交换把任意最优解改造成符合贪心顺序的最优解。
问题与证明直觉
交换论证不直接计算所有方案,而是假设已经存在一个最优解,再把其中“不符合贪心规则”的局部部分替换掉。只要替换后仍然可行,且目标值不劣,就能说明至少存在一个最优解包含当前贪心选择。
这类证明通常依赖三个对象:贪心选择、一个任意最优解,以及连接二者的局部交换。真正需要证明的不是“贪心看起来更好”,而是交换前后的可行性与目标值关系。

核心原理
设最优解为 ,贪心规则要求局部结构为 。若 已包含 ,这一轮无需处理;若不包含,就在 中找到与 冲突的结构 ,再构造替换后的解 。
一次有效交换必须同时满足:
- 仍满足原问题的全部约束。
- 的目标值不差于 。
- 比 更接近贪心结构。
重复执行后,可以把某个最优解变成完全符合贪心规则的解。由于每次交换都不使目标值变差,最终贪心解也是最优解。
标准证明模板
交换论证可以按以下顺序书写:
- 明确贪心规则,并取一个任意最优解 。
- 找到 中第一个违反贪心规则的位置。
- 交换该位置的两个元素,或用贪心元素替换冲突元素。
- 分别证明交换后的可行性和目标值关系。
- 说明交换减少了一个逆序或冲突,因此过程必然终止。
- 得出存在一个最优解与贪心解完全一致。
“目标值不变”与“目标值变好”都足够。若从最优解交换后还能严格变好,反而说明原方案不可能最优;这常用于排除逆序结构。
示例:最小化总完成时间
有若干任务在一台机器上顺序执行,任务 的处理时间为 。所有任务在时刻 0 可用,目标是最小化完成时间总和 。贪心策略是按处理时间从小到大排序,即最短处理时间优先。
假设某个最优调度中存在相邻逆序任务 ,且 。设它们之前已经经过时间 。交换前,这两个任务对总完成时间的贡献为:
交换后,贡献变为:
交换前减去交换后得到 ,因此把较短任务移到前面会严格减小总完成时间。两项之前的任务不受影响,两项之后的任务开始时间也不变,所以整个调度仍然可行。
任何未按处理时间升序排列的调度都至少包含一个相邻逆序。持续交换逆序后,最终得到按 非递减排列的调度,而且目标值只会下降。因此最短处理时间优先必然最优。排序耗时为 ,生成调度顺序耗时为 。
常见误区与练习
常见错误是只写“交换后更合理”,却没有计算目标值;或者只比较被交换的两个任务,遗漏对后续任务的影响。交换论证必须明确指出哪些部分变化、哪些部分保持不变。
练习一:证明在总完成时间目标下,处理时间相同的相邻任务互换不会改变目标值,并说明这对最优解的唯一性意味着什么。
练习二:考虑每个任务带权重 ,目标改为最小化 。比较相邻任务 的两种顺序,推导何时应让 排在 前,并写出对应的排序关键字。验收条件是给出完整的不等式推导,而不是只写结论。
本课总结
- 交换论证通过修改一个最优解,证明贪心选择可以安全地出现在某个最优解中。
- 每次交换都必须同时证明可行性、目标值不变差和过程可终止。
- 相邻逆序是最常见的交换入口,适合处理排序型贪心策略。
下一课预告
下一课将学习“保持领先证明”,不再改造最优解,而是逐步比较贪心解与任意可行解的前缀进度。