Lecture 11 贪心算法的理论基础-拟阵

第4章贪心算法4.8贪心算法的基础理论1.拟阵2.帯权拟阵的贪心算法3.任务时间表问题本讲主要内容：2021/6/2714.8贪心算法的理论基础借助于拟阵[1]（Matroid）工具，可建立关于贪心算法的较一般的理论。线性代数中有如下两条性质：（1）如果X＝{x1,x2,…,xk}是一个线性无关向量组，则对X的任意子集X’也是线性无关的。（2）如果X＝{x1,x2,…,xr}和Y＝{y1,y2,…,ym}是两个线性无关向量组且m>r，则必存在一个yi∈Y，使得X∪{yi}是一个线性无关向量组。1935年，Whitney把以上两条性质进行了抽象推广，提出了拟阵概念。[1]赖虹建.拟阵论[M].北京:高等教育出版社，2002年7月2021/6/2724.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，使得A∪{x}

I。[1]:此处的独立子集是线性无关(或线性独立)概念的推广，代表I的入集条件2021/6/2734.8贪心算法的理论基础例1：如非空集合S的子集K的幂集I=ρ(K),(S,I)是否为拟阵？例2：无向图G=(V,E)的图拟阵：，其中SG定义为图G的边集E，IG定义为SG的无循环边集族，A

IG当且仅当A构成图G的森林*。注*：即IG是图G的无环支撑（生成）子图集合。支撑子图（生成子图）：包含图G所有顶点的子图。2021/6/2744.8贪心算法的理论基础证明：满足拟阵(S,I)的3个条件。(1)因为SG为图G的边集，显然非空；(2)由于从SG的一个无循环边集中去掉若干条边不会产生循环，即森林的子集还是森林，因此SG的无循环边集族IG具有遗传性质。2021/6/2754.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不会产生循环。由此得出IG满足交换性质，即若A

I,B

I且|A|<|B|，则存在某一元素x

B-A，使得A∪{x}

I。2021/6/2764.8贪心算法的理论基础2.拟阵的几个重要概念和性质【定义】：给定拟阵M=(S,I)，对于I中的独立子集A

I，若S有一元素x

A，使得将x加入A后仍保持独立性，即A∪{x}

I,则称x为A的可扩展元素。【定义】：当拟阵M中的独立子集A没有可扩展元素时，称A为极大独立子集，或拟阵的基。2021/6/2774.8贪心算法的理论基础关于极大独立子集的性质【定理4.1】 拟阵M中所有极大独立子集的势相同。

这个定理可以用反证法证明（P134）。【定义】若对拟阵M=(S,I)中的S指定权函数W，使得对于任意x

S，有W(x)>0，则称拟阵M为带权拟阵。依此权函数，S的任一子集A的权定义为。2021/6/2784.8贪心算法的理论基础3.关于带权拟阵的贪心算法许多用贪心算法求解的问题可以表示为求带权拟阵的最大权独立子集问题。给定带权拟阵M=(S,I)，确定S的独立子集A

I使得W(A)达到最大。这种使W(A)最大的独立子集A称为拟阵M的最优子集。由于S中任一元素x的权W(x)是正的，因此，最优子集也一定是极大独立子集(不存在可扩展元素)。2021/6/2794.8贪心算法的理论基础例如，最小生成树问题可以表示为确定带权拟阵MG的最优子集问题。求带权拟阵的最优子集A的算法可用于解最小生成树问题。带权拟阵最优子集的贪心算法框架如下：输入：具有正权函数W的带权拟阵M=(S,I)输出：M的最优子集A。2021/6/27104.8贪心算法的理论基础Setgreedy(M,W){ A=

;

将S中元素依权值W（大者优先）组成优先队列；

while(S!=

){S.removeMax(x);if(A∪{x}

I)A=A∪{x};}returnA}2021/6/27114.8贪心算法的理论基础算法Greedy的时间复杂度分析计算时间由两部分组成：(1)设n＝|S|。将S中的元素依照其权值大小组成一个优先队列，并对其进行n次removeMax运算，需要O(n㏒n)的计算时间。(2)如果检查A∪{x}是否独立需要O(f(n))的计算时间，则对S中元素检查一遍共需O(nf(n))。算法的计算时间复杂性为。2021/6/27124.8贪心算法的理论基础【引理4.2】

拟阵的贪心选择性质设M=(S,I)是具有正权函数W的带权拟阵，且S中元素依权值从大到小排列。又设x

S是S中第一个使得{x}是独立子集的元素，则存在S的最优子集A使得x

A。

2021/6/27134.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。2021/6/27144.8贪心算法的理论基础(a)首先，设A={x}，此时A是一个独立子集。若|B|=|A|=1，则定理得证。(b)反复利用拟阵M的交换性质，从B中选择一个新元素加入A中并保持A的独立性，直到|B|=|A|。此时必有一元素y

B且y

