贪心算法与独立集系统

独立集系统基本定义

独立集系统: 一个独立集系统是指： $(E,\mathscr{F})$ ，其中$E$ 是有限基本元素集合， $\mathscr{F} \subseteq 2^E$（$E$ 的幂集的子集，即 $E$ 中任意元素的集合），且满足：
1. $ $
2. 若 $Y\in \mathscr{F}$ , $Y$ 的子集属于$\mathscr{F}$
独立集：$\mathscr{F}$ 中的元素称为独立集

理解：独立集系统是一个空间，这个空间中有一些元素 ($E$ 中的元素) 以及一个规则 $\mathscr{F}$，通过这个规则判断元素的集合是不是独立集。上面定义中 $\mathscr{F}$ 是幂集的子集，通过集合是否属于 $\mathscr{F}$ 判断它是否是一个独立集，而在应用中， $\mathscr{F}$ 的定义通常是满足某一条件的集合，因此它可以看成是某种规则。

举个例子：设 $E$ 是一个有限点集， \[\mathscr{F} = \{T\subseteq E, \ \vert T\vert\le K\}\] ，可以简单验证它符合上面定义的两个条件，因此 $(E,\mathscr{F})$ 是一个独立集系统。可以看到，这个独立集系统中包含了有限点集和规则：点集集合的模不大于 $K$ 。满足这个规则的集合是独立集。

基：对于$E$ 的子集$FE $， $T\subseteq F$ 是一个独立集，且任何一个元素 $x\in F,x\notin T$ 加进来 $T\cup\{x\}$ 就不是独立集，则称 $T$ 是 $F$ 上的极大独立集，或称 $T$ 是 $F$ 的一个基。
相关集：$2^E \backslash\mathscr{F}$ 中的元素称为相关集，即在 $E$ 中元素构成的集合中不是独立集的集合
圈：极小相关集。若删掉相关集 $T$ 中的任意一个元素就可以得到独立集，则称 $T$ 为极小相关集，也称为圈。

在上面那个例子中，基即为模等于 $K$ 的集合。相关集为任何模大于 $K$ 的集合。圈为模等于 $K+1$ 的集合。

秩(上秩): $ (F) = {Y, YF, Y}$
下秩: $ (F) = {Y, YF, Y是F上的基}$
秩商: \[\mathscr{q}(E,\mathscr{F}) = \min_{F\subseteq E} \frac{\rho(F)}{\gamma(F)}\]

要注意的是，秩和下秩都是相对于$E$ 的子集$FE $ 而言，在子集 $F$ 中，要找到模最大的独立集和模最小的极大独立集。对于秩而言，因为我们要找的是模最大的独立集，所以一定是一个极大独立集，也就是一个基。因此，秩商表示的是：找到集合 $E$ 的一个子集 $F$, 这个子集的模最小的基的模与模最大的基的模的比值最小 (也就是基的模的区间最大)，秩商表示这个比值。

优化问题

大多数的优化问题都可以放到一个独立集系统中解决。

记问题为 $(E, , C) $ 其中 $ C: R$ 表示独立集系统中每个独立集的权重，求 $(E,\mathscr{F})$ 中的一个独立集 $X$使得 $C(X)$ 最大或最小。一般而言，\[C(X) = \sum_{e\in X} C(e)\] , 即独立集的权重是其元素的权重和。

极大化问题 $(E,\mathscr{F},C)$ ：寻找权重最大的独立集(当然最后的解也是极大独立集)
极小化问题 $(E,\mathscr{F},C)$ ：寻找权重最小的极大独立集

例子

最短路问题：
$E$ 表示边集，$\mathscr{F}$ 表示一条s到t路径的子弧的集合。最短路问题是求权重最小的极大独立集。（这里极大独立集就是一条s到t的路径）

最小生成树问题：
$E$ 表示边集，$\mathscr{F} = \{T\subseteq E,T是无圈子图\}$ 。最小生成树问题是求权重最小的极大独立集。（这里极大独立集就是一棵树）

背包问题：
$E$ 表示物品集合，$\mathscr{F}$ 表示能同时装入背包的物品的集合。背包问题是求权重最大的独立集。

TSP问题：
$E$ 表示边集，$\mathscr{F}$ 表示哈密尔顿圈的子图。TSP问题是求权重最小的极大独立集。（这里极大独立集就是一个哈密尔顿圈）

