《Lecture11贪心算法的理论基础-拟阵.ppt》由会员分享，可在线阅读，更多相关《Lecture11贪心算法的理论基础-拟阵.ppt（43页珍藏版）》请在三一办公上搜索。
1、1,第4章 贪心算法,4.8 贪心算法的基础理论1.拟阵2.帯权拟阵的贪心算法3.任务时间表问题,本讲主要内容：,2,4.8 贪心算法的理论基础,借助于拟阵1（Matroid）工具，可建立关于贪心算法的较一般的理论。线性代数中有如下两条性质：（1）如果Xx1,x2,xk是一个线性无关向量组，则对X的任意子集X也是线性无关的。（2）如果Xx1,x2,xr和Yy1,y2,ym是两个线性无关向量组且mr，则必存在一个yiY，使得Xyi是一个线性无关向量组。1935年，Whitney把以上两条性质进行了抽象推广，提出了拟阵概念。,1赖虹建.拟阵论M.北京:高等教育出版社，2002年7月,3,4.8 贪
2、心算法的理论基础,1.拟阵独立公理集系统将拟阵M定义为满足下面3个条件的有序对(S,I)(1)S是非空有限集。(2)I是S的一类具有遗传性质的独立1子集族，即若BI，则B是S的独立子集，且B的任意子集也都是S的独立子集(即该子集属于I)。空集必为I的成员。(3)I满足交换性质，即若AI,BI且|A|B|，则存在某一元素xB-A，使得AxI。1:此处的独立子集是线性无关(或线性独立)概念的推广，代表I的入集条件,4,4.8 贪心算法的理论基础,例1：如非空集合S的子集K的幂集I=(K),(S,I)是否为拟阵？例2：无向图G=(V,E)的图拟阵：，其中SG定义为图G的边集E，IG定义为SG的无循环
3、边集族，AIG 当且仅当A构成图G的森林*。,注*：即IG是图G的无环支撑（生成）子图集合。支撑子图（生成子图）：包含图G所有顶点的子图。,5,4.8 贪心算法的理论基础,证明：满足拟阵(S,I)的3个条件。(1)因为SG为图G的边集，显然非空；(2)由于从SG的一个无循环边集中去掉若干条边不会产生循环，即森林的子集还是森林，因此SG的无循环边集族IG具有遗传性质。,6,4.8 贪心算法的理论基础,(3)设A和B是图G的两个森林，且|B|A|，即B的边比A多。由于图G中有k条边的森林恰由|V|-k棵树组成，因此B中的树比A中的少。很显然，B中至少存在一棵树T，它的顶点分别在森林A的两棵树中。由
4、于T是连通的，故T中必有一条边(u,v)满足u,v分别在A的两棵树中。因此将(u,v)加入A不会产生循环。由此得出IG满足交换性质，即若AI,BI且|A|B|，则存在某一元素xB-A，使得AxI。,7,4.8 贪心算法的理论基础,2.拟阵的几个重要概念和性质【定义】：给定拟阵M=(S,I)，对于I中的独立子集A I，若S有一元素x A，使得将x加入A后仍保持独立性，即Ax I,则称x为A的可扩展元素。【定义】：当拟阵M中的独立子集A没有可扩展元素时，称A为极大独立子集，或拟阵的基。,8,4.8 贪心算法的理论基础,关于极大独立子集的性质【定理4.1】拟阵M中所有极大独立子集的势相同。这个定理可
5、以用反证法证明（P134）。【定义】若对拟阵M=(S,I)中的S指定权函数W，使得对于任意x S，有W(x)0，则称拟阵M为带权拟阵。依此权函数，S的任一子集A的权定义为。,9,4.8 贪心算法的理论基础,3.关于带权拟阵的贪心算法许多用贪心算法求解的问题可以表示为求带权拟阵的最大权独立子集问题。给定带权拟阵M=(S,I)，确定S的独立子集AI使得W(A)达到最大。这种使W(A)最大的独立子集A称为拟阵M的最优子集。由于S中任一元素x的权W(x)是正的，因此，最优子集也一定是极大独立子集(不存在可扩展元素)。,10,4.8 贪心算法的理论基础,例如，最小生成树问题可以表示为确定带权拟阵MG的最
6、优子集问题。求带权拟阵的最优子集A的算法可用于解最小生成树问题。带权拟阵最优子集的贪心算法框架如下：输入：具有正权函数W的带权拟阵M=(S,I)输出：M的最优子集A。,11,4.8 贪心算法的理论基础,Set greedy(M,W)A=;将S中元素依权值W（大者优先）组成优先队列；while(S!=)S.removeMax(x);if(AxI)A=Ax;return A,12,4.8 贪心算法的理论基础,算法Greedy的时间复杂度分析计算时间由两部分组成：(1)设n|S|。将S中的元素依照其权值大小组成一个优先队列，并对其进行n次removeMax运算，需要O(nn)的计算时间。(2)如果检
7、查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 贪心算法的理论基础,证明：若不存在xS，使得x是独立子集，则引理是平凡的。设B是一个非空的最优子集。由于BI，且I具有遗传性，故B中所有单个元素子集y均为独立子集(满足解约束)。又由于x是S中的第一个单元素独立子集，故对任意的y B，均有：W(x)W(y)。
8、(1)若xB，则只要令A=B，定理得证；(2)若xB，我们按如下方法构造包含元素x的最优子集A。,15,4.8 贪心算法的理论基础,(a)首先，设A=x，此时A是一个独立子集。若|B|=|A|=1，则定理得证。(b)反复利用拟阵M的交换性质，从B中选择一个新元素加入A中并保持A的独立性，直到|B|=|A|。此时必有一元素yB且yA，使得A=B-yx，且满足：W(A)=W(B)-W(y)+W(x)W(B)由于B是一个最优子集，所以W(B)W(A)。因此W(A)=W(B)，即A也是一个最优子集，且xA。,16,4.8 贪心算法的理论基础,首个x选出之前被舍弃元素的处理可以证明，这些被舍弃的元素，以
9、后也永远不可能用于构造最优子集。,17,4.8 贪心算法的理论基础,【引理4.3】：设M=(S,I)是拟阵。若S中元素x不是空集的可扩展元素，则x也不可能是S中任一独立子集A的可扩展元素证明：用反证法。设xS不是的一个可扩展元素，但它是S的某独立子集A的一个可扩展元素，即AxI，由I的遗传性可知x是独立的。这与x不是空集的一个可扩展元素相矛盾。由引理4.3可知，算法Greedy在初始化独立子集A时舍弃的元素可以永远舍弃。,18,4.8 贪心算法的理论基础,【引理4.4】拟阵的最优子结构性质设x是求带权拟阵M=(S,I)最优子集的贪心算法greedy所选择的S中的第一个元素。那么，原问题可简化为
10、求带权拟阵M=(S,I)的最优子集问题，其中：S=y|y S且x,y I，即y是x的可扩展元素I=B|B S-x且Bx IM的权函数是M的权函数在S上的限制(称M为M关于元素x的收缩)。,19,4.8 贪心算法的理论基础,证明：(P136)(1)若A是M的包含元素x的最大独立子集，则A=A-x是M的一个独立子集。反之，M的任一独立子集A产生M的一个独立子集A=Ax（均可由M的定义得到）。(2)在这两种情形下均有：W(A)=W(A)+W(x)因此M的包含元素x的最优子集包含M的一个最优子集，反之亦然。,20,4.8 贪心算法的理论基础,【定理4.5】带权拟阵贪心算法的正确性设M(S,I)是具有正
11、权函数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)中的任一独立子集BI，均有Bx在M中是独立的（由M的定义可知）。因此，Greedy选择了元素x后，后续求解将演变为求拟阵M=(
12、S,I)的最优子集问题。由归纳法可知：其后继步骤求出M的一个最优子集，从而算法Greedy最终求出的是M的一个最优子集。,22,4.8 贪心算法的理论基础,具有截止时间和误时惩罚的单位时间任务的调度时间表问题描述如下：(1)n个单位时间任务的集合S=1,2,n；(2)任务i的截止时间di,1in,1din，即要求任务i在时间di之前结束；(3)任务i的误时惩罚wi,1in,即任务i未在规定时间di之前结束将招致wi惩罚；若按时完成则无惩罚。任务时间表问题要求确定S的一个时间表（最优时间表）使得总误时惩罚达到最小。,4.例子：任务时间表问题(带期限作业调度问题),23,4.8 贪心算法的理论基础
13、,用带权拟阵的贪心算法求解的基本思路如下：(1)首先，将S的任一时间表调整成及时优先形式(截止时间之前完成的任务)，即其中所有及时任务先于误时任务，而不会影响原时间表中各任务的及时或误时性质。(2)然后，再进一步调整及时任务的次序，将S的时间表调整成为规范形式，即其中及时任务依其截止时间的非减序排列。(3)任务时间表问题等价于确定最优及时任务子集A的问题。,24,4.8 贪心算法的理论基础,一旦确定了最优及时任务子集A，将A中各任务依其截止时间的非减序列出，然后再以任意次序列出误时任务(S-A中的任务)，由此产生S的一个规范的最优时间表。,25,4.8 贪心算法的理论基础,下面证明“及时任务子
14、集族”构成拟阵设：Nt(A)是任务子集A中所有截止时间是t或小于t的任务数，t=1,2,n。则：任务子集A的独立性条件(即解约束条件：A中的任务都能及时完成)具有以下性质：【引理4.6】对于S的任一任务子集A，下面的各命题是等价的。(1)任务子集A是独立子集。(2)对于t=1,2,n，Nt(A)t。(3)若A中任务依其截止时间非减序排列，则A中所有任务都是及时的。,26,4.8 贪心算法的理论基础,主要证明过程：(1)(2)：假设任务子集A是独立的，且存在某个t使得Nt(A)t,则A中有多于t个任务要在时间t之前完成，这显然是不可能的。故A中必有误时任务，这与A是独立任务子集相矛盾。因此，对所
15、有t=1,2,n，Nt(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)设
16、A、B为独立任务子集且|B|A|，下面证明(S,I)满足交换性质。,29,4.8 贪心算法的理论基础,(a)设从时刻1开始，最后一次出现Nt(B)Nt(A)的t值为k,即k=maxt|Nt(B)Nt(A),1tn。由于Nn(B)=|B|,Nn(A)=|A|,而|B|A|,即Nn(B)Nn(A)。因此必有这样的k，符合kNj(A)。(b)取xB-A，且x的截止时间为k+1。令 A=Ax。下面证明A是独立的,30,4.8 贪心算法的理论基础,首先，由于A是独立的，故对于1tk有：Nt(A)=Nt(A)t。又由于B是独立的，故对ktn有Nt(A)=Nt(A)+1Nt(B)t。由【引理4.6】的条件(
17、2)可知:A是独立的。所以：(S,I)是一个拟阵。,31,4.8 贪心算法的理论基础,由【定理4.5】可知，用带权拟阵的贪心算法可以求得最大权(惩罚)独立（及时）任务子集A，以A作为最优时间表中的及时任务子集，即可构造出最优时间表。,32,4.8 贪心算法的理论基础,AlgorithmSet Greedy-Job(M,W)/拟阵 M=(S,I)A=;将S中的任务按照惩罚权值W排成非递增序；while(S!=)S.removeMax(x);if(AxI)A=Ax;return A,33,4.8 贪心算法的理论基础,计算时间复杂性是。其中f(n)是用于检测任务子集A的独立性所需的时间。用【引理4.
18、6】中的性质(2)容易设计一个 时间算法来检测任务子集的独立性。因此，整个算法的计算时间为。greedyJob算法的具体描述P139。,34,4.8 贪心算法的理论基础,算法改进用抽象数据类型并查集UnionFind可对上述算法作进一步改进。加上对权的排序工作量后,改进后的算法fasterJob所需的计算时间为。,35,4.8 贪心算法的理论基础,【引理】设T（m,n）是处理m次FIND和n-1次UNION的混合序列所要求的最坏情况时间(mn)，则对于某两个正常数K1和K2有 K1 m(m,n)T(m,n)K2 m(m,n)由于阿克曼函数的逆函数(m,n)是一个增长非常缓慢的函数(理论上没有上
19、界，但在实际应用中，对通常的m、n总有(m,n)3)，所以在忽略K1和K2常数情况下，UNION-FIND序列的时间复杂度几乎与FIND的次数m成线性关系。,36,计算时间为 的算法,基本思路：尽可能推迟对作业i的处理。如果还没有给作业i分配处理时间，则分配给它时间片-1,，其中应尽量取大且时间片-1，是空的。,37,例1：,设n=5,(p1,p5)=(20,15,10,5,1)(d1d5)(2,2,1,3,3)。使用上述规则，得最优解是J=1,2,4 J已分配的时间片正处理作业动作无1分配1,211,22分配0,11,20,1,1,23舍弃1,20,1,1,24分配2,31,2,40,1,1
20、,2,2,35舍弃,38,算法,procedure FJS(D,n,b,J,k)/D为期限数组、n作业数、b最大期限、J解向量、k作业个数1 integer b,D(n),J(n),F(0:b),P(0:b)2 for i0 to n do3 F(i)i；P(i)-14 end-for5 k0 6 for i1 to n do 7 jFIND(min(n,D(i)8 if F(j)0 then kk+1；J(k)i 9 LFIND(F(j)-1)；UNION(L,j)10 F(j)F(L)11 endif12 end-for13 end FJS,For循环中含n次查找和小于n次的合并,总时间与
21、n近似成线性关系,39,算法,procedure FIND(i)/查找含有元素i的树根，使用压缩规则压缩由i到根j的所有结点1j=i 2while PARENT(j)0 do/找根3 j=PARENT(j)4repeat5k=i 6while kj do/压缩由i到根j的结点 7 i=PARENT(k)8 PARENT(k)=j 9 k=i10repeat11return(j)12end FIND,40,算法,procedure UNION(i,j)/使用加权规则合并根为i和j的两个集合，i j/PARENT(i)COUNT(i)，PARENT(j)COUNT(j)1integer i,j,x
22、 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)x8 endif9end UNION,41,例2：,设n=7，(p1,p7)=(35,30,25,20,15,10,5)和(d1,d7)(4,2,4,3,4,8,3)。利用算法FJS求解上述作业集的最优解。最优解：J1，2，3，4，6,*余祥宣,等.计算机算法基础M.2版.武汉:华中理工大学出版社,2000.7075,42,将时间片i-1,i表示为i，其中1ib，
23、bminn,maxdi。管理时间片的基本方法是：给每个时间片设立一个标志指针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,
