反悔贪心

先维护一个可行解,用堆、链表或残余结构保存反悔项;出现更优交换时替换旧选择,正确性由交换论证保证。

标签 算法 / 贪心 / 反悔贪心 / 堆 / 交换论证

问题形式

设 𝐸 有限,ℱ︀⊆2𝐸 对子集封闭,𝑐:𝐸→ℝ。按 𝐸 的全序 𝜋=(𝑒1,…,𝑒𝑛) 处理,维护 𝑆∈ℱ︀。加入 𝑒𝑘 后若 𝑆∪{𝑒𝑘}∉ℱ︀,允许删除或替换 𝑆 中若干元素;目标是最小化

𝐶(𝑆)=∑𝑒∈𝑆𝑐(𝑒).

核心思想

对每个 𝑠∈𝑆 记录反悔项 𝜌(𝑠):移除 𝑠 可节省的代价;简单情形 𝜌(𝑠)=𝑐(𝑠)。处理 𝑒𝑘 时,比较 𝑐(𝑒𝑘) 与最大的 𝜌(𝑠);若

𝑆′=(𝑆∖{𝑠})∪{𝑒𝑘}

满足 𝑆′∈ℱ︀ 且 𝐶(𝑆′)<𝐶(𝑆),就执行替换。堆、链表和残余网络维护这些交换选项。

堆实现通常为 𝑂(𝑛log𝑛),空间 𝑂(𝑛);具体复杂度取决于交换结构。

正确性

反悔贪心仍要求安全选择:每次替换得到的 𝑆′ 必须包含于某个最优解。证明使用交换论证;拟阵是 ℱ︀ 的一类充分结构,不是必要条件。

单机最小逾期任务是反悔贪心的标准实例,见 最小逾期任务。

易错点

  • 堆中存的常是变换后的反悔项,不是 𝑐(𝑠) 本身。
  • 一次替换可能不足以恢复可行,需要多步增广。
  • 只按 𝑐(𝑒𝑘) 贪心可能错,必须比较反悔项。
  • 相同键、不可行状态和终止条件需要单独处理。
源码位置