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

保持领先证明

保持领先证明

保持领先证明通过比较两个方案在每一步的进度,说明贪心解始终不落后于任意竞争方案。本课将建立“选择比较指标、证明前缀领先、推出整体最优”的完整链条,并用于活动调度问题。

学习目标

  • 为贪心解与竞争解定义可逐步比较的进度指标。
  • 使用数学归纳法证明贪心解在每个前缀上保持领先。
  • 从前缀优势推出最终解的最优性,并识别不合适的比较指标。

证明思路

保持领先法不修改某个最优解,而是把贪心解 G=(g1,g2,…)G=(g_1,g_2,\ldots) 与任意竞争解 O=(o1,o2,…)O=(o_1,o_2,\ldots) 并排比较。需要找到一个能够反映“完成得更早、剩余资源更多或累计代价更小”的指标,并证明对每个位置 kk,贪心前缀都不劣于竞争前缀。

这种证明通常包含归纳结构:先证明第一个选择领先,再假设第 kk 步领先,利用贪心规则证明第 k+1k+1 步仍领先。最后还要解释为什么“每一步领先”足以推出整体目标最优。

保持领先法比较两个活动调度前缀

标准证明结构

第一步是定义比较指标。指标必须与目标直接相关,并且能按相同的选择序号比较。例如,区间调度中适合比较第 kk 个活动的结束时间;最短路径问题中可能比较到达某个位置的累计距离。

第二步证明基础情况。通常直接由第一次贪心选择的定义得到。

第三步完成归纳。假设第 kk 步贪心解不落后,先证明竞争解的第 k+1k+1 个选择对贪心解也可行,再利用贪心规则推出贪心的第 k+1k+1 个选择不更差。

第四步把领先关系转化为目标结论。仅有不等式还不够,必须说明它如何保证贪心解取得至少相同数量、至少相同收益或至多相同代价。

示例:活动选择问题

给定一组活动,每个活动有开始时间 sis_i 和结束时间 fif_i。同一资源一次只能执行一个活动,目标是选择数量最多的两两兼容活动。贪心策略是每次选择当前可选活动中结束时间最早的一个。

设贪心算法依次选择 G=(g1,g2,…,gr)G=(g_1,g_2,\ldots,g_r),任意最优解按时间顺序为 O=(o1,o2,…,om)O=(o_1,o_2,\ldots,o_m)。我们证明对所有同时存在的位置 kk,都有:

f(gk)≤f(ok)f(g_k)\le f(o_k)

基础情况 k=1k=1:g1g_1 是所有活动中结束最早的活动,因此 f(g1)≤f(o1)f(g_1)\le f(o_1)。

归纳假设:f(gk)≤f(ok)f(g_k)\le f(o_k)。因为 OO 内部兼容,所以 ok+1o_{k+1} 满足 s(ok+1)≥f(ok)s(o_{k+1})\ge f(o_k)。结合归纳假设可得 s(ok+1)≥f(gk)s(o_{k+1})\ge f(g_k),说明 ok+1o_{k+1} 也是贪心算法在选择完 gkg_k 后可以考虑的候选活动。

贪心算法从这些候选活动中选择结束时间最早的 gk+1g_{k+1},因此:

f(gk+1)≤f(ok+1)f(g_{k+1})\le f(o_{k+1})

由归纳法,贪心解在每个选择位置都保持领先。若最优解有 mm 个活动,那么贪心解在选出前 m−1m-1 个活动后,omo_m 仍是一个可行候选,所以贪心解至少能选出 mm 个活动。最优解不可能少于贪心解,而贪心解又不少于最优解,因此两者数量相同,贪心解最优。

实现时先按结束时间排序,再线性扫描选择兼容活动,时间复杂度为 O(nlog⁡n)O(n\log n),额外空间取决于排序实现。

与交换论证的区别

交换论证会把一个最优解逐步改造成贪心解,核心问题是“替换后是否仍然最优”。保持领先法则保持两个解不变,核心问题是“贪心前缀是否始终不落后”。

若问题天然具有逐步进度,例如结束时间、当前位置或累计资源,保持领先法通常更直接。若更容易在最优解中定位一个局部冲突,并能安全替换,交换论证通常更合适。

常见误区与练习

最常见的错误是选择了与最终目标无关的指标。例如,只证明贪心方案第 kk 个活动开始更早,并不能保证它结束更早,也不能保证为后续活动留下更多空间。指标必须支持归纳步骤和最终结论。

练习一:构造一组活动,说明“每次选择开始时间最早的活动”不一定得到最多活动,并解释该策略无法建立结束时间保持领先关系的原因。

练习二:为“每次到达加油站时,在当前可达范围内选择最远的下一站”设计保持领先证明。要求明确比较指标、基础情况、归纳步骤,以及为什么领先关系能推出停靠次数最少。

本课总结

  • 保持领先法比较的是两个方案的对应前缀,而不是修改某个最优解。
  • 一个有效指标必须既能完成归纳,又能直接连接最终优化目标。
  • 活动选择中,最早结束策略通过保持结束时间领先,为后续选择保留了最大空间。

下一课预告

接下来可以继续学习如何为不同贪心问题选择证明方法,并通过反例判断某个局部规则是否具备可证明的全局最优性。

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

目录与阅读设置

阅读设置

17

记录一个想法

保持领先证明

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

登录哪都通