,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,对拟阵的初步研究,对拟阵的初步研究,1,概览,第一部分：拟阵的基本概念,第二部分：拟阵的最优化问题,第三部分 ：一个任务调度问题,第四部分：拟阵实例,拓展部分：,Shannon,开关游戏,概览第一部分：拟阵的基本概念,2,第一部分：拟阵的概念,第一部分：拟阵的概念,3,拟阵,是一个,二元组,S,1,、,S,是一个,有限,集。,2,、,L,是个以集合作为元素的集合,且它的元素必须是,S,的子集,L,拟阵是一个二元组 S1、S是一个有限集。2、L是个以集合作为,4,3,、,遗传性,：对,任意,任意,有,L,B,A,A,3、遗传性：对任意 任意 有LBAA,5,4,、,交换性,：对,任意,存在一个,使,L,B,Ax,x,A,4、交换性：对任意 存在一个,使 LBAxxA,6,定义,拟阵,是一个,二元组,，满足,:,1,、,S,是一个,有限,集。,2,、,L,是由,S,的,一些,子集组成的,有限非空,集,3,、,遗传性,：对,任意,，,任意,有,4,、,交换性,：对,任意,存在一个,使,定义拟阵是一个二元组，满足:1、S是一个有限集。2、L是,7,S,L,S,L,U,A,X,定义,对于,如果,那么称,U,为,独立集,对于独立集,A,若存在,满足,则称,A,为,可扩展,的,不可扩展的独立集称为,极大独立集,满足此条件的,x,称为,A,的一个可扩展元素,SLSLUAX定义对于 如果 那么称U为独立集 对于独立集A,8,定理,:,拟阵的极大独立集大小相同,B,A,根据交换性,必然可以用,B,中一元素扩展,A,定理:拟阵的极大独立集大小相同 BA根据交换性,9,实例,:,图拟阵,考虑对于无向图,定义,1,、,S,是边集,E,2,、,无环的边集的子集必然无环,故满足遗传性,实例:图拟阵考虑对于无向图 定义 1、S是边集E2、无环的边,10,此连通分量中必然存在一条边，放入,A,中不形成环,所以,B,中存在一个连通分量,该分量在,A,中不连通,如果边集,A,的边数比边集,B,少,则,A,形成的连通分量数目比,B,多,该边显然属于,B-A,。交换性成立,M,是拟阵，称为图拟阵,A,B,此连通分量中必然存在一条边，放入A中不形成环所以B中存在一个,11,第二部分：拟阵上的最优化问题,第二部分：拟阵上的最优化问题,12,问题提出,对于拟阵,S,的元素,x,有一个正整数权值,w(x),S,的任意子集,U,的权值,目标,:,求权值最大独立集。,问题提出对于拟阵S的元素x有一个正整数权值w(x)S的任意子,13,贪心算法,Greedy(M,w),A:=,空集,根据,w,按递减顺序对,S,排序,for,每个,根据权,的递减顺序,do,if(,),then,return A,贪心算法Greedy(M,w)for 每个 根据权 的递减顺,14,时间复杂度,排序,若判断需,总复杂度,贪心,次判断,时间复杂度排序若判断需总复杂度贪心次判断,15,正确性证明,只需证明在算法的每一步,A,都是某个最优解的子集，那么当算法结束时,A,就是一个最优解,运用归纳思想,归纳基础,:,初始时,A,为空,满足要求,归纳,:,只需证明一个最优解的子集,A,经过一次循环后仍满足要求,.,正确性证明只需证明在算法的每一步A都是某个最优解的子集，那么,16,T,A,T,A,=Ax,X,能使,A,扩展,的最大元素,y,A,X,T=T-y+x,w(y),w(x),w(T),w(T),T,TATA=AxX能使A扩展yAXT=T-y+,17,第三部分 任务调度问题,第三部分 任务调度问题,18,问题提出,S:,调度,:,0,1,2,3,4,5,给定一个单位时间任务的集合,S,S,有,n,个任务,1,2,n,对,S,的一个,调度,规定了各任务执行的顺序。,该调度第,i,个任务开始于时刻,i-1,结束于时刻,i,问题提出S:调度:012345给定一个单位时间任务的集合S对,19,表示第,i,个任务的截止时刻,问题提出,n,个,整数,(,),表示第,i,个任务的罚款,n,个正整数,调度,:,0,1,2,3,4,5,2,3,1,3,9,7,6,8,罚款,:6+8=14,如果任务,i,的结束时刻超过截止时刻,则要交付,的罚款。,求一个调度，使得罚款最少。,表示第i个任务的截止时刻问题提出 n个整数(),20,分析,考虑这么一个问题：对于,S,的子集,A,，是否存在调度方案使,A,中的任务都被完成。,将,A,按任务的截止时刻从小到大排序作为调度方案,如果按此调度无法全部完成,A,的任务，则其他任意调度方案都无法完成。,调度,:,0,1,2,3,4,5,1,2,4,3,分析考虑这么一个问题：对于S的子集A，是否存在调度方案使A中,21,拟阵结构,对于给定的任务集合,A,，能够有效地判断这些任务能否全部完成,能全部完成的任务集合,A,称为可行的,定义,S,就是所有任务的集合,拟阵结构对于给定的任务集合A，能够有效地判断这些任务能否全部,22,第四部分：拟阵实例,第四部分：拟阵实例,23,线性拟阵,T:,S,U,线性无关,线性拟阵T:SU线性无关,24,1,3,2,7,图拟阵和线性拟阵,G=(V,E),4,5,1,2,3,4,5,1,1,1,0,0,0,2,0,-1,0,-1,0,3,-1,0,0,1,0,4,0,0,0,0,1,5,0,0,0,0,-1,6,0,0,1,0,0,7,0,0,-1,0,0,关联矩阵,6,1327图拟阵和线性拟阵 G=(V,E)4512345111,25,图拟阵和线性拟阵,线性拟阵,图拟阵,图拟阵和线性拟阵线性拟阵图拟阵,26,匹配拟阵,对于无向图,定义,S,的子集,A,是独立集,当且仅当,S=V,A,中的点能被该图的一个匹配覆盖,匹配拟阵对于无向图定义S的子集A是独立集当且仅当 S=VA中,27,拓展部分,:Shannon,开关游戏浅谈,拓展部分:Shannon开关游戏浅谈,28,总结,拟阵,交换性,遗传性,本,构造,反证,相辅相成,总结拟阵交换性遗传性本构造反证 相辅相成,29,总结,最小生成树问题,任务调度问题,线性无关,共性,拟阵,拟阵很美,总结最小生成树问题任务调度问题线性无关共性拟阵拟阵很美,30,谢谢,谢谢,31,最小化问题转化为最大化问题,最小化问题,最大化问题,(12-3 19 7 5 8),(-12 3-19-7-5-8),+,19,+1,(8 23 1 13 15 12),最小化问题转化为最大化问题最小化问题最大化问题(12-3,32,