贪心选择模型
选择型贪心的集合模型:按代价非减序加入可行元素;安全选择与交换论证给出正确性条件,拟阵是充分条件。标签 算法 / 贪心 / 交换论证 / 拟阵
模型
考虑有限集 。记 为可行集族,满足 ,且 、 时 。
给定元素代价 ,加入 的动作代价 。目标是求最小代价的极大可行集。
称 为极大可行集,若不存在 使 。这里的极大按包含关系,不要求元素个数最多。
对 ,记 。最优解是代价最小的极大可行集:
若 是拟阵,极大可行集就是基,最优解也称为最小权基。
按 非减序排列 ,记为 。从 开始,令
则 为所求。
正确性
定义(安全步):若 且存在最优解包含 ,称这一步安全。
引理(安全步归纳):若每次加入可行元素时都安全,则贪心输出 最优。
定理(拟阵贪心):若 是 拟阵 的独立集族,则按 非减序贪心输出最小权基。
证明:设当前集合为 , 是包含 的最优基,当前处理的元素为 ,且 是独立集。若 ,这一步已经安全。否则由 拟阵基定理,存在 ,使
仍是基。若 在 之前被处理,由于 ,它当时没有被选中;但当时已选集合是 的子集,且与 一起包含于 ,按子集封闭性仍可行,矛盾。因此 尚未处理,按 非减序有 。于是
所以 仍是最优基,且包含 ,这一步安全。由引理,贪心输出最小权基。