1、概览概览 第一部分：拟阵的基本概念 第二部分：拟阵的最优化问题 第三部分 ：一个任务调度问题 第四部分：拟阵实例 拓展部分：Shannon开关游戏第一部分：拟阵的概念第一部分：拟阵的概念拟阵拟阵是一个二元组二元组),(LSM S1、S是一个有限有限集。2、L是个以集合作为元素的集合,且它的元素必须是S的子集L3、遗传性遗传性：对任意任意 LB任意任意 BA有LALBAA4、交换性交换性：对任意任意,LBLABA 存在一个 ABx,使 LxALBAxxA定义定义拟阵拟阵是一个二元组二元组),(LSM，满足:1、S是一个有限有限集。2、L是由S的一些一些子集组成的有限非空有限非空集3、遗传性遗传性
2、：对任意任意 LB，任意任意 BA有LA4、交换性交换性：对任意任意,LBLABA 存在一个 ABx,使 LxASLSLUAX定义定义对于 SU 如果 LU 那么称U为独立集独立集 对于独立集A,若存在 ASx满足 LxA则称A为可扩展可扩展的不可扩展的独立集称为极大独立集极大独立集 满足此条件的x称为A的一个可扩展元素定理定理:拟阵的极大独立集大小相同拟阵的极大独立集大小相同 BA根据交换性必然可以用B中一元素扩展A实例实例:图拟阵图拟阵考虑对于无向图 EVG,定义:,LSM 1、S是边集E2、组成的图无环且xExxL:无环的边集的子集必然无环,故满足遗传性此连通分量中必然存在一条边，放入A
3、中不形成环所以B中存在一个连通分量,该分量在A中不连通如果边集A的边数比边集B少则A形成的连通分量数目比B多该边显然属于B-A。交换性成立M是拟阵，称为图拟阵AB第二部分：拟阵上的最优化问题第二部分：拟阵上的最优化问题问题提出问题提出LSM,UxxwUw对于拟阵S的元素x有一个正整数权值w(x)S的任意子集U的权值目标:求权值最大独立集。贪心算法贪心算法Greedy(M,w)A:=空集 根据w按递减顺序对S排序 for 每个 Sx根据权 xw的递减顺序 doif(LxA)then xAA:return A时间复杂度时间复杂度排序nnlog若判断需 nf总复杂度 nfnnnlog贪心 n次判断正
4、确性证明正确性证明 只需证明在算法的每一步A都是某个最优解的子集，那么当算法结束时A就是一个最优解 运用归纳思想 归纳基础:初始时A为空,满足要求 归纳:只需证明一个最优解的子集A经过一次循环后仍满足要求.TATA=AxX能使A扩展的最大元素yAXT=T-y+xw(y)w(x)w(T)w(T)T 第三部分第三部分 任务调度问题任务调度问题问题提出问题提出S:调度:012345给定一个单位时间任务的集合SS有n个任务1,2,n对S的一个调度调度规定了各任务执行的顺序。该调度第i个任务开始于时刻i-1,结束于时刻i表示第i个任务的截止时刻问题提出问题提出:idnddd,.,21ndi1nwww,.
5、,21iw n个整数整数(),表示第i个任务的罚款n个正整数调度:0123452313:iw9768罚款:6+8=14iw 如果任务i的结束时刻超过截止时刻则要交付的罚款。求一个调度，使得罚款最少。id分析分析 考虑这么一个问题：对于S的子集A，是否存在调度方案使A中的任务都被完成。将A按任务的截止时刻从小到大排序作为调度方案,如果按此调度无法全部完成A的任务，则其他任意调度方案都无法完成。调度:012345id124 3 拟阵结构拟阵结构 对于给定的任务集合A，能够有效地判断这些任务能否全部完成 能全部完成的任务集合A称为可行的LSM,是可行的的子集且是xSxxL:定义S就是所有任务的集合第
6、四部分：拟阵实例第四部分：拟阵实例线性拟阵线性拟阵T:SU线性无关线性无关1327图拟阵和线性拟阵图拟阵和线性拟阵 G=(V,E)451234511100020-10-103-1001040000150000-1600100700-100关联矩阵关联矩阵6图拟阵和线性拟阵图拟阵和线性拟阵线性拟阵线性拟阵图拟阵图拟阵匹配拟阵匹配拟阵EVG,),(LSM 对于无向图定义S的子集A是独立集当且仅当 S=VA中的点能被该图的一个匹配覆盖拓展部分拓展部分:Shannon开关游戏浅谈开关游戏浅谈总结总结拟阵拟阵交换性交换性遗传性遗传性本本构造构造反证反证 相辅相成相辅相成总结总结最小生成树问题最小生成树问题任务调度问题任务调度问题线性无关线性无关共性共性拟阵拟阵拟阵很美拟阵很美谢谢最小化问题转化为最大化问题最小化问题转化为最大化问题最小化问题最大化问题(12-3 19 7 5 8)(-12 3-19-7-5-8)+19+1(8 23 1 13 15 12)
