拟阵与贪心算法 #

拟阵可以用来分析和阐释贪心算法成立的原因。

子集系统 #

在了解拟阵前，需要先了解子集系统。子集系统定义在有序二元组$M=(S,L)$上，满足下面几个条件

• 基础集合S是一个有限集。
• L是由S子集构成的集合（注意L是集合的集合）且L非空。
• 遗传性：$\forall A\subseteq B$，如果$B\subseteq L$，则$A\subseteq L$（即L中元素的子集必在L中）。

注意由第二、三点可知，空集$\varnothing$必然在L中（包含空集的集合不是空集🤣）。

例子：集合$S_1=\{1,2,3\}$，$L_1$可以是$\{\varnothing ,\{1\},\{2\},\{1,2\}\}$。

拟阵 #

拟阵是特殊的子集系统，它需要满足交换性（又称独立扩展公理）：$\forall A\subseteq L$，$B\subseteq L$，$|A|＜|B|$，$\exists x\in B\setminus A$，$A\cup \{x\}\subseteq L$。

即$L_2=\{\varnothing ,\{1\},\{2\},\{3\},\{1,2\}\}$是{1,2,3}的子集系统，但是不是一个拟阵。

而$L_3=\{\varnothing ,\{1\},\{2\},\{1,2\}\}$是拟阵。

若$S$中元素带权值$w(s)$，则$M$为带权拟阵。

拟阵的并仍是拟阵。

独立集 #

独立集是拟阵中的元素，仍然用$M=(S,L)$表示子集系统。对于$A\subseteq S$，如果$A\in L$，则$A$为独立集。对于独立集$A$，若存在$x\in S$，满足$x\notin A$且$A\cup \{x\}\in L$，则称$A$为可扩展的。不可扩展的独立集为极大独立集。

它有几个性质：

• 空集一定是独立的，也就是说，$\varnothing \in L$（与子集系统定义的遗传性的推论相符）。
• 遗传性：每个独立集的子集是独立的（与子集系统定义遗传性相符）。
• 交换性：如果$A$和$B$是$L$的两个独立集，$A$比$B$有更多的元素，则在$A$中存在一个元素，当其加入$B$时得到一个比$B$更大独立集 （与拟阵定义中的交换性相符）。

关于拟阵和极大独立集有如下定理：

1. 拟阵$M=(S,L)$的所有极大独立集都有相同大小。

2. 设加权拟阵$M=(S,L)$的权函数为$w(s)$且$S$已按权非升序排序。设$x$是第一个使得$\{x\}$独立的元素，若这样的元素存在，则存在一个包含$\{x\}$的最大权独立子集。

3. 设$\{x\}$是对于加权拟阵$M=(S,L)$由定理2中所选择的S的第一个元素，则剩下问题可归结为求加权矩阵$M^{\prime }=(S^{\prime },L^{\prime })$的最大权独立集问题，其中$S^{\prime }=\{y|y\in S,(x,y)\in L\}$，$L^{\prime }=\{B|B\in S\setminus \{x\},B\cup \{x\}\in L\}$

定理的证明思路：

1. 由交换性可证定理1。

2. 设$B$是任意非空的最优子集，且$x\notin B$，$\forall y\in B$，$w(x)\ge w(y)$。构造集合$A=\{x\}$，由交换性，可反复地在$B$中找出新元素加入$A$中直到$|A|＜|B|$，且$A$仍是独立集。因此$\forall y\in B$，使得$A=B-\{y\}+\{x\}$。$w(A)=w(B)-w(y)+w(x)\ge w(B)$。定理2得证。

3. 对于定理3，在$M^{\prime }=(S^{\prime },L^{\prime })$中的最优解$X’$，$X^{\prime }\in L^{\prime }$，由$L^{\prime }$定义得$X^{\prime }\cup \{x\}\in L$。$M=(S,L)$中包含x的最优解X，$X-\{x\}\subset S-\{x\}$且$X\in L$，即$X-\{x\}\in L^{\prime }$且为$L^{\prime }$中最优解。定理3得证。

定理二和定理三本质提供了一个递归的算法，由它利用数学归纳法可以推出拟阵上使用贪心算法的正确性。

子集优化问题与贪心算法 #

子集优化问题：给集合$S$中每个元素赋予一个正值$w(s)$，在子集系统中选一个元素$E\in L$，使得$w(E)$最大，其中$w(E)=\sum _{e\in E}w(e)$。

该优化问题的解决方法是求权值最大的极大独立集。在拟阵中，可以使用贪心算法。将基础集合$S$中的所有元素$s$按$w(s)$从大到小排序，能加就加入到子集$E$中的元素$s$，就把它加入到$E$中。回顾最小生成树问题的Kruskal算法和Prim算法，是不是就是这么解决的？注意：权值和最小等价于这里的最大，可以把权值视为负数就等价了。

GreedyAlgorithm(M, w){
     A := ∅;
     (S,L) := M;
     Sort S to the descending order;
     For each x in S do
         If(A∪{x} in L) 
         	Then A := A∪{x};
     Return A;
}

案例分析：部分背包 #

给定一个最大载重量为T的背包和N种物品。已知第$i$种物品最多放入$V_i$，其单位价值为$W_i$，确定一个方案，使得装入背包中的所有物品总价值最大。

对于部分背包问题，我们首先进行一步转化：将体积为$V_i$，单位价值为$W_i$的物品变成$V_i$个体积为1，价值为$W_i$的物品。定义$M=(S，L)$：

