拟阵笔记
拟阵是很多贪心算法的基础,也可以帮助我们验证自己的贪心算法的正确性,接下来是我从抄《算法导论》中整理出来的一些关于拟阵的性质:
定义
吐槽:虽然说拟阵叫拟阵,但是这个“阵”和矩阵的阵几乎一点关系都没有(名字的由来纯粹是历史遗留问题),拟阵和矩阵的关系就像JavaScript和Java,雷锋和雷峰塔一样……
拟阵:拟阵是一个二元组,其中为一个有限集,为的一个族(即子集的集合)并满足如下性质:
- 遗传性:若且,则。
- 交换性:若且,那么存在元素,使得。(又是一个误导性的名字……)
中的集合成为的独立子集。
图拟阵:对于一个图,我们定义它的图拟阵为,当中为边集,而的子集的当且仅当中无环(森林)。图拟阵与最小生成树有关(这也解释了为什么最小生成树的算法都是贪心)。由于森林的子图还是森林,因此该拟阵的遗传性显然。而该拟阵的交换性也在算法导论中有详细的证明,简单讲起来就是对于森林,,我们知道中有棵树,中有棵树比少,因此一定存在一条边使得在中分别属于两棵树,而在中却在一棵树上,显然,证毕。
拓展:对于集合,若存在元素使得,则称是的一个拓展。
最大独立子集:不存在拓展的独立子集。
定理:所有的最大独立子集等大小。
证明:反证, 假设存在最大独立子集使得,由交换性,必然存在是的一个拓展,证毕。
加权拟阵:若存在一个权函数为所有的元素定义了严格正的权值,则称为加权拟阵,定义独立子集的权值为:
和贪心的关系
很多贪心问题可以转化为在拟阵上求最大权独立子集,或者称为拟阵的最优子集。
例:最小生成树算法当中我们可以对于边定义权重,其中为边的长度,为一个极大的数。在图拟阵上最大化独立子集权重必然等价于在图上最小化生成树边权(因为生成树的边数总是固定的)。
求解最优子集的算法:将的所有元素按照从大到小排序,初始化,然后依次从大到小考虑每个元素,并尽可能地用去拓展,最后得到的集合必定是最优子集。
这个算法的贪心本质暴露无遗,接下来我们证明这个算法的正确性:
引理1(贪心选择):若将的元素从大到小排序,令为排序后第一个使得的元素,那么必然存在一个包含的最优子集。
证明:如果不存在,则最优子集为空,显然。
否则,假设我们有一个不含的最优子集,显然由遗传性,对于都有,又因为我们选择的方式显然由。我们初始化,利用和交换性不断拓展直至,此时必定存在另一元素,使得,又因为,那么一定不会比差,得证。
引理2:若元素是的一个拓展,那么,换而言之,是的拓展。
证明:由定义,,由遗传性显然。
推论(逆否命题):若不是的拓展,那它也一定不是其他非空独立子集的拓展。
引理3(最优子结构):在如上算法中选择完之后,在中寻找最优子集等价于在中寻找最优子集,其中:
即我们可以忽略继续我们的算法。证明:如果我们在当中选出了最优子集,则显然是的独立子集,并且由的选择方式可知也是最优子集,证毕。
贪心正确性的证明:由引理2的推论,我们知道贪心算法没能一开始用来拓展的一定在后面也没有用。由引理3,选择完之后我们把问题缩小,还可以进一步贪心,此时贪心实质上是在上寻找最优子集。证毕。
从以上讨论我们可以看出,对于一类问题,如果我们可以以某种方式把它规约为在拟阵上求取最优子集,那你一定可以使用贪心解决,这给很多贪心算法(例如Kruskal)提供了理论支持。