Lecture 11 貪心算法的理論基礎(chǔ)-擬陣

第4章貪心算法4.8貪心算法的基礎(chǔ)理論1.擬陣2.帯權(quán)擬陣的貪心算法3.任務(wù)時間表問題本講主要內(nèi)容：2021/6/2714.8貪心算法的理論基礎(chǔ)借助于擬陣[1]（Matroid）工具，可建立關(guān)于貪心算法的較一般的理論。線性代數(shù)中有如下兩條性質(zhì)：（1）如果X＝{x1,x2,…,xk}是一個線性無關(guān)向量組，則對X的任意子集X’也是線性無關(guān)的。（2）如果X＝{x1,x2,…,xr}和Y＝{y1,y2,…,ym}是兩個線性無關(guān)向量組且m>r，則必存在一個yi∈Y，使得X∪{yi}是一個線性無關(guān)向量組。1935年，Whitney把以上兩條性質(zhì)進行了抽象推廣，提出了擬陣概念。[1]賴虹建.擬陣論[M].北京:高等教育出版社，2002年7月2021/6/2724.8貪心算法的理論基礎(chǔ)1.擬陣獨立公理集系統(tǒng)將擬陣M定義為滿足下面3個條件的有序?qū)?S,I)(1)S是非空有限集。(2)I是S的一類具有遺傳性質(zhì)的獨立[1]子集族，即若B

I，則B是S的獨立子集，且B的任意子集也都是S的獨立子集(即該子集屬于I)?？占?/p>

必為I的成員。(3)I滿足交換性質(zhì)，即若A

I,B

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

B-A，使得A∪{x}

I。[1]:此處的獨立子集是線性無關(guān)(或線性獨立)概念的推廣，代表I的入集條件2021/6/2734.8貪心算法的理論基礎(chǔ)例1：如非空集合S的子集K的冪集I=ρ(K),(S,I)是否為擬陣？例2：無向圖G=(V,E)的圖擬陣：，其中SG定義為圖G的邊集E，IG定義為SG的無循環(huán)邊集族，A

IG當(dāng)且僅當(dāng)A構(gòu)成圖G的森林*。注*：即IG是圖G的無環(huán)支撐（生成）子圖集合。支撐子圖（生成子圖）：包含圖G所有頂點的子圖。2021/6/2744.8貪心算法的理論基礎(chǔ)證明：滿足擬陣(S,I)的3個條件。(1)因為SG為圖G的邊集，顯然非空；(2)由于從SG的一個無循環(huán)邊集中去掉若干條邊不會產(chǎn)生循環(huán)，即森林的子集還是森林，因此SG的無循環(huán)邊集族IG具有遺傳性質(zhì)。2021/6/2754.8貪心算法的理論基礎(chǔ)(3)設(shè)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不會產(chǎn)生循環(huán)。由此得出IG滿足交換性質(zhì)，即若A

I,B

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

B-A，使得A∪{x}

I。2021/6/2764.8貪心算法的理論基礎(chǔ)2.擬陣的幾個重要概念和性質(zhì)【定義】：給定擬陣M=(S,I)，對于I中的獨立子集A

I，若S有一元素x

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

I,則稱x為A的可擴展元素。【定義】：當(dāng)擬陣M中的獨立子集A沒有可擴展元素時，稱A為極大獨立子集，或擬陣的基。2021/6/2774.8貪心算法的理論基礎(chǔ)關(guān)于極大獨立子集的性質(zhì)【定理4.1】 擬陣M中所有極大獨立子集的勢相同。

這個定理可以用反證法證明（P134）?！径x】若對擬陣M=(S,I)中的S指定權(quán)函數(shù)W，使得對于任意x

S，有W(x)>0，則稱擬陣M為帶權(quán)擬陣。依此權(quán)函數(shù)，S的任一子集A的權(quán)定義為。2021/6/2784.8貪心算法的理論基礎(chǔ)3.關(guān)于帶權(quán)擬陣的貪心算法許多用貪心算法求解的問題可以表示為求帶權(quán)擬陣的最大權(quán)獨立子集問題。給定帶權(quán)擬陣M=(S,I)，確定S的獨立子集A

