对拟阵的初步研究

《对拟阵的初步研究》由会员分享，可在线阅读，更多相关《对拟阵的初步研究（32页珍藏版）》请在金锄头文库上搜索。

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

2、换性交换性：对任意任意 存在一个 ,使 SLSLUAX定义定义对于 如果 那么称U为独立集独立集 对于独立集A,若存在 满足 则称A为可扩展可扩展的不可扩展的独立集称为极大独立集极大独立集 满足此条件的x称为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 () then return A时间复杂度时间复杂度排序若判断需总复杂度贪心次判断正确性证明正确性证明只需证明在算法的每一步A都是某个最优解的子集，那么当算法结束时A就是一个最优解运用归纳思想归纳基础:初始时A为空,满足要求归纳:只需证明一个最优解的子集A经过一次循环后仍满足要求.TATA =A xX能使A扩展的最大元素yAXT =T-y+xw(y) w(x)w(T ) w(T)T 第三部分

4、第三部分 任务调度问题任务调度问题问题提出问题提出S:调度:012345给定一个单位时间任务的集合SS有n个任务1,2,n对S的一个调度调度规定了各任务执行的顺序。该调度第i个任务开始于时刻i-1,结束于时刻i表示第i个任务的截止时刻问题提出问题提出 n个整数整数 (),表示第i个任务的罚款n个正整数调度:01234523139768罚款:6+8=14 如果任务i的结束时刻超过截止时刻则要交付的罚款。求一个调度，使得罚款最少。分析分析考虑这么一个问题：对于S的子集A，是否存在调度方案使A中的任务都被完成。将A按任务的截止时刻从小到大排序作为调度方案,如果按此调度无法全部完成A的任务，则其他任意

5、调度方案都无法完成。调度:012345124 3 拟阵结构拟阵结构对于给定的任务集合A，能够有效地判断这些任务能否全部完成能全部完成的任务集合A称为可行的 定义S就是所有任务的集合第四部分：拟阵实例第四部分：拟阵实例线性拟阵线性拟阵T:SU线线性性无无关关1327图拟阵和线性拟阵图拟阵和线性拟阵 G=(V,E)451234511100020-10-103-1001040000150000-1600100700-100关联矩阵关联矩阵6图拟阵和线性拟阵图拟阵和线性拟阵线性拟阵线性拟阵图拟阵图拟阵拓展部分拓展部分:Shannon开关游戏浅谈开关游戏浅谈总结总结拟阵交交换性性遗传性性本本构造构造反反证 相相辅相成相成总结总结最小生成最小生成树问题任任务调度度问题线性无关性无关共性共性拟阵拟阵很美很美谢谢最小化问题转化为最大化问题最小化问题转化为最大化问题最小化问题最大化问题(12 -3 19 7 5 8)(-12 3 -19 -7 -5 -8) +19+1(8 23 1 13 15 12)