贪心算法及其理论依据—

贪心算法及其理论依据——拟阵

　　拟阵理论主要是研究定义在一个集合的子集合上的抽象相关关系。不是相关的子集通常也叫独立集。一个拟阵可以有许多不同但是等价的方法定义。

拟阵与子集系统

定义：

　　子集系统是一个二元组M=(S,L)，它须满足以下条件：

S是一个有限集(finite set or ground set)。
L是由S的一些子集组成的有限非空集。
遗传性：对任意B∈L，任意A⊆B，有A∈L（∅必须是L的元素）
拟阵是一个子集系统，必须满足：交换性：对任意A∈L，B∈L，|A|＜|B|，存在一个x∈B-A，使A∪{x}∈L。

　　拟阵是一种组合结构，遗传性和交换性是拟阵最根本的两条性质，拟阵上的其他性质都是基于这两个性质发展出来的。

拟阵上的最优化问题

　　一旦发现了最优化问题的拟阵结构，就可以对该问题实施贪心算法，这是由拟阵的性质决定的。当然仍有大量可以用贪心算法解决的问题无法被拟阵结构覆盖（如哈夫曼问题，最多不冲突区间问题等）。

　　对于拟阵M=(S,L)，我们对S的每个元素x赋予一个正整数权值w(x)，S的任意子集U的权值w(U)=Σ_x∈Uw(x)，即为其所有元素的权值和。对于M，我们希望求出它的一个权值最大独立集。

　　贪心算法主要采用局部最优的解决问题的策略，但是在很多时候都不能达到全局最优的效果，那么什么时候使用贪心算法能够得到全局最优呢？就此引出拟阵的概念。

闭包

　　设M(S,l)是个拟阵，X⊆S是个子集。对任意的e∈S，若r_M(X∪e)=r_M(X)，则称e依赖于X，并记e~_MX。当无需强调M时，记e~X。全体S中依赖于X的元素构成的子集称为X在M中的闭包(closure)，记作

cl_M(X)={e∈S:r(X)=r(X∪e)}

若子集X满足X=cl_M(X)，则称X是M的闭集(closed set)。当无需强调拟阵M是，可用cl(X)来代替cl_M(X)。

　　由于X的闭包cl_M(X)是唯一地由X所确定的，因此可以把取闭包的运算看作是一个算子cl_M:2^S→2^S（称为闭包算子(closure operator)）。

极小圈公理

　　设M(S,l)是一个拟阵。若子集X∈Opp(l)=2^S-l，则X称为M的一个相关集(dependent set)。极小的相关集叫做极小圈(circuit)。令c(M)表示由拟阵M的全体极小圈组成的集合，则有c(M)=Min(Opp(l))。当C∈c(M)，并且|C|=k时，称C为M的一个k-极小圈(k-circuit)，k为C的长度。

　　设M(S,l)是一个拟阵，c=c(M)，则c满足下列性质：

(C1)∅∉c。(因为M(S,l)是拟阵，l满足独立集公理，∅∈l，故∅∉c)
(C2)若C₁,C₂∈c且C₁⊆C₂，则C₁=C₂。(若C₁,C₂∈c且C₁⊆C_2，因为C₁∈2^S-l而C₂是2^S-l中的极小元，所以一定有C₁=C₂)
(C3)若C₁≠C₂，C₁,C₂∈c并且e∈C₁∩C₂，则恒有C₃∈c满足C₃⊆(C₁∪C₂)-e。(只要证明C₁∪C₂-e∈2^S-l)

证明C₁∪C₂-e∈2^S-l

秩函数

贪心算法的一般步骤

确定待解问题的最优子结构
设计递归求解方式
证明在递归的任一阶段，最优选择之一总是贪心的（那么贪心选择是最适合的）
证明通过做贪心选择，所有的子问题都为空（除一个以外）
设计实现贪心策略的递归算法
将设计好的递归算法转换成迭代算法

贪心选择　　

　　贪心算法中，我们所做的总是当前看似最佳的选择，然后在解决经过贪心选择之后所出现的子问题。其作出的当前的选择可能要依赖于已经做出的所有选择，但不依赖于未做出的选择或子问题的解。贪心算法采取的贪婪策略往往是自顶向下的。核心所在就是要证明每一步所做的贪心选择最终能产生一个全局最优解。

最优子结构

