拟阵与贪心算法 拟阵可以用来分析和阐释贪心算法成立的原因。
子集系统 在了解拟阵前,需要先了解子集系统 。子集系统定义在有序二元组M = ( S , L ) M=(S,L) M = ( S , L ) 上,满足下面几个条件
基础集合S是一个有限集。 L是由S子集构成的集合(注意L是集合的集合)且L非空。 遗传性:∀ A ⊆ B \forall A\subseteq B ∀ A ⊆ B ,如果B ⊆ L B\subseteq L B ⊆ L ,则A ⊆ L A\subseteq L A ⊆ L (即L中元素的子集必在L中)。 注意由第二、三点可知,空集∅ \emptyset ∅ 必然在L中(包含空集的集合不是空集🤣)。
例子:集合S 1 = { 1 , 2 , 3 } S_1=\{1,2,3\} S 1 = { 1 , 2 , 3 } ,L 1 L_1 L 1 可以是{ ∅ , { 1 } , { 2 } , { 1 , 2 } } \{\emptyset,\{1\},\{2\},\{1,2\}\} { ∅ , { 1 } , { 2 } , { 1 , 2 }} 。
拟阵 拟阵 是特殊的子集系统,它需要满足交换性(又称独立扩展公理):∀ A ⊆ L \forall A\subseteq L ∀ A ⊆ L ,B ⊆ L B\subseteq L B ⊆ L ,∣ A ∣ < ∣ B ∣ |A|<|B| ∣ A ∣ < ∣ B ∣ ,∃ x ∈ B ∖ A \exists x\in B\setminus A ∃ x ∈ B ∖ A ,A ∪ { x } ⊆ L A\cup\{x\}\subseteq L A ∪ { x } ⊆ L 。
即L 2 = { ∅ , { 1 } , { 2 } , { 3 } , { 1 , 2 } } L_2=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\}\} L 2 = { ∅ , { 1 } , { 2 } , { 3 } , { 1 , 2 }} 是{1,2,3}的子集系统,但是不是一个拟阵。
而L 3 = { ∅ , { 1 } , { 2 } , { 1 , 2 } } L_3=\{\emptyset,\{1\},\{2\},\{1,2\}\} L 3 = { ∅ , { 1 } , { 2 } , { 1 , 2 }} 是拟阵。
若S S S 中元素带权值w ( s ) w(s) w ( s ) ,则M M M 为带权拟阵。
拟阵的并仍是拟阵。
独立集 独立集 是拟阵中的元素,仍然用M = ( S , L ) M=(S,L) M = ( S , L ) 表示子集系统。对于A ⊆ S A\subseteq S A ⊆ S ,如果A ∈ L A\in L A ∈ L ,则A A A 为独立集。对于独立集A A A ,若存在x ∈ S x\in S x ∈ S ,满足x ∉ A x\notin A x ∈ / A 且A ∪ { x } ∈ L A\cup \{x\}\in L A ∪ { x } ∈ L ,则称A A A 为可扩展的。不可扩展的独立集为极大独立集 。
它有几个性质:
空集一定是独立的,也就是说,∅ ∈ L \emptyset\in L ∅ ∈ L (与子集系统定义的遗传性的推论相符)。 遗传性:每个独立集的子集是独立的(与子集系统定义遗传性相符)。 交换性:如果A A A 和B B B 是L L L 的两个独立集,A A A 比B B B 有更多的元素,则在A A A 中存在一个元素,当其加入B B B 时得到一个比B B B 更大独立集 (与拟阵定义中的交换性相符)。 关于拟阵和极大独立集有如下定理:
拟阵M = ( S , L ) M=(S,L) M = ( S , L ) 的所有极大独立集都有相同大小。
设加权拟阵M = ( S , L ) M=(S,L) M = ( S , L ) 的权函数为w ( s ) w(s) w ( s ) 且S S S 已按权非升序排序。设x x x 是第一个使得{ x } \{x\} { x } 独立的元素,若这样的元素存在,则存在一个包含{ x } \{x\} { x } 的最大权独立子集。
设{ x } \{x\} { x } 是对于加权拟阵M = ( S , L ) M=(S,L) M = ( S , L ) 由定理2中所选择的S的第一个元素,则剩下问题可归结为求加权矩阵M ′ = ( S ′ , L ′ ) M'=(S',L') M ′ = ( S ′ , L ′ ) 的最大权独立集问题,其中S ′ = { y ∣ y ∈ S , ( x , y ) ∈ L } S'=\{ y|y \in S, (x,y) \in L \} S ′ = { y ∣ y ∈ S , ( x , y ) ∈ L } ,L ′ = { B ∣ B ∈ S ∖ { x } , B ∪ { x } ∈ L } L'=\{B|B\in S\setminus\{x\}, B\cup\{x\}\in L\} L ′ = { B ∣ B ∈ S ∖ { x } , B ∪ { x } ∈ L }
定理的证明思路:
由交换性可证定理1。
设B B B 是任意非空的最优子集,且x ∉ B x\notin B x ∈ / B ,∀ y ∈ B \forall y\in B ∀ y ∈ B ,w ( x ) ≥ w ( y ) w(x)\ge w(y) w ( x ) ≥ w ( y ) 。构造集合A = { x } A=\{x\} A = { x } ,由交换性,可反复地在B B B 中找出新元素加入A A A 中直到∣ A ∣ < ∣ B ∣ |A|<|B| ∣ A ∣ < ∣ B ∣ ,且A A A 仍是独立集。因此∀ y ∈ B \forall y\in B ∀ y ∈ B ,使得A = B − { y } + { x } 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) w ( A ) = w ( B ) − w ( y ) + w ( x ) ≥ w ( B ) 。定理2得证。
对于定理3,在M ′ = ( S ′ , L ′ ) M'=(S',L') M ′ = ( S ′ , L ′ ) 中的最优解X ’ X’ X ’ ,X ′ ∈ L ′ X'\in L' X ′ ∈ L ′ ,由L ′ L' L ′ 定义得X ′ ∪ { x } ∈ L X'\cup \{x\}\in L X ′ ∪ { x } ∈ L 。M = ( S , L ) M=(S,L) M = ( S , L ) 中包含x的最优解X,X − { x } ⊂ S − { x } X-\{x\}\subset S-\{x\} X − { x } ⊂ S − { x } 且X ∈ L X\in L X ∈ L ,即X − { x } ∈ L ′ X-\{x\}\in L' X − { x } ∈ L ′ 且为L ′ L' L ′ 中最优解。定理3得证。
定理二和定理三本质提供了一个递归的算法,由它利用数学归纳法可以推出拟阵上使用贪心算法的正确性。
子集优化问题与贪心算法 子集优化问题:给集合S S S 中每个元素赋予一个正值w ( s ) w(s) w ( s ) ,在子集系统中选一个元素E ∈ L E\in L E ∈ L ,使得w ( E ) w(E) w ( E ) 最大,其中w ( E ) = ∑ e ∈ E w ( e ) w(E)=\sum \limits_{e\in E} w(e) w ( E ) = e ∈ E ∑ w ( e ) 。
该优化问题的解决方法是求权值最大的极大独立集。在拟阵中,可以使用贪心算法 。将基础集合S S S 中的所有元素s s s 按w ( s ) w(s) w ( s ) 从大到小排序,能加就加入到子集E E E 中的元素s s s ,就把它加入到E E 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 i i 种物品最多放入V i V_i V i ,其单位价值为W i W_i W i ,确定一个方案,使得装入背包中的所有物品总价值最大。
对于部分背包问题,我们首先进行一步转化:将体积为V i V_i V i ,单位价值为W i W_i W i 的物品变成V i V_i V i 个体积为1,价值为W i W_i W i 的物品。定义M = ( S , L ) M=(S,L) M = ( S , L ) :
S是所有物品的集合。 L = { X : X ⊆ S , ∣ X ∣ ≤ T } L=\{X:X\subseteq S,|X|\le T\} L = { X : X ⊆ S , ∣ X ∣ ≤ T } 这个M显然满足拟阵的前两个条件。根据L L L 的定义,∀ A ∈ L \forall A\in L ∀ A ∈ L ,∀ B ⊆ A \forall B\subseteq A ∀ B ⊆ A ,满足∣ B ∣ ≤ ∣ A ∣ ≤ T |B|\le |A|\le T ∣ B ∣ ≤ ∣ A ∣ ≤ T ,有B ∈ L B\in L B ∈ L ,因此M M M 满足遗传性,是一个子集系统。
对于∀ A ∈ L \forall A\in L ∀ A ∈ L ,B ∈ L B\in L B ∈ L ,∣ A ∣ < ∣ B ∣ |A|<|B| ∣ A ∣ < ∣ B ∣ ,随意选取一个x ∈ B ∖ A x \in B\setminus A x ∈ B ∖ A ,令C = A ∪ { x } C=A\cup \{x\} C = A ∪ { x } ,显然有∣ C ∣ = ∣ A ∣ + 1 ≤ ∣ B ∣ |C|=|A|+1\le|B| ∣ C ∣ = ∣ A ∣ + 1 ≤ ∣ B ∣ ,所以M满足交换性。因此M是一个拟阵。
背包问题目标是使权值最大,上面提到了S S S 是所有物品的集合,将S S S 的任意元素x x x 的权值w ( x ) w(x) w ( x ) 定义为x x x 的价值,那么问题就转化成了求背包问题的拟阵中权值最大的独立集,也就是上面的子集优化问题的变种。显然权值最大的独立集是极大独立集,同时因为M M M 是拟阵,故可以用贪心算法求解。
案例分析:最小生成树(MST) 一个有 n n n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有$ n$ 个结点,并且有保持图连通的最少的边。即在一给定的无向图G = ( V , E ) G = (V, E) G = ( V , E ) 中,( u , v ) (u, v) ( u , v ) 代表连接顶点 $u $与顶点 v v v 的边,而 w ( u , v ) w(u, v) w ( u , v ) 代表此边的权重,若存在 T T T 为 E E E 的子集且为无循环图,使得 w ( T ) w(T) w ( T ) 最小,则此 T T T 为 G G G 的最小生成树。
对于最小生成树问题,考虑无向图G = ( V , E ) G=(V,E) G = ( V , E ) ,我们可以定义M = ( S , L ) M=(S,L) M = ( S , L ) :
S S S 是边集E E E 。L = { X ∣ X ⊆ E L=\{X|X\subseteq E L = { X ∣ X ⊆ E 且 x x x 组成的图无环} \} } 这个M M M 显然满足拟阵的前两个条件。
根据L L L 的定义,对∀ x ∈ L ∀x∈L ∀ x ∈ L ,∀ y ⊆ x ∀y⊆x ∀ y ⊆ x ,假设y y y 形成环,则x x x 形成环,矛盾,所以y y y 不形成环,所以y ∈ L y∈L y ∈ L ,因此M M M 满足遗传性。
考虑∀ A ∈ L \forall A \in L ∀ A ∈ L ,B ∈ L B\in L B ∈ L ,∣ A ∣ < ∣ B ∣ |A|<|B| ∣ A ∣ < ∣ B ∣ ,我们将A A A 组成的森林命名为G A GA G A ,B B B 组成的森林命名为G B GB GB 。G A GA G A 有∣ V ∣ − ∣ A ∣ |V|-|A| ∣ V ∣ − ∣ A ∣ 个连通分量,G B GB GB 有∣ V ∣ − ∣ B ∣ |V|-|B| ∣ V ∣ − ∣ B ∣ 个连通分量。∣ A ∣ < ∣ B ∣ |A|<|B| ∣ A ∣ < ∣ B ∣ ,所以∣ V ∣ − ∣ B ∣ < ∣ V ∣ − ∣ A ∣ |V|-|B|<|V|-|A| ∣ V ∣ − ∣ B ∣ < ∣ V ∣ − ∣ A ∣ ,所以G B GB GB 中存在的一个连通分量T T T ,T T T 中的点在G A GA G A 中不连通。那么T T T 中必然存在一条边x x x 连接G A GA G A 中不同的连通分量的边,显然x ∉ A x\notin A x ∈ / A 且x ∈ B x\in B x ∈ B ,且A ∪ { x } A\cup \{x\} A ∪ { x } 无环,即A ∪ { x } ∈ L A\cup\{x\}\in L A ∪ { x } ∈ L 。所以M满足交换性。因此M是一个拟阵。
因为M是一个拟阵,故可以用贪心算法解决它的子集优化问题。
补充:拟阵的秩 极大独立集的基数被定义为它所包含的元素个数。
对于拟阵M = ( S , L ) M=(S,L) M = ( S , L ) ,L L L 中的极大独立集称为拟阵的基 。
用β \beta β 表示基的集合,则β \beta β 非空且它满足基交换性 ,即若A , B ∈ β , A ≠ B , a ∈ A ∖ B A,B\in\beta,A\neq B,a\in A\setminus B A , B ∈ β , A = B , a ∈ A ∖ B ,则∃ b ∈ B ∖ A \exists b\in B\setminus A ∃ b ∈ B ∖ A 使得A − { a } + { b } ∈ β A-\{a\}+\{b\}\in\beta A − { a } + { b } ∈ β 。 基交换性得每个基大小相同。
拟阵的秩 就是基的大小。
子集A A A 的秩通过秩函数 r ( A ) r(A) r ( A ) 定义,它有以下几种性质:
秩函数的值总是非负的 对于任意E E E 的子集A A A ,有r ( A ) ≤ ∣ A ∣ r(A) \leq|A| r ( A ) ≤ ∣ A ∣ 对于E E E 的任意两个子集A A A 和B B B ,有r ( A ∪ B ) + r ( A ∩ B ) ≤ r ( A ) + r ( B ) r(A \cup B)+r(A \cap B) \leq r(A)+r(B) r ( A ∪ B ) + r ( A ∩ B ) ≤ r ( A ) + r ( B ) ,这意味着秩函数是一个子模函数(见补充:子模函数) 对于任意集合A和元素x,有r ( A ) ≤ r ( A ∪ { x } ) ≤ r ( A ) + 1 r(A) \leq r(A \cup\{x\}) \leq r(A)+1 r ( A ) ≤ r ( A ∪ { x }) ≤ r ( A ) + 1 子集A的元素个与其秩的差∣ A ∣ − r ( A ) |A|-r(A) ∣ A ∣ − r ( A ) 叫作子集A A A 的零化度或补秩 ,它是从A中移除元素使得A成为独立集的最小移除数量。
基础集合S S S 在拟阵M M M 上的零化度叫做拟阵M M M 的零化度或M M M 的补秩 。
补充:次模函数 次模(submodular)函数:又称“子模函数”或“亚模函数”,次模函数具有次模性(submodularity),它是经济学上边际效益递减(property of diminishing returns)现象的形式化描述(若对于连续函数,单调递增时,二阶导数递减)。
TIP
次模函数定义:
给定一个集合函数f : 2 V → R f:2^V→\R f : 2 V → R ,其将有限集V的一个子集S ⊆ V S\subseteq V S ⊆ 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 ( S ∪ T ) + f ( S ∩ T ) ≤ f ( S ) + f ( T )
则称f ( ⋅ ) f(\cdot) f ( ⋅ ) 是次模函数。
从边际效益递减的角度考虑,次模函数还有一种等价定义
TIP
次模函数定义:
从边际效益递减的角度考虑,次模函数还有一种等价定义:对任意的R ⊆ S ⊆ V R\subseteq S \subseteq V R ⊆ S ⊆ V ,并且s ∈ V ∖ S s\in V\setminus S s ∈ V ∖ S ,
f ( S ∪ { s } ) − f ( S ) ≤ f ( R ∪ { s } ) − f ( R ) f(S\cup \{s\})-f(S)\leq f(R\cup \{s\})-f(R) f ( S ∪ { s }) − f ( S ) ≤ f ( R ∪ { s }) − f ( R )
上式指出,当集合越来越大,s的“价值”将越来越小,正是边际效益递减的特性。这个现象在自然界普遍存在,例如:香农熵函数就是随机变量集合上的次模函数。当S ⊆ T S\subseteq T S ⊆ T 时有f ( S ) ≤ f ( T ) f(S)\leq f(T) f ( S ) ≤ f ( T ) ,则称该次模函数是单调的(monotone)。 更进一步,次模性是convexity(凸性)的离散模拟。由于convexity使得连续函数更容易最优化,因而次模性在组合优化中重要作用。当目标函数是次模函数时,许多组合优化问题能够在多项式时间内得到最优解或近似解。次模函数最大化被证明是一个NP-hard问题,幸运的是,存在高效并且解的质量有保证的近似算法。一个流行的结果是:最大化一个单调非负的带基数约束(cardinality constraint,即对子集S大小的约束)的次模函数,贪心算法至少能够达到 ( 1 − 1 / e ) f ( S o p t ) (1-1/e)f(S_{opt}) ( 1 − 1/ e ) f ( S o pt ) 的结果,其中f ( S o p t ) f(S_{opt}) f ( S o pt ) 表示问题的最优解,1-1/e大约是0.63。
f ( S a p p ) ≥ ( 1 − 1 e ) f ( S o p t ) f(S_{app})\geq (1-\frac{1}{e})f(S_{opt}) f ( S a pp ) ≥ ( 1 − e 1 ) f ( S o pt )
References 基于次模函数最大化的方法: https://blog.csdn.net/hohaizx/article/details/82936743
浅谈子集系统、拟阵与贪心:https://blog.csdn.net/MaverickFW/article/details/78207719