拟阵及其简单应用

《拟阵及其简单应用》由会员分享，可在线阅读，更多相关《拟阵及其简单应用（20页珍藏版）》请在金锄头文库上搜索。

1、拟阵及其简单应用,By 川雾,最大权极大线性无关组,集合包含个维向量，其中第个向量有一个权 。 求的一个最大权和子集，满足该子集中所有向量线性无关。,判断大小为的向量组是否线性无关，通常需要( 3 )的复杂度 ,如果该线性空间在有限域上(如模2剩余类整数域)，有没有解决办法？,最大权极大线性无关组,事实上，本题可以使用贪心解决。 将所有向量按照 从大到小排序，然后逐个加入答案集合中。如果某个向量能被线性表出，则放弃该向量。 最终的到的集合一定是最优解。如何证明其正确性？这就引出了我们今天的主角拟阵,拟阵,拟阵理论(Matroid Theory)是组合优化的一个分支。 矩阵胚 拟阵理论虽然并不是

2、因为贪心算法而引入，但是却是贪心算法的强力辅助。 拟阵结构的判断并不复杂，结论也十分简单： 在问题模型满足拟阵结构的情况下，贪心策略总是能够得到最优解,拟阵,拟阵的概念 拟阵的基本性质 拟阵结构基础上贪心策略的正确性拟阵的简单应用 开篇：最大权极大线性无关组问题 最小生成树Kruscal算法的正确性证明 其他题目,拟阵的概念,定义1 子集系统的优化问题 设= 1 , 2 , 是个不同元素的集合，对每一个元素 有一个权函数( )，一个集合的权为()，定义为 ()= () 设是有限集的一个子集族，则求解max()|称为子集系统的优化问题. 开篇的向量组子集优化问题 背包，最小生成树,拟阵的概念,定

3、义2 拟阵 一个拟阵（Matroid）是一个有序对=(,)，其中是一个非空有限集合，2，他们满足一下公理 若 ，则 若 1 , 2 且| 1 |=|，则称是的一个极大独立子集。 定理1 拟阵=(,)的所有极大独立子集都有相同的大小。 证明提要：采用反证法。若结论不成立，则与拟阵的第三条性质独立扩充公理矛盾,拟阵的性质,定理2 拟阵=(,)是一个加权矩阵，权函数为，且已按权排成非升顺序。设是第一个使得独立的元素。如果这样的元素存在，则存在一个包含的的最大权独立子集。 证明提要： 假设是任意非空的最优子集，且。 对任意，有()()。（因为已排序） 构造集合A=x，则可以反复地在中找出新元素加入直到

4、|=|，且保持的独立性。（独立扩充定理） 因此存在某个，使得 = ()。 () = ()()+()()。,拟阵的性质,定理3 设x是对于加权拟阵=(,)由贪心算法所选择的S的第一个元素，则剩下的寻找包含x的一个极大权独立子集问题，可以归结为求加权拟阵 = , 的一个极大权独立子集的问题。其中 = 且 , =| 且 证明提要： 首先证明在 = , 中求得任意最优解X均满足 其次证明在=(,)中包含的最优解一定可以表示为，其中是 的最优解,贪心算法,定理3给出了一个正确的递归算法来解决该问题。 容易证明定理3中递归算法每次挑选出的元素是不增的，否则与S已排序的条件矛盾。 通过定理2不难发现，定理3

5、的递归算法中第+1次挑选出的元素 满足 1 , 2 , 。即第次转化模型的到的拟阵 +1 ( +1 , +1 )中有 +1 = 且 ,y = 且 1 , 2 , , +1 = 且 =| 1 , 2 , 且 1 , 2 , ,贪心算法,算法 , 算法 , 的正确性已经显而易见了。现在我们只需证明在递归算法中第个选择的元素 ，就是 , 算法中选择的第个元素 。 显然， 1 = 1 现假设当=时有 = ，1 当 = + 1，考虑所有 ， +1 显然 ，不满足 +1 +1 , +1 在定理3中贪心算法的条件，从而 m+1 而 m+1 满足条件。从而 m+1 = m+1 因此由数学归纳法证明了 , 的正

6、确性。,拟阵的简单应用,任务调度问题 现有一台计算机需要完成个任务，每个任务要花费计算机一个单位时间。第个任务必须在时刻 之前完成，否则会产生 的损失。计算机每一个单位时间只能执行一个任务。初始时刻为0。 求最小损失 问题转化：求一组可以完成的任务使得罚款总和最大 可以完成的一组任务特点：在时刻前必须完成的任务数量需要小于 构建该问题对应的子集系统优化问题 很容易证明该子集系统具有拟阵结构,拟阵的简单应用,开篇问题最大权极大线性无关组 设= 1 , 2 , 是维向量的个向量集合，是由线性无关向量所组成的集合。为的权函数，且对于子集，记()= () 。 求使得且 = max () 。构造二元组=

7、(, )。 设I， 。显然 也线性无关，从而 设 1 , 2 且| 1 | 2 |， 2 线性无关，故必然存在 2 ，使得 1 不能线性表出。从而 1 。 综上=(, )是拟阵。c是拟阵=(, )的权函数。因此可以使用贪心解决此问题。,拟阵的简单应用,异或和最大问题 给出n个数，求从中选出尽可能多的数满足： 这些数之中任意多个的异或和不为0 这些数的和最大将所有数转化为二进制，以每一位作为一维，那么原问题就转化成了模二剩余类整数域上的最大权极大线性无关组问题。 直接贪心即可。,拟阵的简单应用,最小生成树问题Kruscal算法 该算法是经典贪心算法。 我们通过将最小生成树问题转化为一个子集系统的

8、优化问题，并证明该系统具有拟阵结构，从而证明Kruscal算法的正确性。已知=(,)，构造二元组=(,)，其中=， 2 ，且 =|中的边不构成回路 只需证明=(,)是一个拟阵,拟阵的简单应用,设I， ，证明 显然，边集I不构成回路，其子集也不构成回路。 设 1 , 2 且| 1 | 2 |，证明 2 1 ，使得 1 对于=(,)的任一极大独立子集都有|=|1 设 1 ， 2 分别导出图 1 ， 2 。 1 2 1，从而图 1 不连通。用()表示图的连通分量个数，由于 1 ， 2 中均没有回路，故( 1 )( 2 )。 因此 2 1 ，使得所关联的两个顶点在 1 的不同连通分量中。 从而 1 综上， M= , 是拟阵。从而Kruscal的贪心是正确的。,附注,应用拟阵的题目虽然并不常见，但却是某些贪心问题强力解法。其独立扩充公理往往成为证明模型符合拟阵条件的关键。 本文通过介绍拟阵的基本概念和简单应用来帮助大家初步接触拟阵，认识拟阵。而整套拟阵理论更加复杂和深奥，也更加优美。希望本文能过起到抛砖引玉的作用。参考文献 孙贺 程序设计中的组合数学相关习题 1041,谢谢观赏！,