　　对于一个问题，如果它的一个最优解包含了其子问题的最优解，则称该问题具有最优子结构（最优子结构的证明采用部分替换法）。

设计贪心算法的一般步骤

将优化问题转化为：先做出选择，再解决剩下的一个子问题
证明原问题总是有一个最优解是做贪心选择而得到的，从而证明贪心选择的安全性与鲁棒性
说明做出贪心选择之后，剩余的子问题具有一个性质：如果将子问题的最优解和所做的贪心选择联合，可以得到原问题的一个最优解

拟阵来源

　　1935年，Whitney把以上两条性质进行了抽象推广，提出了拟阵的概念。

拟阵

　　拟阵理论是组合优化的一个分支。拟阵理论并不是因为贪心算法而引入，但是却是贪心算法的强力辅助。拟阵理论不能完全覆盖所有的贪心算法（如赫夫曼编码问题），但它可以覆盖大多数具有实际意义的情况。

　　在问题模型满足拟阵结构的情况下，贪心策略总是能够得到最优解。

拟阵的概念

定义1：子集系统的优化问题

定义2：拟阵

注意：上图中l∈2S应为l∈2^S，且集合l中的元素称为拟阵M的独立集，因此上图中的1，2，3称为独立集公理。拟阵M通常也记作M=(S,l)，以强调这是一个在S上以l中的元素为独立集的拟阵。

同构

对于给定的两个拟阵M₁(S₁,l₁)和M₂(S₂,l₂)，若映射∅(不是空集，用红色与空集区分)：S₁→S₂满足以下条件：

∅：S₁→S₂是一个一一对应，
对任意子集X⊆S₁，X∈l₁当且仅当∅(X)∈l₂.

则称∅：S₁→S₂为从M₁到M₂的一个同构。若这样的∅存在，称M₁与M₂同构，记作M₁≌M₂。对每个拟阵M，易见全体从M到M的同构在映射的复合下构成一个群Aut(M)（称为M的自同构群）。

贪心算法

定义4：拟阵的权函数

定义5：拟阵的最大权独立集问题

拟阵的性质

定义3：独立子集

极大独立子集与极大线性无关组的关系？？？

定理1

定理2

定理3

贪心算法

拟阵外史

加权拟阵与贪心

一个有限拟阵是一个满足下列条件的二元组M=(S,I)：

S是一个有限集
I是由S的一些子集组成的有限非空集合（非空族），这些子集称为S的独立子集。属于I的子集要满足的条件是：如果B∈I且A⊆B，那么有A∈I。这种性质称为遗传性（如果I满足这种性质我们称I是遗传的）。规定，∅∈I
若A∈I，B∈I且|B|＞|A|，那么∃x∈B-A使得A∪{x}∈I。这种性质称为交换性质（称M满足交换性质）

拟阵例子

　　M=(S,I)是一个拟阵，其中：

　　S={1,2,3}，I={size≤2的子集}={∅,{1},{2},{3},{1,2},{1,3},{2,3}}

　　如果说拟阵中的一个独立子集A不存在扩展，那么就称它是最大的，这里有一个比较重要的性质：拟阵中所有的最大独立子集都具有相同的大小

加权拟阵

　　如果一个拟阵M=(S,I)关联了一个权重函数w，这个函数为S中的每一个元素x赋予一个严格大于0的权重w(x)，那么我们称这个拟阵M是加权的。子集A的权值就是

问题

　　在加权拟阵中寻找最大权重独立子集，即给定一个加权拟阵M=(S,I)，寻找独立集A∈I使得w(A)最大

贪心法求解

将S中的元素按照w降序排列
现在有一个集合A（初始的时候为∅），按照上面排好的顺序依次考虑S中的每个元素，如果说这个元素x满足A∪{x}是独立的，那么将x加入A中
A就是答案

拟阵的贪心选择性

　　假定 $M = (S, T)$

$M = (S, T)$

1、对于拟阵 $M = (S, I)$

　　证明：由于 $x$

2、对于拟阵 $M = (S, I)$

　　证明：（就是1的逆否命题）

　　所以我们可以得知，如果一个元素首次不能用于构造独立集，之后永远也不可能用到了

　　因此寻找起始元素时，贪心地直接跳过 $S$ $S$

$S$

次模函数

参考文献

赖虹建. 拟阵论[M]. 高等教育出版社, 2002.

次模函数

拟阵