• S是所有物品的集合。
• $L=\{X:X\subseteq S,|X|\le T\}$ 这个M显然满足拟阵的前两个条件。

根据$L$的定义，$\forall A\in L$，$\forall B\subseteq A$，满足$|B|\le |A|\le T$，有$B\in L$，因此$M$满足遗传性，是一个子集系统。

对于$\forall A\in L$，$B\in L$，$|A|＜|B|$，随意选取一个$x\in B\setminus A$，令$C=A\cup \{x\}$，显然有$|C|=|A|+1\le |B|$，所以M满足交换性。因此M是一个拟阵。

背包问题目标是使权值最大，上面提到了$S$是所有物品的集合，将$S$的任意元素$x$的权值$w(x)$定义为$x$的价值，那么问题就转化成了求背包问题的拟阵中权值最大的独立集，也就是上面的子集优化问题的变种。显然权值最大的独立集是极大独立集，同时因为$M$是拟阵，故可以用贪心算法求解。

案例分析：最小生成树(MST) #

一个有 $n$ 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有$ n$ 个结点，并且有保持图连通的最少的边。即在一给定的无向图$G=(V,E)$ 中，$(u,v)$ 代表连接顶点 $u $与顶点 $v$ 的边，而 $w(u,v)$ 代表此边的权重，若存在 $T$ 为 $E$ 的子集且为无循环图，使得 $w(T)$ 最小，则此 $T$ 为 $G$ 的最小生成树。

对于最小生成树问题，考虑无向图$G=(V,E)$，我们可以定义$M=(S,L)$：

• $S$是边集$E$。
• $L=\{X|X\subseteq E$ 且 $x$组成的图无环$\}$

这个$M$显然满足拟阵的前两个条件。

根据$L$的定义，对$\forall x\in L$，$\forall y\subseteq x$，假设$y$形成环，则$x$形成环，矛盾，所以$y$不形成环，所以$y\in L$，因此$M$满足遗传性。

考虑$\forall A\in L$，$B\in L$，$|A|＜|B|$，我们将$A$组成的森林命名为$GA$，$B$组成的森林命名为$GB$。$GA$有$|V|-|A|$个连通分量，$GB$有$|V|-|B|$个连通分量。$|A|＜|B|$，所以$|V|-|B|＜|V|-|A|$，所以$GB$中存在的一个连通分量$T$，$T$中的点在$GA$中不连通。那么$T$中必然存在一条边$x$连接$GA$中不同的连通分量的边，显然$x\notin A$且$x\in B$，且$A\cup \{x\}$无环，即$A\cup \{x\}\in L$。所以M满足交换性。因此M是一个拟阵。

因为M是一个拟阵，故可以用贪心算法解决它的子集优化问题。

补充：拟阵的秩 #

极大独立集的基数被定义为它所包含的元素个数。

对于拟阵$M=(S,L)$，$L$中的极大独立集称为拟阵的基。

用$\beta$表示基的集合，则$\beta$非空且它满足基交换性，即若$A,B\in \beta ,A\ne B,a\in A\setminus B$，则$\exists b\in B\setminus A$使得$A-\{a\}+\{b\}\in \beta$。 基交换性得每个基大小相同。

拟阵的秩就是基的大小。

子集$A$的秩通过秩函数$r(A)$定义，它有以下几种性质:

• 秩函数的值总是非负的
• 对于任意$E$的子集$A$，有$r(A)\le |A|$
• 对于$E$的任意两个子集$A$ 和$B$ ，有$r(A\cup B)+r(A\cap B)\le r(A)+r(B)$，这意味着秩函数是一个子模函数（见补充：子模函数）
• 对于任意集合A和元素x，有$r(A)\le r(A\cup \{x\})\le r(A)+1$

子集A的元素个与其秩的差$|A|-r(A)$叫作子集$A$的零化度或补秩，它是从A中移除元素使得A成为独立集的最小移除数量。

基础集合$S$在拟阵$M$上的零化度叫做拟阵$M$的零化度或$M$的补秩。

补充：次模函数 #

次模（submodular）函数：又称“子模函数”或“亚模函数”，次模函数具有次模性（submodularity），它是经济学上边际效益递减（property of diminishing returns）现象的形式化描述（若对于连续函数，单调递增时，二阶导数递减）。

从边际效益递减的角度考虑，次模函数还有一种等价定义

上式指出，当集合越来越大，s的“价值”将越来越小，正是边际效益递减的特性。这个现象在自然界普遍存在，例如：香农熵函数就是随机变量集合上的次模函数。当$S\subseteq T$时有$f(S)\le f(T)$，则称该次模函数是单调的（monotone）。 更进一步，次模性是convexity（凸性）的离散模拟。由于convexity使得连续函数更容易最优化，因而次模性在组合优化中重要作用。当目标函数是次模函数时，许多组合优化问题能够在多项式时间内得到最优解或近似解。次模函数最大化被证明是一个NP-hard问题，幸运的是，存在高效并且解的质量有保证的近似算法。一个流行的结果是：最大化一个单调非负的带基数约束（cardinality constraint，即对子集S大小的约束）的次模函数，贪心算法至少能够达到 $(1-1/e)f(S_{opt})$的结果，其中$f(S_{opt})$表示问题的最优解，1-1/e大约是0.63。

$f(S_{app})\ge (1-\frac{1}{e})f(S_{opt})$

References #

基于次模函数最大化的方法： https://blog.csdn.net/hohaizx/article/details/82936743

浅谈子集系统、拟阵与贪心：https://blog.csdn.net/MaverickFW/article/details/78207719