最大匹配问题
$E$ 表示边集，$\mathscr{F}$ 表示任一匹配。求权重最大的独立集。

顶点覆盖问题
用对偶的思想解决：$E$ 表示点集，$\mathscr{F} = \{ T\subseteq E,E-T是一个覆盖\}$ ，求权重最大的独立集。

贪⼼算法

对于 $(E,\mathscr{F},C)$ 上极大化问题的贪心算法，有 Best in 和 Worst out 两种

Best in：

对权重进行排序： $c_1 \ge c_2\ge ... \ge c_n$

$F = $
for $ i $ = 1 to n
if $F\cup e_{i} \in \mathscr{F}$
$F := F\cup e_{i}$

Worst out:

对权重进行排序：$c_1 \le c_2\le ... \le c_n$

$F=E$
for $i$ = 1 to n
if $F{e_i} $ 含基
$F := F\backslash{e_i}$

定理

对于极大化问题 $E,\mathscr{F},C$有 \[ q(E,\mathscr{F}) \le \frac{G(E,\mathscr{F},C)}{OPT(E,\mathscr{F},C)} \le 1\]

证明：（针对 Best in 方法，Worst out (应该) 类似）

$E_j = \{e_1, e_2, ..., e_ j\}$ C: $E\rightarrow R^+ ,\quad c_1 \ge c_2\ge ...\ge c_n$
贪心算法解：$G_n,\quad G_j = G_n\cap E_j,\ j = 1,2,...,n$
最优解：$O_n,\quad O_j = O_n\cap E_j,\ j = 1,2,...,n$

\[ \begin{align} C(G_n) &= \sum^n_{j=1} (|G_j|-|G_{j-1}|)c_j \\ &= \sum^n_{j=1} |G_j|(c_j-c_{j+1})\\ &\ge \sum^n_{j=1} \rho(E_j)(c_j-c_{j+1}) \quad[G_j是E_j的⼀个极大独立集]\\ &\ge q \sum^n_{j=1} r(E_j) (c_j-c_{j+1}) \quad[ q(E,\mathscr{F}) = \min_{F\subseteq E}\frac{\rho(F)}{\gamma(F)}]\\ &\ge q \sum^n_{j=1} |O_j| (c_j-c_{j+1}) \quad[ \gamma(F) = \max\{|Y|, Y\subseteq F, Y\in \mathscr{F}\} ]\\ &= q\ C(O_n) \end{align} \]

在证下界是紧的：

由秩商的定义， \[\exists F, \frac{\rho(F)}{\gamma(F)} = q(E,\mathscr{F})\]，即 $\exists F$ , $F$ 的基 $B_1, B_2$ 满足 \[ \frac{\vert B_1\vert}{\vert B_2\vert} = q(E, \mathscr{F})\]

定义权重：$c(e) = 1, e\in F;\ c(e) = 0, e\notin F$ 。把 $B_1$ 的元素排在前面 $e_1, e_2, ..., e_{\vert B_1\vert},...$ 。使用Best in，会选择前 $\vert B_1\vert$ 个元素，而最优解可以选 $\vert B_2\vert$ 个元素。

因此贪心算法的近似比

\[ q(E,\mathscr{F}) \le \frac{G(E,\mathscr{F},C)}{OPT(E,\mathscr{F},C)} \le 1 \]

独立集系统的对偶

\[ (E,\mathscr{F}) \rightarrow (E,\mathscr{F}^*)\\ \mathscr{F}^* = \{X\subseteq E\ \vert\ \exists\mathscr{F}的一个基B，满足 X\cap B = \emptyset \} \]

性质

$(E,\mathscr{F}^*)$ 是一个独立集系统：证明满足独立集系统的定义即可
$B$ 是 \[(E,\mathscr{F})\] 的基，当且仅当， \[E\backslash B\] 是 \[(E,\mathscr{F}^*)\] 的基：
若 $A$ 是 \[(E,\mathscr{F}^*)\] 的一个基，则 \[\exists B\in \mathscr{F},A\cap B = \emptyset\]
由于 $A$ 是极大独立集， \[A = E\backslash B\]
$(E,\mathscr{F}^{**}) = (E,\mathscr{F})$

