Lecture-11-贪心算法的理论基础PPT学习课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,第,4,章 贪心算法,1,4.8,贪心算法的基础理论,1.,拟阵,2.,帯权拟阵的贪心算法,3.,任务时间表问题,本讲主要内容：,2,4.8,贪心算法的理论基础,借助于,拟阵,1,（,Matroid,）工具，可建立关于贪心算法的较一般的理论。,线性代数中有如下两条性质：,（,1,）如果,X,x,1,x,2,x,k,是一个线性无关向量组，则对,X,的任意子集,X,也是线性无关的。,（,2,）如果,X,x,1,x,2,x,r,和,Y,y,1,y,2,y,m,是两个线性无关向量组且,mr,，则必存在一个,y,i,Y,，使得,X,y,i,是一个线性无关向量组。,1935,年，,Whitney,把以上两条性质进行了抽象推广，提出了拟阵概念。,1,赖虹建,.,拟阵论,M.,北京,:,高等教育出版社，,2002,年,7,月,3,4.8,贪心算法的理论基础,1.,拟阵,独立公理集系统,将拟阵,M,定义为满足下面,3,个条件的有序对,(S,I),(1)S,是非空有限集。,(2)I,是,S,的一类具有,遗传性质,的,独立,1,子集族，即若,B,I,，则,B,是,S,的独立子集，且,B,的任意子集也都是,S,的独立子集,(,即该子集属于,I),。空集,必为,I,的成员。,(3)I,满足,交换性质,，即若,A,I,B,I,且,|A|B|,，则存在某一元素,x,B-A,，使得,Ax,I,。,1:,此处的独立子集是线性无关,(,或线性独立,),概念的推广，代表,I,的入集条件,4,4.8,贪心算法的理论基础,例,1,：,如非空集合,S,的子集,K,的幂集,I=(K),(S,I),是否为拟阵？,例,2,：,无向图,G=(V,E),的图拟阵：，其中,S,G,定义为图,G,的边集,E,，,I,G,定义为,S,G,的无循环边集族，,A,I,G,当且仅当,A,构成图,G,的森林,*,。,注,*,：,即,I,G,是图,G,的无环支撑（生成）子图集合。,支撑子图（生成子图）：包含图,G,所有顶点,的子图。,5,4.8,贪心算法的理论基础,证明：满足拟阵,(S,I),的,3,个条件。,(1),因为,S,G,为图,G,的边集，显然非空；,(2),由于从,S,G,的一个无循环边集中去掉若干条边不会产生循环，即森林的子集还是森林，因此,S,G,的无循环边集族,I,G,具有遗传性质。,6,4.8,贪心算法的理论基础,(3),设,A,和,B,是图,G,的两个森林，且,|B|,|A|,，即,B,的边比,A,多。由于图,G,中有,k,条边的森林恰由,|V|-k,棵树组成，因此,B,中的树比,A,中的少。很显然，,B,中至少存在一棵树,T,，它的顶点分别在森林,A,的两棵树中,。由于,T,是连通的，故,T,中必有一条边,(u,v),满足,u,v,分别在,A,的两棵树中。因此将,(u,v),加入,A,不会产生循环。由此得出,I,G,满足,交换性质,，即若,A,I,B,I,且,|A|0,，则称拟阵,M,为,带权拟阵,。依此权函数，,S,的任一子集,A,的权定义为 。,9,4.8,贪心算法的理论基础,3.,关于带权拟阵的贪心算法,许多用贪心算法求解的问题可以表示为求带权拟阵的,最大权独立子集问题,。,给定带权拟阵,M=(S,I),，确定,S,的独立子集,A,I,使得,W(A),达到最大。这种使,W(A),最大的独立子集,A,称为拟阵,M,的,最优子集,。,由于,S,中任一元素,x,的权,W(x),是正的，因此，,最优子集,也一定是极大独立子集,(,不存在可扩展元素,),。,10,4.8,贪心算法的理论基础,例如，,最小生成树问题可以表示为确定带权拟阵,M,G,的最优子集问题。求带权拟阵的最优子集,A,的算法可用于解最小生成树问题。,带权拟阵最优子集,的贪心算法框架如下：,输入,：具有正权函数,W,的带权拟阵,M=(S,I),输出,：,M,的最优子集,A,。,11,4.8,贪心算法的理论基础,Set,greedy,(M,W),A=,;,将,S,中元素依权值,W,（大者优先）组成优先队列；,while(S!=,),S.removeMax(x);,if(Ax,I)A=Ax;,return A,12,4.8,贪心算法的理论基础,算法,Greedy,的时间复杂度分析,计算时间由两部分组成：,(1),设,n,|S|,。将,S,中的元素依照其权值大小组成一个优先队列，并对其进行,n,次,removeMax,运算，需要,O(n,n),的计算时间。,(2),如果检查,Ax,是否独立需要,O(f(n),的计算时间，则对,S,中元素检查一遍共需,O(nf(n),。,算法的计算时间复杂性为,。,13,4.8,贪心算法的理论基础,【,引理,4.2】,拟阵的贪心选择性质,设,M=(S,I),是具有正权函数,W,的带权拟阵，且,S,中元素依权值从大到小排列。又设,x,S,是,S,中第一个使得,x,是独立子集的元素，,则存在,S,的最优子集,A,使得,x,A,。,14,4.8,贪心算法的理论基础,证明：若不存在,x,S,，使得,x,是独立子集，则引理是平凡的。,设,B,是一个非空的最优子集,。由于,B,I,，且,I,具有遗传性，故,B,中所有单个元素子集,y,均为独立子集,(,满足解约束,),。又由于,x,是,S,中的第一个单元素独立子集，故对任意的,y,B,，均有：,W(x)W(y),。,(1),若,x,B,，则只要令,A=B,，定理得证；,(2),若,x,B,，我们按如下方法,构造包含元素,x,的最优子集,A,。,15,4.8,贪心算法的理论基础,(a),首先，设,A=x,，此时,A,是一个独立子集。若,|B|=|A|=1,，则定理得证。,(b),反复利用拟阵,M,的交换性质，从,B,中选择一个新元素加入,A,中并保持,A,的独立性，直到,|B|=|A|,。此时必有一元素,y,B,且,y,A,，使得,A=B-yx,，且满足：,W(A)=W(B)-W(y)+W(x)W(B),由于,B,是一个最优子集，所以,W(B)W(A),。因此,W(A)=W(B),，即,A,也是一个最优子集，且,x,A,。,16,4.8,贪心算法的理论基础,首个,x,选出之前被舍弃元素的处理,可以证明，这些被舍弃的元素，以后也永远不可能用于构造最优子集,。,17,4.8,贪心算法的理论基础,【,引理,4.3】,：,设,M=(S,I),是拟阵。若,S,中元素,x,不是空集,的可扩展元素，则,x,也不可能是,S,中任一独立子集,A,的可扩展元素,证明：,用反证法,。设,x,S,不是,的一个可扩展元素，但它是,S,的某独立子集,A,的一个可扩展元素，即,Ax,I,，由,I,的遗传性可知,x,是独立的。这与,x,不是空集,的一个可扩展元素相矛盾。,由引理,4.3,可知，算法,Greedy,在初始化独立子集,A,时舍弃的元素可以永远舍弃。,18,4.8,贪心算法的理论基础,【,引理,4.4】,拟阵的最优子结构性质,设,x,是求带权拟阵,M=(S,I),最优子集的贪心算法,greedy,所选择的,S,中的,第一个,元素。那么，原问题可简化为,求带权拟阵,M,=(S,I,),的最优子集,问题，其中：,S,=y|y,S,且,x,y,I,，,即,y,是,x,的可扩展元素,I,=B|B,S-x,且,Bx,I,M,的,权函数,是,M,的权函数在,S,上的限制,(,称,M,为,M,关于元素,x,的,收缩,),。,19,4.8,贪心算法的理论基础,证明：,(P136),(1),若,A,是,M,的包含元素,x,的最大独立子集，则,A,=A-x,是,M,的一个独立子集,。,反之，,M,的任一独立子集,A,产生,M,的一个独立子集,A=A,x,（,均可由,M,的定义得到,）。,(2),在这两种情形下均有：,W(A)=W(A,)+W(x),因此,M,的包含元素,x,的,最优子集,包含,M,的一个,最优子集,，反之亦然。,20,4.8,贪心算法的理论基础,【,定理,4.5】,带权拟阵贪心算法的正确性,设,M,(S,I),是具有正权函数,W,的带权拟阵，算法,greedy,返回,M,的最优子集,证明：,(P137),(1),由,【,引理,4.2】,可知，如第一次加入,A,的元素是,x,，,则必存在包含元素,x,的一个最优子集,。因此，,Greedy,第一次选择是正确的,。,(2),由,【,引理,4.3】,可知，选择,x,时被舍弃的元素不可能被再选中，即它们不可能是任一最优子集中的元素。因此，,这些元素可以永远舍弃,。,21,4.8,贪心算法的理论基础,(3),由,【,引理,4.4】,可知，,Greedy,选择了元素,x,后，原问题简化为求拟阵,M,的,最优子集,问题。,由于对,M,=(S,I,),中的任一独立子集,B,I,，均有,Bx,在,M,中是独立的（,由,M,的定义可知,）。因此，,Greedy,选择了元素,x,后，后续求解将演变为求拟阵,M,=(S,I,),的,最优子集,问题。,由归纳法可知：,其后继步骤求出,M,的一个最优子集，从而算法,Greedy,最终求出的是,M,的一个最优子集。,22,4.8,贪心算法的理论基础,具有,截止时间,和,误时惩罚,的单位时间任务的调度时间表问题描述如下：,(1)n,个单位时间任务的集合,S=1,2,n,；,(2),任务,i,的截止时间,d,i,1in,1d,i,n,，即要求任务,i,在时间,d,i,之前结束；,(3),任务,i,的误时惩罚,w,i,1in,即任务,i,未在规定时间,d,i,之前结束将招致,w,i,惩罚；若按时完成则无惩罚。,任务时间表问题,要求确定,S,的一个时间表（最优时间表）使得总误时惩罚达到最小。,4.,例子：任务时间表问题,(,带期限作业调度问题,),23,4.8,贪心算法的理论基础,用,带权拟阵的贪心算法,求解的基本思路如下,：,(1),首先，将,S,的任一时间表调整成,及时优先形式,(,截止时间之前完成的任务,),，即其中所有及时任务先于误时任务，而不会影响原时间表中各任务的及时或误时性质。,(2),然后，再进一步调整及时任务的次序，,将,S,的时间表调整成为,规范形式,，即其中,及时任务依其截止时间的非减序排列,。,(3),任务时间表问题等价于确定最优及时任务子集,A,的问题,。,24,4.8,贪心算法的理论基础,一旦确定了最优及时任务子集,A,，将,A,中各任务依其截止时间的非减序列出，然后再以任意次序列出误时任务,(S-A,中的任务,),，由此产生,S,的一个规范的最优时间表,。,25,4.8,贪心算法的理论基础,下面证明“及时任务子集族”构成拟阵,设：,N,t,(A),是任务子集,A,中所有,截止时间,是,t,或小于,t,的,任务数,，,t=1,2,n,。,则：,任务子集,A,的独立性条件,(,即解约束条件：,A,中的任务都能及时完成,),具有以下性质：,【,引理,4.6】,对于,S,的任一任务子集,A,，下面的各命题是等价的。,(1),任务子集,A,是独立子集。,(2),对于,t=1,2,n,，,N,t,(A)t,。,(3),若,A,中任务依其截止时间非减序排列，则,A,中所有任务都是及时的。,26,4.8,贪心算法的理论基础,主要证明过程：,(1)(2),：假设任务子集,A,是独立的，且存在某个,t,使得,N,t,(A)t,则,A,中有多于,t,个任务要在时间,t,之前完成，这显然是不可能的。故,A,中必有误时任务，这与,A,是独立任务子集相矛盾。因此，对所有,t=1,2,n,，,N,t,(A)t,；,(2)(3),：将,A,中任务按截止时间的非减序排列，则,(2),中不等式意味着排序后,A,中截止时间为,t,的任务前面，需要调度的任务数是少于,t,的。故排序后,A,中所有任务都是及时的；,27,4.8,贪心算法的理论基础,最优任务时间表问题：,要求使总误时惩罚达到最小，,这等价于使任务时间表中的及时任务的惩罚值之和达到最大,。,该问题可用带权拟阵的贪心算法求解。,28,4.8,贪心算法的理论基础,【,定理,4.7】,设,S,是带有截止时间的单位时间任务集，,I,是,S,的所有独立,(,及时,),任务子集构成的集合。,则有序对,(S,I),是拟阵,。,证明：,(1),首先，独立任务集的子集显然也是独立子集。故,I,满足遗传性质。,(2),设,A,、,B,为独立任务子集且,|B|A|,，下面证明,(S,I),满足交换性质。,29,4.8,贪心算法的理论基础,(a),设从时刻,1,开始，,最后一次,出现,N,t,(B)N,t,(A),的,t,值为,k,即,k=maxt|N,t,(B)N,t,(A),1tn,。由于,N,n,(B)=|B|,N,n,(A)=|A|,而,|B|A|,即,N,n,(B)N,n,(A),。因此必有这样的,k,，符合,kN,j,(A),。,(b),取,x,B-A,，,且,x,的截止时间为,k+1,。令,A,=Ax,。,下面证明,A,是独立的,30,4.8,贪心算法的理论基础,首先，由于,A,是独立的，故对于,1tk,有：,N,t,(A,)=N,t,(A)t,。,又由于,B,是独立的，故对,k0 do /,找根,3 j=PARENT(j),4repeat,5k=i,6while k,j do /,压缩由,i,到根,j,的结点,7 i=PARENT(k),8 PARENT(k)=j,9 k=i,10repeat,11return(j),12end FIND,40,算法,procedure UNION(i,j),/,使用加权规则合并根为,i,和,j,的两个集合，,i,j,/,PARENT(i),COUNT(i),，,PARENT(j),COUNT(j),1integer i,j,x,2x=PARENT(i)+PARENT(j),3 if PARENT(i)PARENT(j),4then PARENT(i)=j /,i,的结点少,5 PARENT(j)=x,6else PARENT(j),i /,j,的结点少,7 PARENT(i),x,8 endif,9end UNION,41,例,2,：,设,n=7，(p,1,p,7,)=(35,30,25,20,15,10,5),和(,d,1,d,7,)(4,2,4,3,4,8,3)。,利用算法,FJS,求解上述作业集的最优解。,最优解：,J1，2，3，4，6,*余祥宣,等,.,计算机算法基础,M.2,版,.,武汉,:,华中理工大学出版社,2000.70,75,42,将时间片,i-1,i,表示为,i,，其中,1ib,，,b,minn,maxd,i,。,管理时间片的基本方法是：给每个时间片设立一个标志指针,F,，指向不大于它并最接近它的空闲时间片，如果没有满足条件的空闲时间片，则置,0,。,显然初始时，每个时间片的标志指针将指向它自己，在被分配后，该标志指针将指向前面的某个空闲时间片。,随着空闲时间片不断被分配，被占用的时间片将逐步形成一些连续的区域,(,集合,i-1,i,i,i+1,j-1,j),，其中每个标志指针都指向期限小于它们的同一个最近的空闲时间片，即,F(i)=F(i+1)=F(j)=k,。现在要调度期限为,d,的作业，就是要查找,F(d),，如果,F(d)=k,，则,k,就是最接近的空闲时间片，,k,分配给作业后，,需要将,F(d),的值修改为新的最接近空闲时间片,(,如何修改？,F(d),F(k-1),。下面介绍基于,UNION-FIND,来实现的作业调度算法。,43,初始化树：,Pi -1,初始化：,Fii,LFIND(F4-1)；UNION(3,4),F4F3,LFIND(F3-1)；UNION(1,3),F3F1,LFIND(F1-1)；UNION(0,1),jFIND(min(n,D(i),if F(j)0 then kk+1；J(k)i,LFIND(F(j)-1)；UNION(L,j),F(j)F(L),endif,