I使得W(A)達到最大。這種使W(A)最大的獨立子集A稱為擬陣M的最優(yōu)子集。由于S中任一元素x的權(quán)W(x)是正的，因此，最優(yōu)子集也一定是極大獨立子集(不存在可擴展元素)。2021/6/2794.8貪心算法的理論基礎(chǔ)例如，最小生成樹問題可以表示為確定帶權(quán)擬陣MG的最優(yōu)子集問題。求帶權(quán)擬陣的最優(yōu)子集A的算法可用于解最小生成樹問題。帶權(quán)擬陣最優(yōu)子集的貪心算法框架如下：輸入：具有正權(quán)函數(shù)W的帶權(quán)擬陣M=(S,I)輸出：M的最優(yōu)子集A。2021/6/27104.8貪心算法的理論基礎(chǔ)Setgreedy(M,W){ A=

;

將S中元素依權(quán)值W（大者優(yōu)先）組成優(yōu)先隊列；

while(S!=

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

I)A=A∪{x};}returnA}2021/6/27114.8貪心算法的理論基礎(chǔ)算法Greedy的時間復(fù)雜度分析計算時間由兩部分組成：(1)設(shè)n＝|S|。將S中的元素依照其權(quán)值大小組成一個優(yōu)先隊列，并對其進行n次removeMax運算，需要O(n㏒n)的計算時間。(2)如果檢查A∪{x}是否獨立需要O(f(n))的計算時間，則對S中元素檢查一遍共需O(nf(n))。算法的計算時間復(fù)雜性為。2021/6/27124.8貪心算法的理論基礎(chǔ)【引理4.2】

擬陣的貪心選擇性質(zhì)設(shè)M=(S,I)是具有正權(quán)函數(shù)W的帶權(quán)擬陣，且S中元素依權(quán)值從大到小排列。又設(shè)x

S是S中第一個使得{x}是獨立子集的元素，則存在S的最優(yōu)子集A使得x

A。

2021/6/27134.8貪心算法的理論基礎(chǔ)證明：若不存在x

S，使得{x}是獨立子集，則引理是平凡的。設(shè)B是一個非空的最優(yōu)子集。由于B

I，且I具有遺傳性，故B中所有單個元素子集{y}均為獨立子集(滿足解約束)。又由于x是S中的第一個單元素獨立子集，故對任意的y

B，均有：W(x)≥W(y)。(1)若x

B，則只要令A(yù)=B，定理得證；(2)若x

B，我們按如下方法構(gòu)造包含元素x的最優(yōu)子集A。2021/6/27144.8貪心算法的理論基礎(chǔ)(a)首先，設(shè)A={x}，此時A是一個獨立子集。若|B|=|A|=1，則定理得證。(b)反復(fù)利用擬陣M的交換性質(zhì)，從B中選擇一個新元素加入A中并保持A的獨立性，直到|B|=|A|。此時必有一元素y

B且y

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

A。2021/6/27154.8貪心算法的理論基礎(chǔ)首個x選出之前被舍棄元素的處理

可以證明，這些被舍棄的元素，以后也永遠不可能用于構(gòu)造最優(yōu)子集。2021/6/27164.8貪心算法的理論基礎(chǔ)【引理4.3】：設(shè)M=(S,I)是擬陣。若S中元素x不是空集Φ的可擴展元素，則x也不可能是S中任一獨立子集A的可擴展元素證明：用反證法。設(shè)xS不是Φ的一個可擴展元素，但它是S的某獨立子集A的一個可擴展元素，即A∪{x}I，由I的遺傳性可知{x}是獨立的。這與x不是空集Φ的一個可擴展元素相矛盾。由引理4.3可知，算法Greedy在初始化獨立子集A時舍棄的元素可以永遠舍棄。2021/6/27174.8貪心算法的理論基礎(chǔ)【引理4.4】擬陣的最優(yōu)子結(jié)構(gòu)性質(zhì)設(shè)x是求帶權(quán)擬陣M=(S,I)最優(yōu)子集的貪心算法greedy所選擇的S中的第一個元素。那么，原問題可簡化為求帶權(quán)擬陣M’=(S’,I’)的最優(yōu)子集問題，其中：S’={y|y

S且{x,y}

I，即y是x的可擴展元素}I’={B|B

S-{x}且B∪{x}

I}M’的權(quán)函數(shù)是M的權(quán)函數(shù)在S’上的限制(稱M’為M關(guān)于元素x的收縮)。2021/6/27184.8貪心算法的理論基礎(chǔ)證明：(P136)(1)若A是M的包含元素x的最大獨立子集，則A’=A-{x}是M’的一個獨立子集。反之，M’的任一獨立子集A’產(chǎn)生M的一個獨立子集A=A’∪{x}（均可由M’的定義得到）。(2)在這兩種情形下均有：W(A)=W(A’)+W(x)因此M的包含元素x的最優(yōu)子集包含M’的一個最優(yōu)子集，反之亦然。2021/6/27194.8貪心算法的理論基礎(chǔ)【定理4.5】帶權(quán)擬陣貪心算法的正確性設(shè)M＝(S,I)是具有正權(quán)函數(shù)W的帶權(quán)擬陣，算法greedy返回M的最優(yōu)子集證明：(P137)(1)由【引理4.2】可知，如第一次加入A的元素是x，則必存在包含元素x的一個最優(yōu)子集。因此，Greedy第一次選擇是正確的。(2)由【引理4.3】可知，選擇x時被舍棄的元素不可能被再選中，即它們不可能是任一最優(yōu)子集中的元素。因此，這些元素可以永遠舍棄。2021/6/27204.8貪心算法的理論基礎(chǔ)(3)由【引理4.4】可知，Greedy選擇了元素x后，原問題簡化為求擬陣M’的最優(yōu)子集問題。

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

