算法合集之《对拟阵的初步研究》

《算法合集之《对拟阵的初步研究》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、对拟阵的初步研究浙江省杭州第二中学刘雨辰概览第一部分：拟阵的基本概念第二部分：拟阵的最优化问题第三部分：一个任务调度问题第四部分：拟阵实例拓展部分：Shannon开关游戏第一部分：拟阵的概念拟阵是一个二元组S1、S是一个有限集。2、L是个以集合作为元素的集合,且它的元素必须是S的子集L3、遗传性：对任意任意有LBAA4、交换性：对任意存在一个,使LBA∪{x}xA定义拟阵是一个二元组，满足:1、S是一个有限集。2、L是由S的一些子集组成的有限非空集3、遗传性：对任意，任意有4、交换性：对任意存在一个,使

2、SLSLUAX定义对于如果那么称U为独立集对于独立集A,若存在满足则称A为可扩展的不可扩展的独立集称为极大独立集满足此条件的x称为A的一个可扩展元素定理:拟阵的极大独立集大小相同BA<根据交换性必然可以用B中一元素扩展A实例:图拟阵考虑对于无向图定义1、S是边集E2、无环的边集的子集必然无环,故满足遗传性此连通分量中必然存在一条边，放入A中不形成环所以B中存在一个连通分量,该分量在A中不连通如果边集A的边数比边集B少则A形成的连通分量数目比B多该边显然属于B-A。交换性成立M是拟阵，称为图拟阵AB第二部

3、分：拟阵上的最优化问题问题提出对于拟阵S的元素x有一个正整数权值w(x)S的任意子集U的权值目标:求权值最大独立集。贪心算法Greedy(M,w)A:=空集根据w按递减顺序对S排序for每个根据权的递减顺序doif()thenreturnA时间复杂度排序若判断需总复杂度贪心次判断正确性证明只需证明在算法的每一步A都是某个最优解的子集，那么当算法结束时A就是一个最优解运用归纳思想归纳基础:初始时A为空,满足要求归纳:只需证明一个最优解的子集A经过一次循环后仍满足要求.TATA=A∪{x}X能使A扩展的最大

4、元素yAXT=T-{y}+{x}w(y)≤w(x)w(T)≥w(T)T′′′′′第三部分任务调度问题问题提出S:调度:012345给定一个单位时间任务的集合SS有n个任务1,2,…,n对S的一个调度规定了各任务执行的顺序。该调度第i个任务开始于时刻i-1,结束于时刻i表示第i个任务的截止时刻问题提出n个整数(),表示第i个任务的罚款n个正整数调度:01234523139768罚款:6+8=14如果任务i的结束时刻超过截止时刻则要交付的罚款。求一个调度，使得罚款最少。分析考虑这么一个问题：对于S的子集A，

5、是否存在调度方案使A中的任务都被完成。将A按任务的截止时刻从小到大排序作为调度方案,如果按此调度无法全部完成A的任务，则其他任意调度方案都无法完成。调度:0123451243拟阵结构对于给定的任务集合A，能够有效地判断这些任务能否全部完成能全部完成的任务集合A称为可行的定义S就是所有任务的集合第四部分：拟阵实例线性拟阵T:SU线性无关1327图拟阵和线性拟阵G=(V,E)451234511100020-10-103-1001040000150000-1600100700-100关联矩阵6图拟阵和线性拟阵

6、线性拟阵图拟阵匹配拟阵对于无向图定义S的子集A是独立集当且仅当S=VA中的点能被该图的一个匹配覆盖拓展部分:Shannon开关游戏浅谈总结拟阵交换性遗传性本构造反证相辅相成总结最小生成树问题任务调度问题线性无关共性拟阵拟阵很美谢谢最小化问题转化为最大化问题最小化问题最大化问题(12-319758)(-123-19-7-5-8)+19+1(8231131512)