\[ \begin{align} \forall X\in \mathscr{F}^{**} &\Leftrightarrow \exists (E,\mathscr{F}^*)的一个基 B^*, X\cap B^* = \emptyset\\ &\Leftrightarrow \exists (E,\mathscr{F})的一个基 B, X\cap (E\backslash B) = \emptyset\\ &\Leftrightarrow \exists (E,\mathscr{F})的一个基 B, X\subseteq B, X\subseteq\mathscr{F} \end{align} \]

独立集系统的对偶主要用于分析极小化问题，可以证明：

\[ 1\le \frac{G(E,\mathscr{F},C)}{OPT(E,\mathscr{F},C)} \le \max_{F\neq \emptyset }\frac{\vert F\vert-\rho^*(F)}{\vert F\vert-\gamma^*(F)} \]

证明与极大化问题类似.

拟阵

拟阵是一类特殊的独立集系统: $(E,\mathscr{F})$ 满足:

(M1): \[ \emptyset \in \mathscr{F}\]
(M2): 若 $X\in \mathscr{F},\ \forall Y\subseteq X,Y\in\mathscr{F}$
(M3): $ 若X, Y,X >Y,则 eXY, Y{e} $ , 也就是说 $Y$ 可扩充
(M3’): $ 若X, Y,X = Y+1,则 eXY, Y{e} $
(M3”): $\forall F \subseteq E$, $F$ 上的任何基有相同的元素个数 (要注意这里不只是 $E$ 上的基，而是 $E$ 的任意子集上的基)
M3, M3’, M3” 是相互等价的，只要满足其中之一的独立集系统就是拟阵。

例子:

向量矩阵
\[ E = \{v_1,v_2,...,v_m\},\ \mathscr{F} = \{Z\subseteq E\vert Z 是线性无关组\} \]
一致拟阵
E 是有限集合，K 是一个给定的正整数, \[\mathscr{F} = \{X\subseteq E\vert\ \vert X\vert\le K\} \]
图拟阵
$E$ 是无向图 $G$ 中的编辑, $\mathscr{F} = \{X\subseteq E, X 构成一个森林\}$

waw 可以看到很多常见的体系都是一个拟阵，如矩阵与线性无关的概念，森林与树。又或者说，拟阵是这些体系的一个抽象，从而分析它们的共性。

拟阵与贪心算法

可以简单得到，拟阵的秩商是 1，根据前面独立集系统的分析，贪心算法的近似比为1。因此，在拟阵中使用贪心算法可以得到最优解。[ 所以最小生成树问题贪心就可以得到最优解。]

用秩商分析得到这个结论是显然的，下面用另一种方法证明拟阵上贪心算法可以得到最优解（来自算法导论）

引理1： (拟阵具有贪心选择性质) 假定 $M= ( S , I )$ 是一个加权拟阵，加权函数为 $ w$ , 且 $S$ 已按权重单调递减顺序排序．令 $x$ 是S 中第一个满足 $\{x\}$ 独立的元素（如果存在）。如果存在这样的 $x$ ，那么存在 $S$ 的一个最优子集 $A$ 包含$x$．

证明：

如果不存在这样的 $x$ ，唯一的独立子集是空集，引理显然成立。否则，令B 为任意非空最优子集．假定 $x\notin B$。
$B$ 中元素的权重都不大于 $w( x ) $: 我们观察到 $y\in B$ 意味 ${y} $是独立的，$x$ 是第一个形成独立集的元素，因此对任意 $y\in B$, 有 $w(x) w(y) $。
构造集合 $A$ . 以 $A = {x} $ 开始，集合 $A$ 是独立的。根据 (M3): 若$ X, Y$, $X >Y$, 则$ eXY$,$ Y{e} $，反复寻找 $B$ 中一个可以加入 $A$ 中的新元素, 同时保持 $A$ 的独立性，直至 $A =B$ . 此时， A 和B 的区别仅在 $A$ 包含 $x$ ，而 $B$ 包含另一个元素 $y$ . 由于 $w(x)\ge w(y)$ , $ w(A) = w(B) - w(y) +w(x) w(B)$ 。
由于集合B 是最优的，因此集合A 必然也是最优的，且包含 $x$。

引理2: $M= (S , I )$ 是一个拟阵．如果 $x$ 是 $S$ 中一个元素，且它不是 $\emptyset$ 的一个扩展．那么它也不是 $S$ 的任何独立子集 $A$ 的扩展．