I’，均有B∪{x}在M中是獨立的（由M’的定義可知）。因此，Greedy選擇了元素x后，后續(xù)求解將演變?yōu)榍髷M陣M’=(S’,I’)的最優(yōu)子集問題。

由歸納法可知：其后繼步驟求出M’的一個最優(yōu)子集，從而算法Greedy最終求出的是M的一個最優(yōu)子集。2021/6/27214.8貪心算法的理論基礎(chǔ)具有截止時間和誤時懲罰的單位時間任務(wù)的調(diào)度時間表問題描述如下：(1)n個單位時間任務(wù)的集合S={1,2,…,n}；(2)任務(wù)i的截止時間di,1≤i≤n,1≤di≤n，即要求任務(wù)i在時間di之前結(jié)束；(3)任務(wù)i的誤時懲罰wi,1≤i≤n,即任務(wù)i未在規(guī)定時間di之前結(jié)束將招致wi懲罰；若按時完成則無懲罰。任務(wù)時間表問題要求確定S的一個時間表（最優(yōu)時間表）使得總誤時懲罰達到最小。4.例子：任務(wù)時間表問題(帶期限作業(yè)調(diào)度問題)2021/6/27224.8貪心算法的理論基礎(chǔ)用帶權(quán)擬陣的貪心算法求解的基本思路如下：(1)首先，將S的任一時間表調(diào)整成及時優(yōu)先形式(截止時間之前完成的任務(wù))，即其中所有及時任務(wù)先于誤時任務(wù)，而不會影響原時間表中各任務(wù)的及時或誤時性質(zhì)。(2)然后，再進一步調(diào)整及時任務(wù)的次序，將S的時間表調(diào)整成為規(guī)范形式，即其中及時任務(wù)依其截止時間的非減序排列。(3)任務(wù)時間表問題等價于確定最優(yōu)及時任務(wù)子集A的問題。2021/6/27234.8貪心算法的理論基礎(chǔ)