A，使得A=B-{y}∪{x}，且满足：W(A)=W(B)-W(y)+W(x)≥W(B)由于B是一个最优子集，所以W(B)≥W(A)。因此W(A)=W(B)，即A也是一个最优子集，且x

A。2021/6/27154.8贪心算法的理论基础首个x选出之前被舍弃元素的处理

可以证明，这些被舍弃的元素，以后也永远不可能用于构造最优子集。2021/6/27164.8贪心算法的理论基础【引理4.3】：设M=(S,I)是拟阵。若S中元素x不是空集Φ的可扩展元素，则x也不可能是S中任一独立子集A的可扩展元素证明：用反证法。设xS不是Φ的一个可扩展元素，但它是S的某独立子集A的一个可扩展元素，即A∪{x}I，由I的遗传性可知{x}是独立的。这与x不是空集Φ的一个可扩展元素相矛盾。由引理4.3可知，算法Greedy在初始化独立子集A时舍弃的元素可以永远舍弃。2021/6/27174.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}且B∪{x}

I}M’的权函数是M的权函数在S’上的限制(称M’为M关于元素x的收缩)。2021/6/27184.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’的一个最优子集，反之亦然。2021/6/27194.8贪心算法的理论基础【定理4.5】带权拟阵贪心算法的正确性设M＝(S,I)是具有正权函数W的带权拟阵，算法greedy返回M的最优子集证明：(P137)(1)由【引理4.2】可知，如第一次加入A的元素是x，则必存在包含元素x的一个最优子集。因此，Greedy第一次选择是正确的。(2)由【引理4.3】可知，选择x时被舍弃的元素不可能被再选中，即它们不可能是任一最优子集中的元素。因此，这些元素可以永远舍弃。2021/6/27204.8贪心算法的理论基础(3)由【引理4.4】可知，Greedy选择了元素x后，原问题简化为求拟阵M’的最优子集问题。

由于对M’=(S’,I’)中的任一独立子集B

I’，均有B∪{x}在M中是独立的（由M’的定义可知）。因此，Greedy选择了元素x后，后续求解将演变为求拟阵M’=(S’,I’)的最优子集问题。

由归纳法可知：其后继步骤求出M’的一个最优子集，从而算法Greedy最终求出的是M的一个最优子集。2021/6/27214.8贪心算法的理论基础具有截止时间和误时惩罚的单位时间任务的调度时间表问题描述如下：(1)n个单位时间任务的集合S={1,2,…,n}；(2)任务i的截止时间di,1≤i≤n,1≤di≤n，即要求任务i在时间di之前结束；(3)任务i的误时惩罚wi,1≤i≤n,即任务i未在规定时间di之前结束将招致wi惩罚；若按时完成则无惩罚。任务时间表问题要求确定S的一个时间表（最优时间表）使得总误时惩罚达到最小。4.例子：任务时间表问题(带期限作业调度问题)2021/6/27224.8贪心算法的理论基础用带权拟阵的贪心算法求解的基本思路如下：(1)首先，将S的任一时间表调整成及时优先形式(截止时间之前完成的任务)，即其中所有及时任务先于误时任务，而不会影响原时间表中各任务的及时或误时性质。(2)然后，再进一步调整及时任务的次序，将S的时间表调整成为规范形式，即其中及时任务依其截止时间的非减序排列。(3)任务时间表问题等价于确定最优及时任务子集A的问题。2021/6/27234.8贪心算法的理论基础

一旦确定了最优及时任务子集A，将A中各任务依其截止时间的非减序列出，然后再以任意次序列出误时任务(S-A中的任务)，由此产生S的一个规范的最优时间表。2021/6/27244.8贪心算法的理论基础下面证明“及时任务子集族”构成拟阵设：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中所有任务都是及时的。2021/6/27254.8贪心算法的理论基础主要证明过程：(1)→(2)：假设任务子集A是独立的，且存在某个t使得Nt(A)>t,则A中有多于t个任务要在时间t之前完成，这显然是不可能的。故A中必有误时任务，这与A是独立任务子集相矛盾。因此，对所有t=1,2,…,n，Nt(A)≤t；(2)→(3)：将A中任务按截止时间的非减序排列，则(2)中不等式意味着排序后A中截止时间为t的任务前面，需要调度的任务数是少于t的。故排序后A中所有任务都是及时的；2021/6/27264.8贪心算法的理论基础最优任务时间表问题：要求使总误时惩罚达到最小，这等价于使任务时间表中的及时任务的惩罚值之和达到最大。该问题可用带权拟阵的贪心算法求解。2021/6/27274.8贪心算法的理论基础【定理4.7】设S是带有截止时间的单位时间任务集，I是S的所有独立(及时)任务子集构成的集合。则有序对(S,I)是拟阵。证明：(1)首先，独立任务集的子集显然也是独立子集。故I满足遗传性质。(2)设A、B为独立任务子集且|B|>|A|，下面证明(S,I)满足交换性质。2021/6/27284.8贪心算法的理论基础(a)设从时刻1开始，最后一次出现Nt(B)≤Nt(A)的t值为k,即k=max{t|Nt(B)≤Nt(A),1≤t≤n}。由于Nn(B)=|B|,Nn(A)=|A|,而|B|>|A|,即Nn(B)>Nn(A)。因此必有这样的k，符合k<n，且对于满足k+1≤j≤n的j有：Nj(B)>Nj(A)。(b)取x