证明：由独立集的定义，独立集中的任何元素 $x$ 自身形成的集合 $\{x\}$ 也是一个独立集。因此若 $\{x\}$ 不是独立集，则 $A\cup\{x\}$ 也不是独立集。

引理2表明，任何元素如果首次不能用于构造独立集，则之后也不可能被用到。因此，贪心算法跳过 $S$ 中那些不是 $\emptyset$ 的扩展的起始元素，不会导致错误结果。

引理3: （拟阵具有最优子结构性质） $M= (S , I )$ 是一个加权拟阵，$x$ 是 $S$ 中第一个被贪心算法选出的元素，则接下来寻找一个包含 $x$ 的最大权重独立子集的问题归结为寻找加权拟阵 $M’=(S’,I’) $ 的一个最大权重独立子集的问题，其中

\[ S' = \{y\in S:(x,y)\in I\}\\ I' = \{B\subseteq S-\{x\}:B\cup\{x\}\in I\}\\ \]

$M'$ 的权重函数就是 $M$ 的权重函数，但只局限于S’ 中元素．我们称 $M'$ 为 $M$ 在元素 $x$ 上的收缩 ( contraction)

证明: 若 $A$ 是 $M$ 的任意一个包含x 的最大权独立子集，则 $A' = A -\{x\}$ 是 $M'$ 的一个独立子集。同时，任何 $M'$ 的独立子集 $A$ 可生成 $M$ 的独立子集 $A = A’{x} $ . 均有 $w(A)=w(A')+w(x)$.因此 $M$ 的包含 $x$ 的最大权重独立子集必然生成 $M'$ 的最大权重独立子集．反之亦然．

定理: （拟阵上贪心算法的正确性）若 $M= ( S , I )$ 是一个加权拟阵，加权函数为 $ w$ ．那么贪心算法返回一个最优子集

证明：由引理2, 贪心算法跳过 $S$ 中那些不是 $\emptyset$ 的扩展的起始元素可永远丢弃．因为这些元素不会被用到。一旦贪心算法选出第一个元素 $x$， 引理 1 表明算法将 $x$加入 $A$ 不会导致错误结果，因为必然存在包含 $x$ 的最优子集。 引理 3 说明剩下的问题就是如何寻找拟阵 $M'$ 的最优子集， $M'$ 是 $M$ 在 $x$ 上的收缩。将 $A$ 设为 $\{ x\}$ 后．我们可以将之后的所有步骤解释为拟阵 $M' =(S',I')$上的操作,因为对所有集合 $B\in I'$ , $B$ 在 $M'$ 中独立当且仅当 $B\cup\{x\}$ 在 $M$ 中独立。因此，贪心算法随后的操作将会找到M’ 的一个最大权重独立子集。而其所有操作的总体效果就是找到 $M$ 的一个最大权重独立子集。

拟阵与独立集系统

独立集系统的交： $(E,_1), (E,_2) $ 的交为 $(E,\mathscr{F}_1\cap\mathscr{F}_2)$

任何⼀个独⽴集系统⼀定是有限个拟阵的交

证：用构造法证明

记独立集系统为 $(E,\mathscr{F})$ , 设独立集系统有 $k$ 个圈： $c_1,c_2,...,c_k$

令 \[\mathscr{F}_i = \{X\subseteq E\vert X\nsupseteq c_i\}\] , 可以证明 $(E,\mathscr{F}_i)$ 是一个独立集系统。

[ 这里很容易弄晕，解释一下。前面说过独立集系统表示了一个集合与一个规则，在这里不同的 $\mathscr{F}_i$ 表示了不同的规则，因此形成了不同的独立集系统，每个独立集系统都确定了哪些是独立集哪些不是。 $(E,\mathscr{F}_i)$ 这个独立集系统表示的是：如果一个集合不包含 $c_i$ 中的所有元素，则它是一个独立集。对于第 $i$ 个独立集系统，独立集可以包含其他圈。圈的概念是极小相关集，但这里的相关集是独立集系统 $(E,\mathscr{F})$ 中的相关集，在当前的独立集系统中，包含 ‘圈’ 的集合仍可以是独立集 ]

下证， $(E,\mathscr{F}_i)$ 是拟阵，用 M3”: $\forall F \subseteq E$, $F$ 上的任何基有相同的元素个数。对于 $\forall F \subseteq E$