一旦確定了最優(yōu)及時任務(wù)子集A，將A中各任務(wù)依其截止時間的非減序列出，然后再以任意次序列出誤時任務(wù)(S-A中的任務(wù))，由此產(chǎn)生S的一個規(guī)范的最優(yōu)時間表。2021/6/27244.8貪心算法的理論基礎(chǔ)下面證明“及時任務(wù)子集族”構(gòu)成擬陣設(shè)：Nt(A)是任務(wù)子集A中所有截止時間是t或小于t的任務(wù)數(shù)，t=1,2,…,n。則：任務(wù)子集A的獨立性條件(即解約束條件：A中的任務(wù)都能及時完成)具有以下性質(zhì)：【引理4.6】對于S的任一任務(wù)子集A，下面的各命題是等價的。(1)任務(wù)子集A是獨立子集。(2)對于t=1,2,…,n，Nt(A)≤t。(3)若A中任務(wù)依其截止時間非減序排列，則A中所有任務(wù)都是及時的。2021/6/27254.8貪心算法的理論基礎(chǔ)主要證明過程：(1)→(2)：假設(shè)任務(wù)子集A是獨立的，且存在某個t使得Nt(A)>t,則A中有多于t個任務(wù)要在時間t之前完成，這顯然是不可能的。故A中必有誤時任務(wù)，這與A是獨立任務(wù)子集相矛盾。因此，對所有t=1,2,…,n，Nt(A)≤t；(2)→(3)：將A中任務(wù)按截止時間的非減序排列，則(2)中不等式意味著排序后A中截止時間為t的任務(wù)前面，需要調(diào)度的任務(wù)數(shù)是少于t的。故排序后A中所有任務(wù)都是及時的；2021/6/27264.8貪心算法的理論基礎(chǔ)最優(yōu)任務(wù)時間表問題：要求使總誤時懲罰達到最小，這等價于使任務(wù)時間表中的及時任務(wù)的懲罰值之和達到最大。該問題可用帶權(quán)擬陣的貪心算法求解。2021/6/27274.8貪心算法的理論基礎(chǔ)【定理4.7】設(shè)S是帶有截止時間的單位時間任務(wù)集，I是S的所有獨立(及時)任務(wù)子集構(gòu)成的集合。則有序?qū)?S,I)是擬陣。證明：(1)首先，獨立任務(wù)集的子集顯然也是獨立子集。故I滿足遺傳性質(zhì)。(2)設(shè)A、B為獨立任務(wù)子集且|B|>|A|，下面證明(S,I)滿足交換性質(zhì)。2021/6/27284.8貪心算法的理論基礎(chǔ)(a)設(shè)從時刻1開始，最后一次出現(xiàn)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(yù)’=A∪{x}。下面證明A’是獨立的2021/6/27294.8貪心算法的理論基礎(chǔ)首先，由于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貪心算法的理論基礎(chǔ)由【定理4.5】可知，用帶權(quán)擬陣的貪心算法可以求得最大權(quán)(懲罰)獨立（及時）任務(wù)子集A，以A作為最優(yōu)時間表中的及時任務(wù)子集，即可構(gòu)造出最優(yōu)時間表。2021/6/27314.8貪心算法的理論基礎(chǔ)AlgorithmSetGreedy-Job(M,W)//擬陣M=(S,I){ A=

;

將S中的任務(wù)按照懲罰權(quán)值W排成非遞增序；

while(S!=

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

I)A=A∪{x};}returnA}2021/6/27324.8貪心算法的理論基礎(chǔ)計算時間復(fù)雜性是。其中f(n)是用于檢測任務(wù)子集A的獨立性所需的時間。用【引理4.6】中的性質(zhì)(2)容易設(shè)計一個時間算法來檢測任務(wù)子集的獨立性。因此，整個算法的計算時間為。greedyJob算法的具體描述P139。2021/6/27334.8貪心算法的理論基礎(chǔ)算法改進用抽象數(shù)據(jù)類型并查集UnionFind可對上述算法作進一步改進。加上對權(quán)的排序工作量后,改進后的算法fasterJob所需的計算時間為。

2021/6/27344.8貪心算法的理論基礎(chǔ)【引理】設(shè)T（m,n）是處理m次FIND和n-1次UNION的混合序列所要求的最壞情況時間(m≥n)，則對于某兩個正常數(shù)K1和K2有K1mα(m,n)≤T(m,n)≤K2mα(m,n)由于阿克曼函數(shù)的逆函數(shù)α(m,n)是一個增長非常緩慢的函數(shù)(理論上沒有上界，但在實際應(yīng)用中，對通常的m、n總有α(m,n)≤3)，所以在忽略K1和K2常數(shù)情況下，UNION-FIND序列的時間復(fù)雜度幾乎與FIND的次數(shù)m成線性關(guān)系。2021/6/2735計算時間為的算法基本思路：盡可能推遲對作業(yè)i的處理。如果還沒有給作業(yè)i分配處理時間，則分配給它時間片[α-1,α]，其中α應(yīng)盡量取大且時間片[α-1，α]是空的。2021/6/2736例1：設(shè)n=5,(p1,…p5)=(20,15,10,5,1)

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

使用上述規(guī)則，得最優(yōu)解是J={1,2,4}J 已分配的時間片 正處理作業(yè) 動作

Ф 無 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為期限數(shù)組、n作業(yè)數(shù)、b最大期限、J解向量、k作業(yè)個數(shù) 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循環(huán)中含n次查找和小于n次的合并,總時間與n近似成線性關(guān)系2021/6/2738算法

procedureFIND(i)//查找含有元素i的樹根，使用壓縮規(guī)則壓縮由i到根j的所有結(jié)點 1

j=i 2

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

j=PARENT(j)

4

repeat 5

k=i 6

whilek≠jdo//壓縮由i到根j的結(jié)點

7

i=PARENT(k) 8

PARENT(k)=j 9

k=i 10

repeat 11

return(j) 12

endFIND2021/6/2739算法

procedureUNION(i,j)//使用加權(quán)規(guī)則合并根為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的結(jié)點少 5

PA