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

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

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

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

I,B

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

B-A，使得A∪{x}

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

IG當(dāng)且僅當(dāng)A構(gòu)成圖G的森林*。注*：即IG是圖G的無(wú)環(huán)支撐（生成）子圖集合。支撐子圖（生成子圖）：包含圖G所有頂點(diǎn)的子圖。2021/6/2744.8貪心算法的理論基礎(chǔ)證明：滿(mǎn)足擬陣(S,I)的3個(gè)條件。(1)因?yàn)镾G為圖G的邊集，顯然非空；(2)由于從SG的一個(gè)無(wú)循環(huán)邊集中去掉若干條邊不會(huì)產(chǎn)生循環(huán)，即森林的子集還是森林，因此SG的無(wú)循環(huán)邊集族IG具有遺傳性質(zhì)。2021/6/2754.8貪心算法的理論基礎(chǔ)(3)設(shè)A和B是圖G的兩個(gè)森林，且|B|＞|A|，即B的邊比A多。由于圖G中有k條邊的森林恰由|V|-k棵樹(shù)組成，因此B中的樹(shù)比A中的少。很顯然，B中至少存在一棵樹(shù)T，它的頂點(diǎn)分別在森林A的兩棵樹(shù)中。由于T是連通的，故T中必有一條邊(u,v)滿(mǎn)足u,v分別在A的兩棵樹(shù)中。因此將(u,v)加入A不會(huì)產(chǎn)生循環(huán)。由此得出IG滿(mǎn)足交換性質(zhì)，即若A

I,B

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

B-A，使得A∪{x}

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

I，若S有一元素x

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

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

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

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

I使得W(A)達(dá)到最大。這種使W(A)最大的獨(dú)立子集A稱(chēng)為擬陣M的最優(yōu)子集。由于S中任一元素x的權(quán)W(x)是正的，因此，最優(yōu)子集也一定是極大獨(dú)立子集(不存在可擴(kuò)展元素)。2021/6/2794.8貪心算法的理論基礎(chǔ)例如，最小生成樹(shù)問(wèn)題可以表示為確定帶權(quán)擬陣MG的最優(yōu)子集問(wèn)題。求帶權(quán)擬陣的最優(yōu)子集A的算法可用于解最小生成樹(shù)問(wèn)題。帶權(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)先隊(duì)列；

while(S!=

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

I)A=A∪{x};}returnA}2021/6/27114.8貪心算法的理論基礎(chǔ)算法Greedy的時(shí)間復(fù)雜度分析計(jì)算時(shí)間由兩部分組成：(1)設(shè)n＝|S|。將S中的元素依照其權(quán)值大小組成一個(gè)優(yōu)先隊(duì)列，并對(duì)其進(jìn)行n次removeMax運(yùn)算，需要O(n㏒n)的計(jì)算時(shí)間。(2)如果檢查A∪{x}是否獨(dú)立需要O(f(n))的計(jì)算時(shí)間，則對(duì)S中元素檢查一遍共需O(nf(n))。算法的計(jì)算時(shí)間復(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中第一個(gè)使得{x}是獨(dú)立子集的元素，則存在S的最優(yōu)子集A使得x

A。

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

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

I，且I具有遺傳性，故B中所有單個(gè)元素子集{y}均為獨(dú)立子集(滿(mǎn)足解約束)。又由于x是S中的第一個(gè)單元素獨(dú)立子集，故對(duì)任意的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}，此時(shí)A是一個(gè)獨(dú)立子集。若|B|=|A|=1，則定理得證。(b)反復(fù)利用擬陣M的交換性質(zhì)，從B中選擇一個(gè)新元素加入A中并保持A的獨(dú)立性，直到|B|=|A|。此時(shí)必有一元素y

B且y

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

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

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

S且{x,y}

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

S-{x}且B∪{x}

I}M’的權(quán)函數(shù)是M的權(quán)函數(shù)在S’上的限制(稱(chēng)M’為M關(guān)于元素x的收縮)。2021/6/27184.8貪心算法的理論基礎(chǔ)證明：(P136)(1)若A是M的包含元素x的最大獨(dú)立子集，則A’=A-{x}是M’的一個(gè)獨(dú)立子集。反之，M’的任一獨(dú)立子集A’產(chǎn)生M的一個(gè)獨(dú)立子集A=A’∪{x}（均可由M’的定義得到）。(2)在這兩種情形下均有：W(A)=W(A’)+W(x)因此M的包含元素x的最優(yōu)子集包含M’的一個(gè)最優(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的一個(gè)最優(yōu)子集。因此，Greedy第一次選擇是正確的。(2)由【引理4.3】可知，選擇x時(shí)被舍棄的元素不可能被再選中，即它們不可能是任一最優(yōu)子集中的元素。因此，這些元素可以永遠(yuǎn)舍棄。2021/6/27204.8貪心算法的理論基礎(chǔ)(3)由【引理4.4】可知，Greedy選擇了元素x后，原問(wèn)題簡(jiǎn)化為求擬陣M’的最優(yōu)子集問(wèn)題。

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

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

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

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

B-A，且x的截止時(shí)間為k+1。令A(yù)’=A∪{x}。下面證明A’是獨(dú)立的2021/6/27294.8貪心算法的理論基礎(chǔ)首先，由于A是獨(dú)立的，故對(duì)于1≤t≤k有：Nt(A’)=Nt(A)≤t。又由于B是獨(dú)立的，故對(duì)k<t≤n有Nt(A’)=Nt(A)+1≤Nt(B)≤t。由【引理4.6】的條件(2)可知:A’是獨(dú)立的。所以：(S,I)是一個(gè)擬陣。2021/6/27304.8貪心算法的理論基礎(chǔ)由【定理4.5】可知，用帶權(quán)擬陣的貪心算法可以求得最大權(quán)(懲罰)獨(dú)立（及時(shí)）任務(wù)子集A，以A作為最優(yōu)時(shí)間表中的及時(shí)任務(wù)子集，即可構(gòu)造出最優(yōu)時(shí)間表。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ǔ)計(jì)算時(shí)間復(fù)雜性是。其中f(n)是用于檢測(cè)任務(wù)子集A的獨(dú)立性所需的時(shí)間。用【引理4.6】中的性質(zhì)(2)容易設(shè)計(jì)一個(gè)時(shí)間算法來(lái)檢測(cè)任務(wù)子集的獨(dú)立性。因此，整個(gè)算法的計(jì)算時(shí)間為。greedyJob算法的具體描述P139。2021/6/27334.8貪心算法的理論基礎(chǔ)算法改進(jìn)用抽象數(shù)據(jù)類(lèi)型并查集UnionFind可對(duì)上述算法作進(jìn)一步改進(jìn)。加上對(duì)權(quán)的排序工作量后,改進(jìn)后的算法fasterJob所需的計(jì)算時(shí)間為。

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

Ф 無(wú) 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è)個(gè)數(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次的合并,總時(shí)間與n近似成線(xiàn)性關(guān)系2021/6/2738算法

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

j=i 2

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

j=PARENT(j)

4

repeat 5

k=i 6

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

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的兩個(gè)集合，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é)點(diǎn)少 5

PA