拟阵与最优化问题

# 目录 · 引子 · 拟阵的相关定义 · 拟阵上的最优化问题 · 例子：最小生成树问题 · 例子：任务调度问题 ## 引子 竞赛中我们时常会用到贪心算法，而这里我们将要讨论的拟阵 $(Matroid)$ 便是研究贪心算法的数学基础。如果一个问题可以转化为拟阵，那么它便一定可以使用贪心进行解决，且解决方法有迹可循(但不是所有可以贪心的问题都可以转化为拟阵)。 本文面向拟阵初学者，致力于让像作者一样的蒟蒻也能看得懂。但在阅读本文之前，请确认你对集合的相关知识有所了解 $QwQ$ ## 拟阵的相关定义 **子集系统**是一个二元组，对于一个子集系统 $M=(S,L)$ ,它需要满足以下三个条件： $(1)$ $S$ 是一个有限集 $(2)$ $L$ 是一个有限非空集，其**元素**是 $S$ 的部分子集 $(3)$ 具有**遗传性** ，即对于任意$A⊆B$ ，若$B∈L$，那么一定有$A∈L$ **拟阵**是一个子集系统，它还需要满足**交换性** ，即对任意$A∈L$，$B∈L$且 $|A|<|B|$ ( $|A|$ 表示 $A$ 中的元素个数，以下同义) , 一定存在元素 $x∈B$ 且 $x∉A$ ,使得 $A$ $∪$ { $x$ } $∈L$ 这里我们通俗的理解一下：$S$ 是我们可能采购的物品的集合，$L$是部分采购清单的集合。若 $M=(S,L)$是拟阵，那么由**遗传性**，我们知道从任何一张采购清单 $A$ ($A∈L$) 中选出部分物品组成的新的采购清单 $B$ 一定满足 $B∈L$ 。而由**交换性**，我们知道若有两张采购清单$A$，$B$ ($A∈L,B∈L$，$|A|<|B|$ ) ，那么必然可以找到一件物品在 $A$ 中没有但在 $B$ 中有，且将这件物品加入 $A$ 后形成的新的清单也在 $L$ 中 这里给出一个简单的拟阵实例，大家自行验证 ``` M=(S,L) S={1,2,3,5} L={ {1},{3},{5},{1,3},{1,5},{3,5},{1,3,5} } ``` 同时，为了方便接下来的讨论，对拟阵$M=(S,L)$给出以下定义： $(1)$ 若$A∈L$，那么称 $A$ 为**独立集** $(2)$ 对于独立集 $A$ ，若存在 $ x∈S $，满足 $ x ∉ A $且$A$ $∪$ { $x$ } $∈L$，那么称 $A$ 为**可拓展的**。若独立集 $A$ 不可拓展，那么称 $A$ 为**极大独立集**。 **定理——同一拟阵的极大独立集元素个数(即大小)相同** >证明: >反证法。设 $A$与 $B$ 为拟阵的两个大小不同的极大独立集，不妨设$|A|<|B|$，那么根据拟阵的**交换性**，$A$ 是可拓展的，不满足最大独立集的定义，与假设矛盾，故命题成立。 ## 拟阵上的最优化问题 ~~(直到现在，我们还是不知道拟阵到底有什么用)~~ 别急，接下来，我们讨论拟阵与最优化问题的关系。 为了对我们要解决的问题进行描述，对拟阵 $M=(S,L)$ ，我们对 $S$ 内的每一个元素赋予一个**正整数**权值 $w(x) $ ("整数"这里只是规定，事实上我们在解决问题时可以进行融会贯通) , 定义 $S$ 的子集 $A$ 的权值 $w(A)$ = $∑_{x∈A}w(x)$，即其元素权值和。 我们规定权值最大的独立集为**权值最大独立集**，显然权值最大独立集一定是极大独立集。 >简单的证明一下： >若独立集 $A$ 在拟阵 $M$ 中不是极大独立集，那么它一定是可拓展的，又因为权值一定为正，所以 $A$ 拓展后的集合的权值一定大于 $w(A)$ ，所以 $A$ 一定不是权值最大独立集。(要求权值为正的作用在这里便体现了) 通常，我们求出的权值最大独立集与最终答案息息相关。拟阵解决贪心问题的规律便在于此——对于任何能够转换为拟$M=(S,L)$的问题，都可以通过如下算法解决(即求出权值最大独立集)： ``` Set Solve(M,w)//给出拟阵M与权值函数w (Set这里意为返回一个集合) { 清空A; 将S按w(x)的大小降序排好； for(对每一个x∈S,按w(x)降序) { if(A∪{x}∈L) A=A∪{x}； } return A;//即权值最大独立集 } ``` 令$n=|S|$,$f(n)$表示判断独立集的复杂度，那么上述算法的时间复杂度为$O(nlog_2n+nf(n))$ 。事实上，在将问题转化为拟阵后，套用该算法的关键便在于如何判断独立集。不同问题有不同的独立集及判定方法，拟阵体现的是这些问题允许贪心的共性。 $and$ $then$ 这个贪心算法正确吗？ ~~废话，不正确我还讲什么~~ 如何证明它呢？为了证明最终的 $A$ 为权值最大独立集，我们可以证明在任何时刻 $A$ 都是某一目标(权值最大独立集)的子集，这样最终无法拓展的 $A$ 便一定是某一权值最大独立集。 **引理**：对于拟阵 $M=(S,L)$ , $A∈L$，$A$ 为该拟阵某一权值最大独立集 $T$ 的子集 ，定义集合$P=${$x| $ $ A$ $∪$ { $x$ } $∈L$}， $y$ 为$P$中权值最大的元素，那么令 $A'$ =$A$ $∪$ { $y$ }，则$ A'$也是某一权值最大独立集的子集。 >证明： >反证法。由引理的定义,假设 $A'$ 不是任一权值最大独立集的子集。那么对于权值最大独立集 $T$ ，当$|A'|<|T|$，由拟阵的 **交换性** 可得知一定存在 $x$ 满足 $x∈T$ ，$x∉A$且 $A$ $∪$ { $x$ } $∈L$ ,那么我们不断令$A'=A'$ $∪$ { $x$ }直到 $|A'|=|T|$ , 由先前假设可知**此时**： >定义$K=A'$ $∩$ $T$ , 那么有{ $y$ } $=∁_TK$ , { $x$ } $=∁_{A'}K$，$w(y)≤w(x)$ 。 >因此此时 $w(A')=w(K)+w(x)≥w(K)+w(y)=w(T)$ >若$w(A')>w(T)$，那么 $T$ 不是权值最大独立集，与假设矛盾 ; 若$w(A')=w(T)$ ，那么现在的 $A' $ 为权值最大独立集，最开始的 $A'$ 是此权值最大独立集的子集，也与假设矛盾，故引理成立。 可以看出，在上述证明中拟阵的**交换性**起到了至关重要的作用，这也说明了一点，在子集系统中贪心不一定正确，需要赋予之**交换性**使之成为拟阵，它才能派上用场。 可能你看到这里还是有点懵，或许你在想——即使求出这个权值最大独立集又有什么用呢？别急，我们已经完成了所有的定义及证明，接下来就带大家感受一下拟阵的实际应用。 ## 例子:最小生成树问题 相信大家都知道什么是最小生成树了，在此不再赘述定义。 现在我们从拟阵的角度分析最小生成树问题。 对于无向图 $G= (V , E)$ 【注 : $V$ 是点集，$E$ 是边集】 我们定义这样一个$M=(S,L):$ $(1)$ $S=E$ $(2)$ $L=${ $x$ $|$ $x⊆E$ 且图 $G'=(V,x)$ 中无环 } 这个 $M$ 显然满足子集系统的前两个条件。这里证明其具有遗传性与交换性： >遗传性：对任意$A∈L$， $B⊆A$ , 显然$B⊆E$。假设 $B$ 中有环，那么 $A$ 中也一定有环，与 $A∈L$ 矛盾，故 $B$ 中无环，因此$B∈L$ ， $M$具有遗传性。 >交换性：对任意$A∈L$，$B∈L$，设$|A|<|B|$，显然 $G_A=(V,A)$ 中有$|V|-|A|$ 个连通分量 , $G_B=(V,B)$ 中有$|V|-|B|$ 个连通分量。 >由$|A|<|B|$ 有 $|V|-|A|$ $>$ $|V|-|B|$ , 可知此时 $B$ 中一定存在一条边 $x$ 连接了 $G_A$ 中的两个不同的连通分量。显然，$G'=$( $V$ , $A$ $∪$ { $x$ }$)$中无环且$A$ $∪$ { $x$ } $∈L$ ，因此$M$具有交换性。 综上，$M$是一个拟阵。 现在，我们需要设计权值函数 $w(x)$ 了。我们需要思考，如何将求最小生成树这一权值最小化的问题转化为求权值最大独立集的问题呢？我们自然而然的想到将权值取相反数，但是这样就产生了负数，不满足$w(x)$的要求了。怎么办呢？我们可以先将权值取相反数，再统一加上一个足够大的数使得权值为正即可，因此，我们使元素的权值为 $w(x)=x$ 的边权的相反数 $+(E$ 中最大边权 $+1)$，此时便满足 $w(x)>0 $了， 我们便可以使用上述贪心模板进行求解了。 或许你已经发现，如果我们使用并查集来判断环(即判断独立集)，那么这个贪心算法与著名的 $Kruskal$ 算法几乎一模一样，将边按$w(x)$降序排列其实也就是将边按原本权值升序排列。 因此，我们刚刚使用拟阵工具进行的分析事实上是对$Kruskal$ 算法进行了证明 (而贪心正确性的保证便是证明)~~(别跟我说是大量对拍)~~ 由于$Kruskal$ 算法广为人知，这里就不给出代码了 ~~(懒)~~ 。 ## 例子:任务调度问题 给定一个完成时间**均是单位时间**的任务集合 $S$ ，集合 $S$ 中的每个任务都有一个截止期限 $ d_i$ 和超时惩罚 $ w_i$ ，你需要找出集合 $S$ 的一个调度，使得因任务误期所导致的总惩罚最小。(上述出现的数据均为正整数) 还是先定义拟阵。 令$M=(S,L)$ $(1)$ $S$ 即所给集合 $(2)$ $L=${ $x|$ $x⊆S$ , 且存在对 $x$ 的合理调度使总惩罚为$0$} 显然，这个 $M$ 满足子集系统的前两个条件。我们只需要证明其具有遗传性与交换性即可。 >遗传性：对任意$A∈L$， $B⊆A$ , 显然$B⊆S$。因为 $A∈L$ ，所以减少了部分任务的 $B$ 也一定存在合理的调度使得总惩罚为 $0$ ， 故$M$具有遗传性。 >交换性：对任意$A∈L$，$B∈L$，设$|A|<|B|$，显然 $A$ 中存在任务 $x$ 满足$x∈B$ ，$x∉A$ ，我们取其中完成期限最靠后的一个任务$x'$。 >由于完成期限在 $x'$ 之后的任务集 $P$ 在 $A$ , $B$ 中均含有，我们便令$A'=∁_AP$ ,$B'=∁_BP$ ，显然$|A'|<|B'|$，由 $B∈L$ 我们知道在 $x'$ 完成期限之前至少可以合理调度$|B'|$个任务，又因为$|B'|>|A'|$，所以在 $A'$ 的合理调度中一定存在位于 $x'$ 完成期限前的空余时间，在此安排 $x'$ 一定不会增加新的惩罚。 >因此$A$ $∪ $ { $x'$ }$∈L$ , $M$ 具有交换性。 综上所述， $M$ 是一个拟阵。 那么如何设计权值函数呢？在这里我们令元素的权值$w(x)=w_x$ ，即惩罚。 在这样设计权值函数之后，我们可以先把所有任务没有完成的的惩罚统计出来。再计算上述拟阵的权值最大独立集(即最多免受的惩罚)，两者相减即是答案。 最后就是对独立集的判断，我们可以考虑贪心地安排任务来检验是否存在合法调度(这是一个非常简单的贪心) 其实，我们可以发现，有的题目中，我们靠**人类智慧**可以直接推出最后的贪心策略，那拟阵是不是就没有用了呢？事实上，不然，在本蒟蒻看来，拟阵提供了一种可能的套路化的方法将问题进行正确的转化，使复杂问题简单化，方便我们求解。 关于拟阵的初步讲解到这里就结束了，大家可以去尝试使用拟阵解决各类贪心问题，感受其妙处$QwQ$