贪心法矩阵胚理论介绍

pk_001

贪心法矩阵胚理论介绍

矩阵胚的定义是：
M={S,I}
其中S为有限集，I为S的一个子集族，满足下面条件：
1.{}属于I
2.如果集合X属于I，则X的所有子集都属于I。
3.如果集合W，V都属于I，且|V|>|W|,则V中存在一个不在W中的集合z，使W并{z}属于I。

I中的集合叫做矩阵胚的独立子集。上面三个定义保证了独立子集具有如下属性：
1.独立子集至少有一个（空集）
2.独立子集是“遗传”的。
3.只要一个独立子集不是最大（元素最多）的，我们总可以把它变得更大。

定义：把S中的元素加非负的权，我们可以得到一个加权矩阵胚。

定理1：贪心的扩展加权矩阵胚可以得到最优子集。

证明：设贪心法得到的独立子集是B，最优独立子集为T(如果有多个T，选择使B交T最大的那个)，那么：
i)如果B=T,则成功
ii)否则，设x为不在T中的第一个被贪心法选择的元素，则T并x为非独立集（否则与T最大矛盾）。
设C为T并x的子集中的最小的非独立集，则x属于C(否则C就为T的子集，与属性2矛盾)。这样，我们取C
中任意不属于B的元素y，又条件3，C-{y}为独立集。

下面，我们从C-{y}出发构造一个最优独立子集T_1，使B交T_1比B交T更大。

对于C-{y}，我们把T中不属于其中的元素依次加到里面（根据属性3），则最后我们得到一个T_1,
其中T_1=T-{y}+{x}。

下面，我们来说明w(x)=w(y)。
1.T是最优的，因此w(T_1)<=w(T),即w(x)<=w(y)
2.假设贪心算法选择x之前选择过的元素集合为X,那么：X为T的子集，且X并{y}也是T的子集。那么，在
选择x的时候，y也是可以选的。但是贪心算法选择的是x,必有w(x)>=w(y),故w(x)=w(y)

这样，T_1也是最优独立子集，但是T_1比T多一个在B中的元素x,与T的选择矛盾。故贪心法能够选择最优
独立子集。


定理2：如果F关于子集运算是封闭的，而对于任何权函数(F,w),贪心法都适用，则F为某个矩阵胚的
独立子集族。

这里略去定理的证明，想知道证明的朋友可以来信问我。

两个常用的独立子集的例子是：
1.有限个n维向量集合中个线性无关的向量 。
2.某个图中没有圈的边集。

根据定理一，我们如果可以把问题归结成在加权矩阵胚中求最优独立子集的问题（需要验证问题的结构满足矩阵胚
的三个定义），我们就可以采用贪心法。也就是每次选取权值最优的元素加到独立子集中，最后得到的最大独立子
集必然是最优的。