概论
拟阵是一种数学工具，可以用来证明贪心算法的正确性。
定义与定理
$\text{Def 1.}$ 对于一个二元组 $M=(S,L)$，若 $M$ 满足
- $S$ 是一个有限集
- $L$ 是一个有限非空集，它是 包含 $S$ 的所有子集的集合的一个子集
- $\forall A\subseteq B,B\in L\Rightarrow A\in L$
则称 $M$ 为子集系统
如果你对最后一条有符号上的疑问 ，你可能需要再注意下第二条中 $L$ 的定义
$\text{Def 2.}$ 对于一个子集系统 $M=(S,L)$，若 $M$ 满足
$\forall A,B\in L,| A| < |B|,\exists x\in B,x\notin A,s.t.A\cup\{x\}\in L$
则称 $M$ 为拟阵
$\text{Def 3.} $ 对于一个拟阵 $M=(S,L)$，若 $A\in L$，则称 $A$ 为独立集
$\text{Def 4.}$ 对于一个独立集 $A$，若
- $\exists x\in S,s.t. x\notin A,A\cup\{x\}\in L$
则称 $A$ 是可拓展的
若一个独立集 $A$ 不可拓展，则称 $A$ 是一个极大独立集
$\text{Theorem 1}$ 同一拟阵的极大独立集大小相同
$\text{Proof}$ 考虑反证法，假设$\exists A,B$ 为同一拟阵的极大独立集，$|A|<|B|$，由拟阵的定义得 $A$ 是可拓展的，矛盾，证毕
$\text{Def 5.}$ 对于一个拟阵 $M=(S,L)$，我们给 $\forall x\in S$ 赋一个权值 $w(x)$，一个集合 $A\in S$ 的权值 $w(A)=\sum_{x\in A} w(x)$，那么称权值最大的独立集为权值最大独立集，一个显然的事实是权值最大独立集一定是一个极大独立集
应用
接下来我们将探讨拟阵的应用。
先考虑对于一个给定的拟阵 $M=(S,L)$ 和权值函数 $w(x)$，如何求出该拟阵的一个权值最大独立集。
一个比较显然的想法是，我们维护一个集合 $A$，每次选出当前 $w(x)$ 最大且 $A\cup\{x\}\in L$ 的 $x$ 加入集合。接下来证明这个算法是正确的。
$\text{Proof}$ 考虑反证法。假设 $\exists A’\neq A$ 是拟阵的一个极大独立集，且 $w(A’)>w(A)$。
也就是说在算法执行的某一个时刻，我们选择了当前可选的权值最大元素，使得后面可选的元素比另一种方案劣。不妨设这个时刻是算法刚开始的时刻，假设当前可选的最大元素为 $m$，本来应该选的元素为 $n$，而最优方案为 $\{n\}\cup A’$，选取了最大元素后方案为 $\{m\}\cup A$，那么根据 $w(A’)>w(A)$ 和拟阵的定义，$|\{m\}|<|A’|\Rightarrow \exists x\in A’,x\neq m,\{m,x\}\in L$，按照上面所说的 $\{m,n\}\notin L$，我们有 $\{m\}\cup A’\in L$。
根据 $w(m)>w(n)$，所以 $w(\{m\}\cup A’)>w(\{n\}\cup A’)$ ，矛盾，证毕
于是我们有了一个求拟阵的权值最大独立集的算法，那么这个算法效率如何呢？我们设 $T_1(n)$ 表示计算一次 $w(x)$ 的时间复杂度，设 $T_2(n)$ 表示判断 $A$ 是否为独立集的复杂度，那么总时间复杂度就为 $O(T_1(n)\times n\log n+T_2(n)\times n)$。
但是这个算法有什么用呢？我们发现这个算法本质上就是贪心，那么这个算法与贪心有什么共性吗？答案是肯定的，事实上对于一道贪心题，只要我们能够抽象出一个对象，并证明这个对象是拟阵，那么我们就可以利用这个算法去求解该问题。所以，在求解部分贪心题时，我们所做的就是转化成拟阵，然后求该拟阵的最大权值独立集。这是一件好事，因为我们成功将归纳了一类题目的解法。
总结
我们实际上是抽象了一类贪心的共同特点，并基于此来证明这一类贪心的证明。