Skip to content

拟阵与贪心算法 ​

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

子集系统 ​

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

  • 基础集合S是一个有限集。
  • L是由S子集构成的集合(注意L是集合的集合)且L非空。
  • 遗传性:∀A⊆B\forall A\subseteq B,如果B⊆LB\subseteq L,则A⊆LA\subseteq L(即L中元素的子集必在L中)。

注意由第二、三点可知,空集∅\emptyset必然在L中(包含空集的集合不是空集🤣)。

例子:集合S1={1,2,3}S_1=\{1,2,3\},L1L_1可以是{∅,{1},{2},{1,2}}\{\emptyset,\{1\},\{2\},\{1,2\}\}。

拟阵 ​

拟阵是特殊的子集系统,它需要满足交换性(又称独立扩展公理):∀A⊆L\forall A\subseteq L,B⊆LB\subseteq L,∣A∣<∣B∣|A|<|B|,∃x∈B∖A\exists x\in B\setminus A,A∪{x}⊆LA\cup\{x\}\subseteq L。

即L2={∅,{1},{2},{3},{1,2}}L_2=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\}\}是{1,2,3}的子集系统,但是不是一个拟阵。

而L3={∅,{1},{2},{1,2}}L_3=\{\emptyset,\{1\},\{2\},\{1,2\}\}是拟阵。

若SS中元素带权值w(s)w(s),则MM为带权拟阵。

拟阵的并仍是拟阵。

独立集 ​

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

它有几个性质:

  • 空集一定是独立的,也就是说,∅∈L\emptyset\in L(与子集系统定义的遗传性的推论相符)。
  • 遗传性:每个独立集的子集是独立的(与子集系统定义遗传性相符)。
  • 交换性:如果AA和BB是LL的两个独立集,AA比BB有更多的元素,则在AA中存在一个元素,当其加入BB时得到一个比BB更大独立集 (与拟阵定义中的交换性相符)。

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

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

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

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

定理的证明思路:

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

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

  3. 对于定理3,在M′=(S′,L′)M'=(S',L')中的最优解X’X’,X′∈L′X'\in L',由L′L'定义得X′∪{x}∈LX'\cup \{x\}\in L。M=(S,L)M=(S,L)中包含x的最优解X,X−{x}⊂S−{x}X-\{x\}\subset S-\{x\}且X∈LX\in L,即X−{x}∈L′X-\{x\}\in L'且为L′L'中最优解。定理3得证。

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

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

子集优化问题:给集合SS中每个元素赋予一个正值w(s)w(s),在子集系统中选一个元素E∈LE\in L,使得w(E)w(E)最大,其中w(E)=∑e∈Ew(e)w(E)=\sum \limits_{e\in E} w(e)。

该优化问题的解决方法是求权值最大的极大独立集。在拟阵中,可以使用贪心算法。将基础集合SS中的所有元素ss按w(s)w(s)从大到小排序,能加就加入到子集EE中的元素ss,就把它加入到EE中。回顾最小生成树问题的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种物品。已知第ii种物品最多放入ViV_i,其单位价值为WiW_i,确定一个方案,使得装入背包中的所有物品总价值最大。

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

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

根据LL的定义,∀A∈L\forall A\in L,∀B⊆A\forall B\subseteq A,满足∣B∣≤∣A∣≤T|B|\le |A|\le T,有B∈LB\in L,因此MM满足遗传性,是一个子集系统。

对于∀A∈L\forall A\in L,B∈LB\in L,∣A∣<∣B∣|A|<|B|,随意选取一个x∈B∖Ax \in B\setminus A,令C=A∪{x}C=A\cup \{x\},显然有∣C∣=∣A∣+1≤∣B∣|C|=|A|+1\le|B|,所以M满足交换性。因此M是一个拟阵。

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

案例分析:最小生成树(MST) ​

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

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

  • SS是边集EE。
  • L={X∣X⊆EL=\{X|X\subseteq E 且 xx组成的图无环}\}

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

根据LL的定义,对∀x∈L∀x∈L,∀y⊆x∀y⊆x,假设yy形成环,则xx形成环,矛盾,所以yy不形成环,所以y∈Ly∈L,因此MM满足遗传性。

考虑∀A∈L\forall A \in L,B∈LB\in L,∣A∣<∣B∣|A|<|B|,我们将AA组成的森林命名为GAGA,BB组成的森林命名为GBGB。GAGA有∣V∣−∣A∣|V|-|A|个连通分量,GBGB有∣V∣−∣B∣|V|-|B|个连通分量。∣A∣<∣B∣|A|<|B|,所以∣V∣−∣B∣<∣V∣−∣A∣|V|-|B|<|V|-|A|,所以GBGB中存在的一个连通分量TT,TT中的点在GAGA中不连通。那么TT中必然存在一条边xx连接GAGA中不同的连通分量的边,显然x∉Ax\notin A且x∈Bx\in B,且A∪{x}A\cup \{x\}无环,即A∪{x}∈LA\cup\{x\}\in L。所以M满足交换性。因此M是一个拟阵。

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

补充:拟阵的秩 ​

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

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

用β\beta表示基的集合,则β\beta非空且它满足基交换性,即若A,B∈β,A≠B,a∈A∖BA,B\in\beta,A\neq B,a\in A\setminus B,则∃b∈B∖A\exists b\in B\setminus A使得A−{a}+{b}∈βA-\{a\}+\{b\}\in\beta。 基交换性得每个基大小相同。

拟阵的秩就是基的大小。

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

  • 秩函数的值总是非负的
  • 对于任意EE的子集AA,有r(A)≤∣A∣r(A) \leq|A|
  • 对于EE的任意两个子集AA 和BB ,有r(A∪B)+r(A∩B)≤r(A)+r(B)r(A \cup B)+r(A \cap B) \leq r(A)+r(B),这意味着秩函数是一个子模函数(见补充:子模函数)
  • 对于任意集合A和元素x,有r(A)≤r(A∪{x})≤r(A)+1r(A) \leq r(A \cup\{x\}) \leq r(A)+1

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

基础集合SS在拟阵MM上的零化度叫做拟阵MM的零化度或MM的补秩。

补充:次模函数 ​

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

TIP

次模函数定义:

给定一个集合函数f:2V→Rf:2^V→\R ,其将有限集V的一个子集S⊆VS\subseteq V映射为一个实数。

如果对于任意S,满足:

f(S∪T)+f(S∩T)≤f(S)+f(T)f(S\cup T)+f(S\cap T)\leq f(S)+f(T)

则称f(⋅)f(\cdot)是次模函数。

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

TIP

次模函数定义:

从边际效益递减的角度考虑,次模函数还有一种等价定义:对任意的R⊆S⊆VR\subseteq S \subseteq V,并且s∈V∖Ss\in V\setminus S,

f(S∪{s})−f(S)≤f(R∪{s})−f(R)f(S\cup \{s\})-f(S)\leq f(R\cup \{s\})-f(R)

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

f(Sapp)≥(1−1e)f(Sopt)f(S_{app})\geq (1-\frac{1}{e})f(S_{opt})

References ​

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

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