数据结构与算法 / 系统课时

交换论证

交换论证

交换论证用于回答一个关键问题:贪心算法只做眼前最优选择,为什么不会错过全局最优解?本课将把“局部替换不变差”写成可复用的证明结构,并用最小化总完成时间说明如何从一次交换推导整体最优。

学习目标

  • 识别最优解中与贪心选择冲突的局部结构。
  • 证明一次交换保持可行性,且目标值不会变差。
  • 使用连续交换把任意最优解改造成符合贪心顺序的最优解。

问题与证明直觉

交换论证不直接计算所有方案,而是假设已经存在一个最优解,再把其中“不符合贪心规则”的局部部分替换掉。只要替换后仍然可行,且目标值不劣,就能说明至少存在一个最优解包含当前贪心选择。

这类证明通常依赖三个对象:贪心选择、一个任意最优解,以及连接二者的局部交换。真正需要证明的不是“贪心看起来更好”,而是交换前后的可行性与目标值关系。

交换论证中相邻逆序任务的替换过程

核心原理

设最优解为 OO,贪心规则要求局部结构为 GG。若 OO 已包含 GG,这一轮无需处理;若不包含,就在 OO 中找到与 GG 冲突的结构 XX,再构造替换后的解 O′O'。

一次有效交换必须同时满足:

  1. O′O' 仍满足原问题的全部约束。
  2. O′O' 的目标值不差于 OO。
  3. O′O' 比 OO 更接近贪心结构。

重复执行后,可以把某个最优解变成完全符合贪心规则的解。由于每次交换都不使目标值变差,最终贪心解也是最优解。

标准证明模板

交换论证可以按以下顺序书写:

  1. 明确贪心规则,并取一个任意最优解 OO。
  2. 找到 OO 中第一个违反贪心规则的位置。
  3. 交换该位置的两个元素,或用贪心元素替换冲突元素。
  4. 分别证明交换后的可行性和目标值关系。
  5. 说明交换减少了一个逆序或冲突,因此过程必然终止。
  6. 得出存在一个最优解与贪心解完全一致。

“目标值不变”与“目标值变好”都足够。若从最优解交换后还能严格变好,反而说明原方案不可能最优;这常用于排除逆序结构。

示例:最小化总完成时间

有若干任务在一台机器上顺序执行,任务 ii 的处理时间为 pip_i。所有任务在时刻 0 可用,目标是最小化完成时间总和 ∑Ci\sum C_i。贪心策略是按处理时间从小到大排序,即最短处理时间优先。

假设某个最优调度中存在相邻逆序任务 a,ba,b,且 pa>pbp_a>p_b。设它们之前已经经过时间 TT。交换前,这两个任务对总完成时间的贡献为:

(T+pa)+(T+pa+pb)(T+p_a)+(T+p_a+p_b)

交换后,贡献变为:

(T+pb)+(T+pb+pa)(T+p_b)+(T+p_b+p_a)

交换前减去交换后得到 pa−pb>0p_a-p_b>0,因此把较短任务移到前面会严格减小总完成时间。两项之前的任务不受影响,两项之后的任务开始时间也不变,所以整个调度仍然可行。

任何未按处理时间升序排列的调度都至少包含一个相邻逆序。持续交换逆序后,最终得到按 pip_i 非递减排列的调度,而且目标值只会下降。因此最短处理时间优先必然最优。排序耗时为 O(nlog⁡n)O(n\log n),生成调度顺序耗时为 O(n)O(n)。

常见误区与练习

常见错误是只写“交换后更合理”,却没有计算目标值;或者只比较被交换的两个任务,遗漏对后续任务的影响。交换论证必须明确指出哪些部分变化、哪些部分保持不变。

练习一:证明在总完成时间目标下,处理时间相同的相邻任务互换不会改变目标值,并说明这对最优解的唯一性意味着什么。

练习二:考虑每个任务带权重 wiw_i,目标改为最小化 ∑wiCi\sum w_iC_i。比较相邻任务 a,ba,b 的两种顺序,推导何时应让 aa 排在 bb 前,并写出对应的排序关键字。验收条件是给出完整的不等式推导,而不是只写结论。

本课总结

  • 交换论证通过修改一个最优解,证明贪心选择可以安全地出现在某个最优解中。
  • 每次交换都必须同时证明可行性、目标值不变差和过程可终止。
  • 相邻逆序是最常见的交换入口,适合处理排序型贪心策略。

下一课预告

下一课将学习“保持领先证明”,不再改造最优解,而是逐步比较贪心解与任意可行解的前缀进度。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

交换论证

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通