$ F c_i$ ，则整个集合 $F$ 是一个独立集，因此它就是 $F$ 上的极大独立集， $F$ 上的基有相同的元素个数
$ F c_i$ ，对 $\forall e\in c_i$ , $F\backslash {e}$ 是极大独立集， $F$ 上的基有相同的元素个数

现证 \[ \mathscr{F} = \cap_{i = 1}^k \mathscr{F}_i\]

\[\mathscr{F} \subseteq \cap_{i = 1}^k \mathscr{F}_i\]:
\[\forall X\in \mathscr{F},X\] 不包含任何圈, \[X\in\mathscr {F}_i,i=1,...,k \ \Rightarrow X\in \cap_{i = 1}^k \mathscr{F}_i\]
\[ \mathscr{F} \supseteq \cap_{i = 1}^k \mathscr{F}_i \]
\[\forall X\in \mathscr{F}_i,X\]不包含圈 $c_i$ 。\[\forall X\in\cap_{i = 1}^k \mathscr{F}_i\Rightarrow X\]不包含任何圈 \[ \Rightarrow X\in \mathscr{F}\]

[ 需要指出的是，这里只是用构造法说明了任何⼀个独⽴集系统都可以表示为有限个拟阵的交，但用这种构造不一定能分解为最少的拟阵，在实际应用中不一定能得到紧的解 ]

少数的例子：

对于二部图 $G=(AB,E) $, $(E,\mathscr{F})$ 表示图的匹配的独立集系统。

\[ \mathscr{F}_1 = \{X\subseteq E, \vert\delta _X(u)\vert\le 1,\forall u\in A\}\\ \mathscr{F}_2 = \{Y\subseteq E, \vert\delta _Y(u)\vert\le 1,\forall u\in B\}\\ \]

其中 $\delta_X(u)$ 表示 $u$ 的度数，只考虑 $X$ 中的边。可以证明， $(E,\mathscr{F}_1),(E,\mathscr{F}_2)$ 是拟阵且 $\mathscr{F} = \mathscr{F}_1\cap \mathscr{F}_2$ 。

若独⽴集系统是 $k$ 个拟阵的交，则贪⼼解的近似⽐至少为 $1/k$

记独⽴集系统为 $(E，\mathscr{F})$，是 $k$ 个拟阵 $(E，\mathscr{F}_i)$ 的交。

证：即证秩商 $q(E ,\mathscr{F}) \ge 1 /k$ 。对 $\forall F\subseteq E$, 考虑 $(E ,\mathscr{F})$ 在 $F$ 上任意两个不同的极⼤独⽴集 $A, B$ $BA$ , 只需证 $BkA$

$A_i$ 是 \[(E,\mathscr{F}_i)\] 在 $A\cup B$ 上含 $A$ 的极⼤独⽴集，容易得 $A = \bigcap_{i=1}^k A_i$
$B_i$ 是 \[(E,\mathscr{F}_i)\] 在 $AB $ 上含 $B$ 的极⼤独⽴集，$B = \bigcap_{i=1}^k B_i$

\[\forall e \in B\backslash A\], ，由于 $e\notin A$, 有 \[e\notin \bigcap_{i=1}^k A_i\], 则 $e$ 不可能同时在每个 $A_i$ , $e$ 最多同时出现在 $k-1$ 个 $A_i\backslash A$ 中。每一个 $B\backslash A$ 中的元素最多在 $k-1$ 个 $A_i\backslash A$ 中，因此有 $ _{i=1}^k A_iABA$ , 于是：

\[ \sum_{i=1}^k \vert A_i\backslash A\vert \le (k-1)\vert B\backslash A\vert \le (k-1)\vert B\vert\\ \sum_{i=1}^k \vert A_i\vert - k\vert A\vert\le (k-1)\vert B\vert \]

由于 $(E,\mathscr{F}_i)$ 是拟阵， $A_i, B_i$ 是在 $AB $ 上的基，有 $\forall i,\vert A_i\vert = \vert B_i\vert$ .因此

\[ k\vert B\vert \le\sum_{i=1}^k\vert B_i\vert \le\sum_{i=1}^k\vert A_i\vert \le k\vert A\vert+ (k-1)\vert B\vert\\ \vert B\vert \le k\vert A\vert \]

对 $\forall F\subseteq E$, $F$ 上任意两个不同的极⼤独⽴集$A, B$ 有 $ABkA$，因此秩商最小为 $1/k$ ，贪⼼解的近似⽐至少为 $1/k$ 。