[总结]拟阵以及其在贪心算法中的应用

拟阵是一类贪心算法正确性的来源。
考虑二元组,其中是一个集合,是集合子集的集合。当然其中只包含部分子集。
若集合,则称集合是拟阵的独立子集。且空集一定为独立子集。
拟阵满足以下性质:
(1)遗传性:若,且,则.
(2)交换性:若,且,必定存在,使得.

现在我们举例说明,表示无向图的边集,表示的子集集合使得这些子集不存在环。
现在我们试图证明是一个拟阵。

首先中的元素可看作若干颗不相交的树,树中可能只存在一个节点。
遗传性:显然在若干棵树中去掉任意条边,依然不存在环。
交换性:设.设原无向图的点集为,那么中实际上是颗树,因为一开始每一个节点为一棵树,此后每添加一条不形成环的边,将减少一条边。同理中是棵树。由于事实上是将个点划分为数目比较少的集合,因此中必然存在一个集合存在属于中至少两个集合的点。那么在这个集合也就是这棵树中至少存在一条边,使得不在中的同一个集合中。而显然,但将加入中后不存在回路。从而我们成功证明了交换性。
综上所述,是一个拟阵。

对于集合,若,则称的一个扩张。
若不存在,使得的一个扩张,则称集合是拟阵的一个最大独立子集。
我们证明如下的定理,一个拟阵的所有最大独立子集的大小均相等。
利用反证法,若集合是拟阵的最大独立子集且,不妨设,那么由交换性,必定存在,使得,与集合的最大独立子集矛盾。因此证明结束。
不过只有这些是不够的。
定义权函数为集合中的元素实数的映射。
拓展定义权函数.
很多情况下,我们要处理的是求出拟阵的一个最大独立子集,使得最大。

我们给定一个算法Greedy(S,I),其返回我们要求的最优的最大独立子集。

1---- \保证S中元素按照函数递减序排序
2----
3----
4--------
5------------
6--------
7----
8----
那么我们如何判断这个算法的正确性呢?

引理1:若元素为集合最大且的元素,则若中存在这样的元素,则存在一个最优的最大独立子集,使得.
:设当前的一个最优的最大独立子集为,若,得证;否则有,我们接下来证明不可能存在这样的一个.
,显然.若,则显然不是拟阵的最优最大独立子集;否则.此时我们由交换性,依次向中添加中的任意个元素,不妨设没有添加到中.于是此时,也是拟阵的最大独立子集。中只有不同,则由(由的最优性),显然.与集合是拟阵的最优最大独立子集矛盾。
综上所述,引理1正确。

那么我们按照值从大到小维护最优最大独立子集
由于必然存在一个最优的最大独立子集包含当前权值最大的元素,我们选中当前最优的元素加入集合,随后我们对拟阵进行收缩操作。即排除掉集合与子集中的元素及满足的元素,我们容易证明子问题的最大独立子集即为原问题的最优最大独立子集。

下面我们利用拟阵证明Kruskal算法的正确性。
之前已经证明,是一个拟阵,其中表示无向图的边集,表示的子集集合使得这些子集不存在环。
我们定义一条边的边权越小,这条边的权函数越大。
于是显然我们要求的就是原拟阵的最优最大独立子集。
我们按照权函数从大到小(边权从小到大)加入每条边,并用并查集维护独立性,直到边数为成为最大独立子集。

comments powered by Disqus