贪心选择模型

选择型贪心的集合模型:按代价非减序加入可行元素;安全选择与交换论证给出正确性条件,拟阵是充分条件。

标签 算法 / 贪心 / 交换论证 / 拟阵

模型

考虑有限集 𝐸。记 ℱ︀⊆2𝐸 为可行集族,满足 ∅∈ℱ︀,且 𝐴∈ℱ︀、𝐵⊆𝐴 时 𝐵∈ℱ︀。

给定元素代价 𝑐:𝐸→ℝ,加入 𝑒 的动作代价 𝑐(𝑒)。目标是求最小代价的极大可行集。

称 𝐵∈ℱ︀ 为极大可行集,若不存在 𝑒∈𝐸∖𝐵 使 𝐵∪{𝑒}∈ℱ︀。这里的极大按包含关系,不要求元素个数最多。

对 𝑆∈ℱ︀,记 𝐶(𝑆)=∑𝑒∈𝑆𝑐(𝑒)。最优解是代价最小的极大可行集:

𝐶(𝑂)=min{𝐶(𝐵):𝐵∈ℱ︀,𝐵极大}.

若 ℱ︀ 是拟阵,极大可行集就是基,最优解也称为最小权基。

按 𝑐 非减序排列 𝐸,记为 𝜋=(𝑒1,…,𝑒𝑛)。从 𝑆0=∅ 开始,令

𝑆𝑘={𝑆𝑘−1∪{𝑒𝑘}𝑆𝑘−1∪{𝑒𝑘}∈ℱ︀𝑆𝑘−1否则

则 𝑆𝑛 为所求。

正确性

定义(安全步):若 𝑆∪{𝑒}∈ℱ︀ 且存在最优解包含 𝑆∪{𝑒},称这一步安全。

引理(安全步归纳):若每次加入可行元素时都安全,则贪心输出 𝑆𝑛 最优。

定理(拟阵贪心):若 ℱ︀ 是 拟阵 的独立集族,则按 𝑐 非减序贪心输出最小权基。

证明:设当前集合为 𝑆,𝑂 是包含 𝑆 的最优基,当前处理的元素为 𝑒,且 𝑆∪{𝑒} 是独立集。若 𝑒∈𝑂,这一步已经安全。否则由 拟阵基定理,存在 𝑒′∈𝑂∖𝑆,使

𝑂′=(𝑂∖{𝑒′})∪{𝑒}

仍是基。若 𝑒′ 在 𝑒 之前被处理,由于 𝑒′∉𝑆,它当时没有被选中;但当时已选集合是 𝑆 的子集,且与 𝑒′ 一起包含于 𝑂,按子集封闭性仍可行,矛盾。因此 𝑒′ 尚未处理,按 𝑐 非减序有 𝑐(𝑒)≤𝑐(𝑒′)。于是

𝐶(𝑂′)=𝐶(𝑂)−𝑐(𝑒′)+𝑐(𝑒)≤𝐶(𝑂).

所以 𝑂′ 仍是最优基,且包含 𝑆∪{𝑒},这一步安全。由引理,贪心输出最小权基。

源码位置