动机
贪心算法并不是仅仅因为每一步的选择在局部看起来有吸引力就能成功。它们需要一个结构性的理由,说明为什么较早的选择可以被纳入某个最优解。拟阵刻画了这样一种结构:独立集对取子集封闭,并且较小的独立集可以利用较大独立集中的某个元素进行扩充。这些性质支撑了一类相当广泛的加权贪心算法的交换证明。
下面的结果求的是最大权基,即极大独立集。如果权可以为负,那么这与在任意大小的独立集中求最大权独立集是不同的目标。这一区别是定理本身的一部分,而不是实现上的细节。
定义
定义 2.8.1
(拟阵、独立集与基)
有限拟阵是一个二元组 ,其中 是有限集, 非空,并且满足:
- 遗传性质:若 且 ,则 。
- 扩充性质:若 且 ,则存在 使得 。
基是关于包含关系极大的独立集。反复扩充可知每个独立集都可以扩展为一个基,并且任意两个基的基数相同:否则可以用较大者去扩充较小者。给每个元素赋予一个实数权 。
定义 2.8.2
(按权非增顺序的贪心扫描)
贪心算法按权非增的顺序排列元素,权相同时按任意固定的顺序处理。它依次扫描这个顺序,当且仅当所选集合在加入某元素后仍为独立集时才加入该元素。即使某些权为负,它也会扫描整个基础集。
定理
引理 2.8.3
(利用基进行扩展)
若 是一个基, 是独立集,且 使 为独立集,则存在 ,使得 是一个基。
定理 2.8.4
(加权拟阵贪心定理)
对于任意有限拟阵和任意实数权函数,贪心算法返回一个最大权基。
证明思路与证明
证明
(以扩充性质把独立集扩展为基)
为证明扩展引理,从 出发。只要它的大小小于 ,扩充性质就会提供 中的一个元素,可在保持独立性的前提下加入。当大小达到 时,所得集合包含 、 的全部元素,以及 中除某一个元素 之外的所有元素。它是一个基,并且具有所述的形式。
证明
(最优基包含贪心的各项选择)
对于贪心定理,最终选出的集合是极大的:某个元素在被扫描时若被拒绝,则在之后选入更多元素也不可能变得可加入,因为独立集的子集必须是独立的。因此结果是一个基。我们维护一个包含迄今贪心所作选择的最优基 。起初任何最优基都可以。假设贪心下一步把 加入先前已选集合 。若 ,则保留 。否则,由引理得到 ,使得 是一个基。
元素 不可能在 之前被扫描:在扫描 的时刻,已选集合是 的子集,而由于 ,加入 后仍会保持独立。那么贪心会选中它,这与 矛盾。因此在固定的非增顺序中 排在 之后,从而 。交换后的基不比最优基轻,因此同样是最优的;它包含新的贪心集合。由归纳法可知,存在一个包含最终贪心基的最优基,故二者相等。
证明透视
被拒绝元素的论证
交换只依赖一个事实: 是独立集,从而经由引理得到某个可移除的元素 ,这正是扩充性质被使用的地方。扫描顺序随后给出权的比较。遗传性质有两个作用:使拒绝成为永久的,并说明若 在 之前被扫描,那时已选集合包含于 , 本会被接受。论证按贪心所作选择的个数归纳而告完结:始终保持一个包含迄今所有选择的最优基,于是最终的贪心基等于某个最优基。权相同并无影响,因为只用到 。若没有扩充性质,引理便不成立,后面“贪心失效的遗传族”一节的例子显示此时贪心会返回非最优的集合。
例题详解
例题 2.8.5
(基数约束)
设独立集为 的所有大小至多为二的子集,权分别为 。贪心选取 ,并因容量已满而拒绝 。所得的基具有最大权七。
例题 2.8.6
(图拟阵)
对于无向图,令独立边集为森林。贪心按边权递减的顺序,在不产生圈时加入边。在连通图上,其输出是最大权生成树,即 Kruskal 最小生成树算法的最大权对应版本。
例题 2.8.7
(权相同的情形)
若秩为二的拟阵中所有元素的权相等,则不同的固定平局顺序可能得到不同的基。每个基都有两个元素,因此总权相同。该定理允许任意固定的平局顺序。
常见错误
常见错误
(最大权基不等于最优的任意独立集)
在只有一个元素、秩为一的拟阵中,若权为 ,则唯一的基是权为 的单元素集,而空独立集的权为零。扫描所有元素解决的是最大权基问题,而不是这个不加限制的独立集问题。
常见错误
(仅有遗传封闭性并不充分)
仅有遗传封闭性不足以推出该定理。扩充性质被用来把贪心选择扩展为基,并使所有基的大小相同。对于任意的可行集族,证明不能悄悄地假设这一性质。
为什么交换引理由扩充性质推出
设 是大小为 的基,包含当前独立集 ,并设 是独立集且 。只要当前集合的元素少于 个,扩充公理就可应用于当前集合与独立集 。它会提供 中一个尚未出现的、可以加入的元素。重复这一过程,直到新的独立集大小为 。
最终的集合包含 、新元素 ,以及 中恰好 个元素。由于 有 个元素,恰有一个被遗漏。把该元素记为 ,便得到 。它是独立的,且大小为共同的基大小 ,所以是一个基。这一证明反复使用扩充性质;“交换”这个名称是一个结论,而不是未经解释就假设的额外公理。
贪心证明所维护的是包含迄今所作选择的最优基,而不一定始终是原来的那个最优基。需要交换时,见证用的最优基可能会改变。新的基不比原来的轻,而它的权又不可能超过原最优基的权,所以其权等于最优值。这就是算法在作出一系列局部选择的同时,如何在每一步都保有全局最优性证明的原因。
贪心失效的遗传族
反例模式
有遗传性而无扩充性
断言:对任何遗传族及任意实数权,降序贪心都返回最大权基。设 ,独立集为 的所有子集与 的所有子集。这个集族具有遗传性质,但对 与 扩充性质不成立: 和 都不能加入 。取权 、,按降序的贪心选取 ,且无法再加入其他任一元素,得到权三。而独立集 的权为四。该集族不是拟阵,所以定理不适用。修正之道是要求扩充性质:这个性质正好排除了此集族,而有了它,贪心就是最优的。
这个例子中还有大小不同的极大独立集,分别为一和二。在拟阵中这不可能发生:若某个极大独立集比另一个独立集小,则扩充性质会与它的极大性矛盾。基的大小相等是公理的推论,而不是额外隐藏的假设。
为什么森林构成拟阵
对于有限无向图,取 为其边集,并称不含圈的边集为独立集。从森林中删除边不会产生圈,所以遗传性质成立。对于扩充性质,设森林 满足 。若 中没有任何一条边连接森林 的不同连通分支,则 的每条边都落在这些分支之一的内部。在有 个顶点的分支中,无圈图至多有 条边。对各分支求和将得到 ,矛盾。因此 中有某条边连接 的不同分支,并且可以加入而不产生圈。
在连通图中,每个极大森林都是生成树。因此,把最大权基定理应用于图拟阵,便证明了权递减版本的 Kruskal 算法。将顺序反转,或等价地把权取负,就得到最小生成树版本。该定理涵盖权相同的情形,因为证明的每一步都不需要严格的权不等式。
基与任意独立集
当所有权均非负时,最大权独立集可以在不减少权的前提下扩展为基。因此最大权基在所有独立集中也是最优的。当权可以为负时,扩展可能使权变差,正如单元素例子所示。扫描全部元素的算法刻意返回一个基,必要时会为了达到基而包含负权元素。
若要在任意实数权下使独立集的权最大,则在考虑时舍弃所有负权元素,并对正权元素构成的限制运行同样的贪心规则。每个独立集都可以舍去其负权元素而不减少其权;权为零的元素也可以省略而不改变其权。正权元素上的限制仍是拟阵,并且该限制中的最优正独立集可以扩展为该限制的一个基,同时权增加或保持不变。因此贪心定理证明了所得到的正权元素集对于不加限制的独立集目标是最优的。这是一个相关的推论,并不是扫描全部元素的基算法的目标。
概念视角结构
贪心所得的基是每个权重阈值的基
对实数 ,令 。贪心在扫描任何其他元素之前先扫描完 ,所以输出与 的交集是 的一个极大独立子集,大小为 。反过来,基 的权重最大,当且仅当对每个 都有 :它的权重是 加上各个 乘以相邻权重之间非负的差距后的总和,而没有基在任何一层能超过秩。
复杂度与谕示的含义
对 个元素排序需要 次比较。之后,通用算法对每个元素进行一次独立性查询。其实际运行时间取决于如何检验独立性以及如何表示已选集合。把一次独立性查询视为常数时间的谕示,给出的是谕示调用次数,而不会自动成为具体实现的时间上界。
对于图拟阵,可以用不相交集合结构来检验一条边是否连接当前不同的分支;其精确代价取决于所选择的合并与查找操作。对于基数拟阵,独立性通过当前集合的大小来检验。同一个抽象证明适用于二者,而它们的实现与复杂度分析各不相同。
要检验一个给定的输出,需验证其独立性与极大性,并将其权与另行论证的上界比较。仅有独立性并不能证明权最大。贪心的交换证明为算法自身的输出提供最优性保证;大小正确的任意独立集不一定是最大权的。
追踪一次图上的交换
例题 2.8.8
(追踪四顶点图上的交换)
考虑四个顶点 ,边 的权分别为 。降序贪心首先接受 和 。它拒绝 ,因为这三条边构成圈;接受 ,然后拒绝 。其生成树的权为 。
为了看出交换证明如何证实这一答案,改为从生成树 出发,其权为十六。贪心的第一条边 不在 中。加入它会产生顶点 上的三角形;删除 便得到包含 的、权为十八的树。第二条贪心边 已经在其中。最后,向这棵新树加入 ;产生的圈包含 ,其权较小,因此可以删除。最终的树权为十九。这里的交换见证是明确的边,而一般定理则在不假设图的情形下由扩充性质得到见证。
被拒绝的边可以比之后被接受的边权更大: 的权为六,而 的权为四。这并不矛盾。是否接受一条边取决于之前选出的整个森林,而不只取决于权。具体而言,在 和 之后加入 会违反独立性,而 连接了两个分支。
贪心不再最优,但两个拟阵的问题仍然可以有效求解。
通往推广的路径
若集合须同时在两个拟阵中独立呢?
贪心不再最优,但两个拟阵的问题仍然可以有效求解。
二部图匹配就是两个划分拟阵的公共独立集:每个左顶点至多一条边,每个右顶点至多一条边。设边 权重为 ,边 、 权重为 :贪心取 后即停在 ,而另外两条边合起来是 。对两个拟阵,求最大公共独立集已有多项式时间算法;对三个拟阵,问题则是 NP 困难的。
总结
扩充性质使得独立的贪心选择可以替换最优基中的一个元素。扫描顺序保证替换后不会更轻。重复这样的交换,便对任意实数权给出最大权基。
练习
快速检查
(在四个元素、权为 的秩为二的基数拟阵中,列出两种可能的贪心输出及它们共同的权。)
按扫描顺序处理元素,并在每一步后检查秩。
解答 · 答案
贪心必须取权为六的元素。权同为四的两个元素中任意一个都可以接着被取,由此得到两个不同的基,权均为 。秩已满之后,负权元素不能被包含。
快速检查
(在四顶点图拟阵的例子中,从树 出发。加入 ,并指出可以删除哪条边,使得到的树同时包含 和 。比较新旧权。)
在树中加入一条边,恰好产生一个圈。
解答 · 答案
加入 产生圈 。删除 得到 。原来的权为 ,新的权为 。未改变的边 仍然连接着顶点 。
快速检查
(某个遗传族的独立集恰为 的所有子集与 的所有子集。给出一个扩充失败的例子,并选取正权使得降序贪心不是最优的。)
寻找一个独立集,使较大独立集中的任何元素都不能加入其中。
解答 · 答案
取 与 ; 中的两个元素都不能加入 。令 的权为 , 的权各为 。贪心得到 ,但 的权为 。
快速检查
(在元素权为 的秩为二的基数拟阵中,分别给出最大权基与最大权独立集。解释两个目标为何不同。)
基必须是极大的;独立集则可以更早停止。
解答 · 答案
最重的基包含权 与 ,总权为 。最优独立集是权为 的单元素集。基必须是极大的,因此有两个元素,而任意独立集可以更早停止。