B-A，且x的截止时间为k+1。令A’=A∪{x}。下面证明A’是独立的2021/6/27294.8贪心算法的理论基础首先，由于A是独立的，故对于1≤t≤k有：Nt(A’)=Nt(A)≤t。又由于B是独立的，故对k<t≤n有Nt(A’)=Nt(A)+1≤Nt(B)≤t。由【引理4.6】的条件(2)可知:A’是独立的。所以：(S,I)是一个拟阵。2021/6/27304.8贪心算法的理论基础由【定理4.5】可知，用带权拟阵的贪心算法可以求得最大权(惩罚)独立（及时）任务子集A，以A作为最优时间表中的及时任务子集，即可构造出最优时间表。2021/6/27314.8贪心算法的理论基础AlgorithmSetGreedy-Job(M,W)//拟阵M=(S,I){ A=

;

将S中的任务按照惩罚权值W排成非递增序；

while(S!=

){S.removeMax(x);if(A∪{x}

I)A=A∪{x};}returnA}2021/6/27324.8贪心算法的理论基础计算时间复杂性是。其中f(n)是用于检测任务子集A的独立性所需的时间。用【引理4.6】中的性质(2)容易设计一个时间算法来检测任务子集的独立性。因此，整个算法的计算时间为。greedyJob算法的具体描述P139。2021/6/27334.8贪心算法的理论基础算法改进用抽象数据类型并查集UnionFind可对上述算法作进一步改进。加上对权的排序工作量后,改进后的算法fasterJob所需的计算时间为。

2021/6/27344.8贪心算法的理论基础【引理】设T（m,n）是处理m次FIND和n-1次UNION的混合序列所要求的最坏情况时间(m≥n)，则对于某两个正常数K1和K2有K1mα(m,n)≤T(m,n)≤K2mα(m,n)由于阿克曼函数的逆函数α(m,n)是一个增长非常缓慢的函数(理论上没有上界，但在实际应用中，对通常的m、n总有α(m,n)≤3)，所以在忽略K1和K2常数情况下，UNION-FIND序列的时间复杂度几乎与FIND的次数m成线性关系。2021/6/2735计算时间为的算法基本思路：尽可能推迟对作业i的处理。如果还没有给作业i分配处理时间，则分配给它时间片[α-1,α]，其中α应尽量取大且时间片[α-1，α]是空的。2021/6/2736例1：设n=5,(p1,…p5)=(20,15,10,5,1)

(d1…d5)＝(2,2,1,3,3)。

使用上述规则，得最优解是J={1,2,4}J 已分配的时间片 正处理作业 动作

Ф 无 1 分配[1,2] {1} [1,2] 2 分配[0,1] {1,2} [0,1],[1,2] 3 舍弃 {1,2} [0,1],[1,2] 4 分配[2,3] {1,2,4} [0,1],[1,2],[2,3] 5 舍弃2021/6/2737算法

procedureFJS(D,n,b,J,k)//D为期限数组、n作业数、b最大期限、J解向量、k作业个数 1

integerb,D(n),J(n),F(0:b),P(0:b) 2

fori←0tondo 3

F(i)←i；P(i)←-1 4

end-for 5

k←0 6

fori←1tondo 7

j←FIND(min(n,D(i))) 8

ifF(j)≠0thenk←k+1；J(k)←i 9

L←FIND(F(j)-1)；UNION(L,j) 10

F(j)←F(L) 11

endif 12

end-for 13

endFJSFor循环中含n次查找和小于n次的合并,总时间与n近似成线性关系2021/6/2738算法

procedureFIND(i)//查找含有元素i的树根，使用压缩规则压缩由i到根j的所有结点 1

j=i 2

whilePARENT(j)>0do//找根 3

j=PARENT(j)

4

repeat 5

k=i 6

whilek≠jdo//压缩由i到根j的结点

7

i=PARENT(k) 8

PARENT(k)=j 9

k=i 10

repeat 11

return(j) 12

endFIND2021/6/2739算法

procedureUNION(i,j)//使用加权规则合并根为i和j的两个集合，i≠j//PARENT(i)＝－COUNT(i)，PARENT(j)＝－COUNT(j) 1

integeri,j,x 2

x=PARENT(i)+PARENT(j) 3

ifPARENT(i)>PARENT(j)

4

thenPARENT(i)=j//i的结点少 5

PA