可用于解决一些最大权重独立子集的问题.
拟阵的定义
一个有限 拟阵 是满足以下条件的二元组 $M=(S,I)$ :
- $S$ 是有限集.
- $I$ 是由 $S$ 的一些子集组成的有限非空集合(非空族) ,这些子集称为 $S$ 的 独立子集 .
- $I$ 有 遗传性 ,即,若 $B\in I,A\subset B$ ,则 $A\in I$ .又因为 $I$ 非空,所以一定有 $\emptyset \in I$ .
- $M$ 有 交换性 ,即,若 $A,B\in I,|B|>|A|$ ,则 $\exists x\in B-A$ ,使得 $A\cup \lbrace x \rbrace \in I$ .
举个例子, $M=(S,I)$ 是一个拟阵,其中 $S=\lbrace 1,2,3 \rbrace ,I=\lbrace A\subset S:|A|\le 2 \rbrace$ .
容易验证 $M$ 满足以上的 $4$ 个条件.
拓展
有拟阵 $M=(S,I)$ ,若 $A\in I,x\not \in A,A\cup { x } \in I$ ,则称 $x$ 是独立子集 $A$ 的一个 拓展 .
最大独立子集
若一个独立子集 $A$ 不存在拓展,则称它为 最大独立子集 .
由这个定义与拟阵的交换性质可以得出一条重要性质:拟阵中所有 最大独立子集 都具有相同的大小.
线性无关与拟阵
设 $S$ 是一个行向量组, $I$ 是由所有 $S$ 的线性无关子集组成的集合,有定理:
二元组 $M=(S,I)$ 是一个拟阵.
证明该定理只需要证明 $M=(S,I)$ 满足拟阵的 $4$ 个条件.前 $2$ 个条件显然满足,只需证遗传性和交换性.
遗传性的证明
一个线性无关组的子集,显然也线性无关.即,若 $A\in I,B\subset I$ ,则 $B\in I$ ,满足遗传性.
交换性的证明
令 $X,Y\in I,|X|>|Y|$ .
考虑反证法,假设 $\forall x\in X-Y$ ,都有 $Y\cup {x} \not \in I$ 成立.
则说明将任意一个在 $X$ 集合中,而不在 $Y$ 集合中的向量 $x$ 添加到 $Y$ 集合中,都会使得 $Y$ 变为线性相关.
说明任意一个这样的 $x$ 都可以被 $Y$ 中向量线性组合表示.
而 $X$ 中其它向量也被 $Y$ 包含,也可以被 $Y$ 中向量线性组合表示.
于是 $X$ 中的所有向量都可以被 $Y$ 中向量线性组合表示.但 $X$ 线性无关,不可能被更小的集合完全表示,矛盾.
交换性得证.
加权拟阵
若一个拟阵 $M=(S,I)$ 关联了一个权重函数 $w$ ,它为 $S$ 中的每一个元素 $x$ 赋予了一个 严格大于0 的权重 $w(x)$.
则称拟阵 $M$ 是加权的,即 加权拟阵 .
$S$ 的子集 $A$ 的权值就是
$$
w(A)=\sum_{x\in A}w(x)
$$
最大权重独立子集
定义
在加权拟阵 $M=(S,I)$ 中,权值最大的 独立子集 .
即所有 $A\in I$ 中, $w(A)$ 最大的 $A$ .
贪心求解
- 将 $S$ 中所有元素按照 $w(x)$ 降序排列.
- 初始有一个集合 $A=\emptyset$ ,按照第 $1$ 步排好的顺序依次遍历 $S$ 中的每个元素 $x$ ,若 $A\cup {x}\in I$ ,则令 $A=A\cup {x}$ .
- 遍历结束后,此时的 $A$ 就是要求的最大权重独立子集的一个解.
贪心正确性证明
若 $I= { \emptyset }$ ,正确性显然,考虑 $I\not= { \emptyset }$ 的情况.
只需要考虑加权拟阵 $M=(S,I)$ 的 $3$ 条优美性质.
贪心选择性
若 $S$ 中的元素已按 $w(x)$ 降序排列,令 $x$ 为 $S$ 中第一个 ${x}\in I$ 的元素.
那么存在一个最大权重独立子集 $A$ ,使得 $x\in A$ .
元素只考虑一次
如果一个元素 $x$ 被遍历到时, $A\cup {x}\not \in I$ ,那么之后 $A$ 增大时,也总是有 $A\cup {x}\not \in I$ .
反证,由拟阵的遗传性即可得出矛盾.
最优子结构性质
若 $x$ 是求解过程中第一个被选出的元素,那么选出剩下的元素就归结为一个子问题.
即求解加权拟阵 $M’=(S’,I’)$ 的最大权重独立子集,其中,
$$
S’={y\in S:{x,y}\in I}\
I’={B\subset S-{x}:B\cup {x}\in I}
$$
应用
根据线性无关与拟阵的关系,一个常见的应用是求解向量组的 最大权值线性无关组 .
直接套用贪心求解的过程即可.
对于其它的问题,如果能构造出对应的拟阵,也可以套用上述贪心求解的过程.