有些贪心证明依赖可行集的结构,而非区间或图的特定图像。拟阵刻画了其中一种结构。我们会证明最大权定理,并看清楚目标改变时为什么负权需要小心处理。
独立性与增广
定义 6.1.1
(拟阵、独立集与基)
有限拟阵由有限地集 及非空集合族 构成,满足两项条件。
- 遗传性:若 且 ,则 。
- 增广性:若 且 ,则存在 使 。
的成员称为独立集;基是包含关系下极大的独立集。由非空及遗传性,空集独立。
这些是关于包含关系的结论,与权重无关。
引理 6.1.2
(基的大小相同,独立集可扩展为基)
在有限拟阵中,任何两个基含有相同数目的元素,而且每个独立集都包含于某个基之中。
证明
(增广性对抗极大性)
设 为基且 。由增广性,存在 使 独立,这与 的极大性矛盾。因此 ,由对称性得两者大小相等。
设 为独立集。若 不是极大的,就存在独立的真超集,用它取代 。每次取代都使大小增加,而大小不超过 ,所以经有限步后 成为极大,即成为包含原来集合的基。
按递减权重贪心选取
给每个元素 一个实数权重 ,并记 。按权重非递增排序所有元素,得 ,满足 ,以任何固定规则打破平手。由 开始依次扫描;恰在加入后仍独立时加入该元素。即使权重为负也要扫描。记 为前 个元素的前缀, 为从中已选出的元素。
定理 6.1.3
(贪心法返回最大权基)
对任意实数权重,扫描所得的集合 是一个基,而且对每个基 都有 。
证明
(先证极大性,再作前缀比较)
是基。 独立,因为它由空集开始,而元素只在保持独立时加入。设 。扫描到 时,当时的集合 满足 。因 ,若 独立,则由遗传性 也独立。所以不能再向 加入任何元素, 是极大的。
每个前缀都处理得最优。同一论证表明 在 中极大独立:此前被拒的 内元素,不能在 增长后变得可行。若有独立集 满足 ,增广性给出 使 独立,与极大性矛盾。所以 在 的独立子集中大小最大。
与基比较。令 为任意基,其元素按排序为 ,即 ,。由引理, 也有 个元素 (按排序),。集合 由遗传性是独立的,所以 。因此 的第 个所选元素不迟于位置 出现:。由于次序为权重不增,每个 都有 。对 求和,得 。平手、负权及 (此时两个和皆为零)都包括在内。
证明透视
各项假设在何处使用
证明在不同地方分别用到两条公理。遗传性出现两次:一次用来说明被拒元素在 增长后仍然被拒,一次用来说明 的前 个元素构成某个前缀的独立子集。增广性恰好出现一次,把“在 中极大”提升为“在 中大小最大”。等大小引理本身是增广性的推论,它使 与 的两个和含有相同数目的项。
不明显的一步是逐个前缀比较,而不是把两个集合直接比较。不等式 把关于权重的陈述变成关于独立集的计数陈述,排序次序再把“不迟于出现”换成“权重至少一样大”。论证逐项收尾: 对 都满足 ,所以两个和可以比较。
要留意的是证明从未用到权重的正负号,只用到排序次序,这就是负权对基没有影响的原因。真正使论证失效的是公理不成立,下面的遗传性例子就是如此。
因此,对任意实数权重,贪心法返回最大权基;最优解未必唯一。直接实现的排序需要 次比较,另有 次独立性测试;每次测试成本取决于拟阵的表示。
快速检查
(贪心基定理可否使用负权?)
留意证明用到权重的哪一种性质。
解答 · 答案
可以。它仍在所有基中最大化,因为证明比较的是等长的已排序权重表,只用到权重的次序,没有用到正负号。
例题
例题 6.1.4
(分割拟阵)
假设 有两个红元素 ,权重为 ,以及两个蓝元素 ,权重为 。集合独立当且仅当红、蓝各至多一个。遗传性显然成立。对增广性,若 , 必用到 没用的某种颜色; 中该颜色的元素可增广 。贪心法依次扫描 ,选出 ,总权重 ;余下元素会重复颜色。这是最大权基,在此例中也是最大权独立集。
例题 6.1.5
(平手与负权)
令 ,所有至多含两个元素的集合都独立。遗传性明显;若 ,任取 ,大小仍至多为 。取 、,并以 先于 打破平手。贪心法接受 ,再接受 ( 有两个元素),然后拒绝 。输出 的权重为 。
对照所有基,即三个二元素集合:,,。最大值为 ,出现两次。若以相反方式打破平手,则返回 ,是另一个权重相同的集合。
例题 6.1.6
(环元素永不被选取)
令 ,独立集只有 和 ;元素 是环,因为 不独立。遗传性成立;增广性成立,因为唯一满足 的组合是 、,而 可增广。设 、。贪心法先扫描 ,因 不独立而拒绝;然后接受 。输出 的权重为 ,它是唯一的基,所以即使存在更重的元素它仍是最优。若 也是环,唯一的基就是 ,此时 ,权重为 。
反例模式
基未必是最佳独立集
取单元素地集 , 与 均独立,且 。唯一的基是 ,故贪心法返回权重 ;但在所有独立集中,空集权重为 。若权重全非负,每个独立集均可扩展为基而不减少权重;此时最大权基也是最大权独立集。权重可正可负时,两个目标不同。
常见错误
常见错误
(略过负权元素)
权重变为负数后就停止扫描,是常见的想法。对基的问题这是错的。在 、 的例子中,若在 之前停止,返回 :它独立但不是基,因为仍可加入 。定理针对的是基,所以每个元素都必须扫描。在所有独立集中求最大权是另一个问题。
常见错误
(以为最优解唯一)
定理给出的是最优权重,不是唯一的最优集合。在上面的例子中, 与 的权重都是 ,输出取决于打破平手的规则。任何规则都可行,但返回的集合并不唯一。
仅有遗传性并不足够
遗传性可以在局部检查,于是人们可能期望贪心法对每个具有遗传性的系统都最优。证明所需要的正是增广性;缺少它,结论不成立。
反例模式
具遗传性但不是拟阵的系统
令 ,独立集为 的所有子集,以及 的所有子集。此系统有遗传性但不是拟阵: 与 违反增广性。若 、,递减贪心法选 后不能选余下元素,总权重为 ; 的权重为 。局部可行性测试本身不是全局最优证明。
习题
快速检查
(在分割例中,若蓝色权重 改为 ,结果如何?)
先把四个元素重新排序。
解答 · 答案
排序变为 。贪心法选该蓝元素与 ,总权重为 ; 与 会重复颜色。
快速检查
(为什么前缀中被拒的元素不能在以后变得可行?)
对较早的已选集使用遗传性。
解答 · 答案
若它和较大的已选集可行,遗传性就使它和此前的子集可行,但当时它正是在那个子集上被拒的。
快速检查
(单元素负权例中的最大权独立集是什么?)
比较 与 。
解答 · 答案
,权重为 ,因为 的权重为 。