第4章貪心法4.1背包問題

4.2活動選擇問題

4.3貪心算法的基本元素

4.4哈夫曼編碼

4.5最小生成樹算法

4.6貪心算法的理論基礎(chǔ)

4.7作業(yè)調(diào)度問題

習題

4.1背包問題

考慮背包問題(knapsackproblem)。某商店有n個物品，第i個物品價值為vi，重量(或稱權(quán)值)為wi，其中vi和wi為非負數(shù)。背包的容量為W，W也為一非負數(shù)。目標是如何選擇裝入背包的物品，使裝入背包的物品總價值最大。背包問題與0-1背包問題的不同點在于，在選擇物品裝入背包時，可以只選擇物品的一部分，而不一定要選擇物品的全部?？蓪⑦@個問題形式描述如下：(4.1)約束條件為

式(4.1)是目標函數(shù)，式(4.2)是約束條件。滿足約束條件的任一集合(x1,x2,…,xn)是問題的一個可行解(可行解即滿足約束條件的解)?？紤]表4-1中5個物品的一個例子，其中W=100。

4個可行解如表4-2所示。這4個可行解中第4個解的總價值最大。下面將看到，這個解是背包問題實例的最優(yōu)解。(4.2)表4-1背包問題實例表4-2背包問題實例的可行解定理4.1中證明，如果事先將物品按照vi/wi的非增次序排列，用這種策略得到的背包解，是該問題的最優(yōu)解，即過程GREEDY-KNAPSACK得到背包問題的最優(yōu)解。GREEDY-KNAPSACK(v,w,W,x,n)

1 x

0 //初始化解

2 c

W //c：背包剩余可用容量

3 fori

1to

n

do

4

if

w(i)

c//當前考慮的物品權(quán)值小于背包現(xiàn)有容量

5

thenx(i)

1//物品放入

6

c

c

w(i)//更新現(xiàn)有背包容量

7 ifi

n

8

then

x(i)

c/w(i)//將物品一部分放入背包

9 return

x //返回背包問題解

定理4.1如果v1/w1≥v2/w2≥…≥vn/wn，則算法GREEDY-KNAPSACK產(chǎn)生背包問題的一個最優(yōu)解。

證明:

設(shè)x=(x1,x2,…,xn)是GREEDY-KNAPSACK產(chǎn)生的解。如果所有的xi等于1，顯然這個解為最優(yōu)解。

考慮一般情況，設(shè)j是使得xj≠1的最小下標。由算法可知，對于1≤i≤j，xi=1；對于j<i≤n，xi=0；對于j，0≤xj<1。如果x不是問題的一個最優(yōu)解，則必定存在一個可行解y=(y1,y2,…,yn)，使得 。不失一般性，可以假定 。設(shè)k是使得yk≠xk的最小下標。顯然，這樣的k必定存在。由上述假設(shè)，可以推得yk<xk。以下首先證明這一點，分三種情況討論：

(1)若k<j，則xk=1。又yk≠xk，從而yk<xk。

(2)若k=j，對于1≤i<j，有xi=yi=1；而對于j<i≤n，有xi=0。若yk>xk，顯然有 ，因為 與y是可行解矛盾。若yk=xk，與假設(shè)yk≠xk矛盾，因此，yk<xk。

(3)若k>j，則 ，這是不可能的。

現(xiàn)在將yk增加到xk，那么必須從(yk+1,…,yn)中減去同樣多的量，使得所用的總?cè)萘咳匀皇荳。這導致一個新的解z=(z1,z2,…,zn)，其中，zi=xi，1≤i≤k，并且因此，對于z,有如果 ，則y不可能是最優(yōu)解。如果這兩個和相等，則或者z=x，x就是最優(yōu)解，或者z≠x。在后一種情況下重復上述過程，或者證明y不是最優(yōu)解，或者把y變成x，從而證明了x也是最優(yōu)解。證畢。

4.2活動選擇問題

活動選擇問題(activity-selectionproblem)即若干個具有競爭性的活動要求互斥使用某一公共資源，目標是選擇最大的相容活動集合。假定集合S={a1,a2,…,an}中含有n個希望使用某一資源的活動，這樣的資源有教室、某一設(shè)備等，它們一次只能由一個活動使用。每個活動ai有開始時間(starttime)si和完成時間(finishtime)fi，其中，0≤si<fi<∞。如果某個活動ai被選中使用資源，則該活動在半開區(qū)間(si，fi］這段時間占據(jù)資源。如果活動ai和aj在時間區(qū)間(si，fi］和(sj，fj］上不重疊，則稱它們是相容的(compatible)，即如果si≥fj

或者sj≥fi，活動ai和aj是相容的?；顒舆x擇問題是選擇最大的相容活動集合?？紤]表4-3所示的活動選擇問題實例。從這個例子可見，其中一個相容活動集合為{a3,a9,a11}，但這不是最大

的相容活動集。而{a1,a4,a8,a11}是最大的相容活動集，另一個相容活動集為{a2,a4,a9,a11}。我們將在稍后解釋為什么需預(yù)先對完成時間進行排序(f1≤f2≤…≤fn)，才能更好地解決這個問題。這個排序的運行時間為O(nlbn)。表4-3活動選擇問題實例

1.刻畫活動選擇問題的最優(yōu)子結(jié)構(gòu)

首先定義問題的子空間Sij={ak∈S：fi≤sk<fk≤sj}，Sij表示活動集合S的一個子集，它定義了那些在活動ai完成之后開始，在活動aj開始之前完成的所有活動集。事實上，Sij中所定義的活動與ai和aj相容，同時這些活動相互相容。為了

表達整個問題，我們虛構(gòu)兩個活動a0和an+1，并設(shè)f0=0和sn+1=∞。因此，S=S0,n+1，且0≤i，j≤n+1。

我們進一步限定i和j的范圍。假設(shè)活動按照完成時間遞增的次序排序：f0≤f1≤f2≤…≤fn≤fn+1。

性質(zhì)4.2如果i≥j，那么Sij=。

證明：用反證法。假定對于某些i≥j，存在活動ak∈Sij。按照排序位置，ai在aj之后。又因為fi≤sk<fk≤sj<fj，這與排序中ai在aj之后的假設(shè)相矛盾，故Sij=。證畢。

由此可得，如果我們將活動的完成時間排成升序，那么子問題空間就是從Sij中選擇最大相互相容活動子集，0≤i，j≤n+1，其他的Sij為空。為了搞清楚活動選擇問題的子結(jié)構(gòu)，考慮某些非空子集Sij(有時稱做子集，有時稱做子問題，讀者可從上下文看出)。假定Sij的一個解包括活動ak，則有fi≤sk<fk≤sj。活動ak產(chǎn)生兩個子問題Sik和Skj。Sik表示活動ai完成之后，活動ak開始之前的那些活動集。Skj表示活動ak完成之后，活動aj開始之前的那些活動集。這兩個集合中的每一個都是Sij中活動的一個子集。問題Sij的解為Sik和Skj的解并加上活動ak。因此，問題Sij的解的活動數(shù)為子集Sik的大小，加上子集Skj的大小，再加1(活動ak)。

問題的最優(yōu)子結(jié)構(gòu)表明，利用子問題的最優(yōu)解可以構(gòu)造問題的最優(yōu)解。由上述論證可知，任何非空子問題Sij的解包括某些活動ak，且任何最優(yōu)解包括子問題的最優(yōu)解。因此， Aij=Aik∪{ak}∪Akj

問題的最優(yōu)解為S0,n+1。

2.遞歸地求最優(yōu)解的值

對于活動選擇問題，設(shè)c［i,j］表示Sij中最大相容子集中的活動數(shù)。當Sij=時，c［i,j］=0；尤其對于i≥j，c［i,j］=0。

考慮非空子集Sij，由于活動ak出現(xiàn)在Sij的某些最大相容活動的子集中，根據(jù)上面的討論,則有

c［i,j］=c［i,k］+c［k,j］+1

在遞歸方程中，k值有j－i－1種選擇，即k=i+1,…,j－1。Sij的最大相容子集必為這些k值之一。我們可以逐一進行檢查，來得到問題的最優(yōu)解。因此，c［i,j］的遞歸定義變?yōu)?/p>

3.將動態(tài)規(guī)劃解轉(zhuǎn)換成貪心算法

基于遞歸方程(4.3)，我們可以寫一個自底向上的動態(tài)規(guī)劃算法。但是，基于兩點觀察，我們可以簡化求解過程。

定理4.3考慮非空子問題Sij，設(shè)am為Sij中完成時間最早的活動，且

fm=min{fk：ak∈Sij}

那么

(1)活動am出現(xiàn)在Sij的某些最大相容活動的子集中。

(2)子問題Sim為空，因此選擇am后，使得子問題Smj是惟一可能非空的子問題。(4.3)

證明：(2)的證明比較簡單，我們先證明它。假定Sim非空，則存在活動ak，滿足fi≤sk<fk≤sm<fm，那么ak也在Sij中，且活動ak的完成時間早于am。這與我們選擇am為Sij中完成時間最早的活動相矛盾。因此，Sim為空。

現(xiàn)在證明(1)。假定Aij是Sij中最大相容活動子集，并將Aij中的活動按照完成時間遞增的次序排列。設(shè)ak是Aij中的第一個活動。如果ak=am，則(1)得證，因為我們已經(jīng)證明am在最大相容活動子集中。如果ak≠am，我們構(gòu)造活動集合A'ij=Aij－{ak}∪{am}。A'ij中的活動互不相交，因為Aij中的活動ak是第一個要完成的活動，且fm≤fk。注意，A'ij中的活動數(shù)與Aij中的活動數(shù)相同。因此，A'ij是包括am在內(nèi)的Sij的一個最大相容活動子集。證畢。定理4.3的價值是巨大的。我們從以下的分析中可以看出。在3.4節(jié)討論了問題的最優(yōu)子結(jié)構(gòu)，它與原問題的最優(yōu)解中所用的子問題個數(shù)有關(guān)，還與決定使用哪個子問題所做的決策數(shù)有關(guān)。因此它與兩個因素有著直接關(guān)系。在活動選擇問題中，最優(yōu)解中利用了兩個子問題，解子問題Sij需要做出j－i－1種選擇。定理4.3大大減少了子問題的個數(shù)和所做的決策數(shù)，就是最優(yōu)解中只用到一個子問題(另一個子問題保證為空)；在解子問題Sij中，只需考慮一種選擇，就是考慮Sij中具有最早完成時間的那個活動。并且，我們可以容易地決定哪個活動具有最早完成時間。除了減少子問題的數(shù)目和減少選擇數(shù)目外，定理4.3還帶來了另一種好處：我們可以以自頂向下的方式解決每個子問題，而不必采用動態(tài)規(guī)劃中典型的自底向上的方式。為解決子問題Sij，我們可以選擇Sij中最早完成時間的活動am，并將這個解加入到子問題Smj的最優(yōu)解中。我們知道，一經(jīng)選擇am，我們可以肯定Sij的最優(yōu)解中一定會用到Smj的解。在解Sij之前，我們不需解子問題Smj。我們只需首先選擇最早完成時間的am作為Sij中的活動，然后解子問題Smj。我們要解的子問題存在結(jié)構(gòu)上的相似性。原始問題為S0,n+1。假定選擇S0,n+1中最早完成時間的活動，因為我們已按活動的完成時間排序，且f0=0，因此，這個被選的活動一定是m1=1。下一個子問題是 。假定選擇 中最早完成時間的活動，此時，這個被選的活動未必是m2=2，則我們下一個子問題是 。繼續(xù)這一過程，可以看到，對于某些活動號mi，每個子問題都是形如 的子問題。換句話說，每個子問題由那些所要完成的最后活動組成。這些活動的數(shù)目隨著子問題的不同而不同。在我們所選的活動之間同樣存在著結(jié)構(gòu)。因為我們總是選擇 中最早完成時間的活動，所以在所有子問題中所選活動的完成時間隨著時間嚴格遞增。我們只需按照完成時間遞增的次序，全面考慮每個活動一次即可。在解子問題的過程中，我們總是選擇可以合理安排且具有最早完成時間的活動am。這樣所做的選擇，從某種意義上說就是貪心選擇。它為其余要被調(diào)度的活動提供了盡可能多的機會，即貪心選擇就是使未經(jīng)調(diào)度的時間余量達到最大的選擇。

4.活動選擇問題的遞歸貪心算法

我們按照自頂向下的方式，將動態(tài)規(guī)劃算法線性化，可得到自頂向下的貪心算法。根據(jù)上述分析，我們給出該問題直接的遞歸過程RECUR-ACTIVITY-SELECT。輸入?yún)?shù)

為活動的起始時間s和完成時間f，以及子問題Sij的下標i和j。這個過程返回Sij中相互相容活動的最大子集。假設(shè)n個活動已按照完成時間排序。初始調(diào)用為RECUR-ACTIVITY-SELECT(s,f,0,n+1)。RECUR-ACTIVITY-SELECT(s,f,i,j)

1 m

i+1

2 while

m<jandsm<fi//找Sij中第一個活動

3

do

m

m+1

4 if

m<j

//找到滿足條件的活動m

5 thenreturn{am}

RECUR-ACTIVITY-SELECT(s,f,m,j)

//將m加入集合

6 elsereturn

圖4-1顯示了算法的運行過程。圖4-1算法RECUR-ACTIVITY-SELECT的運行過程

5.活動選擇問題的迭代貪心算法

過程RECUR-ACTIVITY-SELECT幾乎是一個“尾遞歸”：它以遞歸調(diào)用自己，并接著進行并的操作來結(jié)束。通常直接將尾遞歸轉(zhuǎn)變成迭代形式。盡管RECUR-ACTIVITY-SELEC

T調(diào)用子問題Sij，實際上，只需考慮j=n+1的子問題，即由最后完成的活動組成的那些子問題。過程ITERATIVE-ACTIVITY-SELECT是RECUR-ACTIVITY-SELECT的迭代形式,它也假設(shè)輸入活動按照完成時間遞增的次序排列。它將所選的活動放入集合A中，當執(zhí)行完成后，返回這個集合。ITERATIVE-ACTIVITY-SELECT(s,f,i,j)

1 n

length[s]

2 A

{a1} //活動a1加入集合

3 i

1

4 form

2ton

5

doifsm

fi //找到滿足條件的活動m

6

thenA

A

{am}//將活動m加入集合

7 i

m

//更新當前加入的活動

8 returnA

4.3貪心算法的基本元素

1.貪心選擇的性質(zhì)

更好地利用貪心算法的第一步是，問題具有貪心選擇(greedy-choice)的性質(zhì)，通過局部最優(yōu)選擇(貪心)，可以得到問題的全局最優(yōu)解。換句話說，當考慮要做出哪一個選擇時，我們會選擇當前看起來最優(yōu)的，而不考慮子問題的結(jié)果。這就是貪心算法和動態(tài)規(guī)劃算法的不同之處。在動態(tài)規(guī)劃算法中，當我們在每一步做出選擇時，這個選擇通常會依賴于

子問題的解。因而，我們一般會按照自底向上的方式，先從較小的問題開始求解，然后逐步求解較大的問題，最后解決原問題。而在貪心算法中，我們首先會做出當前看起來最優(yōu)的選擇，然后解決選擇之后出現(xiàn)的子問題。貪心算法的選擇可能取決于到目前為止所做的選擇，但不會依賴于未來的選擇，也不會依賴于子問題的解。因此，不像動態(tài)規(guī)劃算法那樣，采用貪心策略解問題的過程通常按照自頂向下的方式逐次進行貪心選擇，將每一給定問題實例減少到更小的問題實例。我們必須證明，在貪心選擇的每一步，都會產(chǎn)生問題的最優(yōu)解。正如定理4.1和定理4.3中問題所表明的那樣。首先考察全局最優(yōu)解，然后證明可以利用貪心策略，對這個全局最優(yōu)解進行修改，從而導致相似卻具有更小規(guī)模的子問題。貪心選擇的性質(zhì)常?？梢允沟脤ψ訂栴}進行決策時獲得更高的效率。在背包問題中，假定我們已經(jīng)按照每單位價值將物

品排成非升次序，那么每個物品只需檢查一次。在活動選擇問題中，假定我們已經(jīng)按照活動的完成時間把活動排成升序，那么每個活動只需檢查一次。因此，通常我們會對輸入數(shù)據(jù)進行預(yù)處理，或者利用一種合適的數(shù)據(jù)結(jié)構(gòu)，如優(yōu)先隊列，然后就能快速地進行貪心選擇，從而產(chǎn)生問題的有效算法。

2.最優(yōu)子結(jié)構(gòu)

如果問題的最優(yōu)解中包含子問題的最優(yōu)解，則我們說這個問題展示了最優(yōu)子結(jié)構(gòu)(optimalsubstructure)。這個性質(zhì)是評價應(yīng)用動態(tài)規(guī)劃以及貪心算法的基本性質(zhì)。作為最優(yōu)子結(jié)構(gòu)的例子，我們看到背包問題和活動選擇問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

在背包問題中，如果問題的一個最優(yōu)解包含物品j，我們從最優(yōu)裝包中去掉物品j的一個權(quán)值w，那么，余下至多為W－w的容量，一定包括n－1個物品以及物品j的權(quán)值為wj－w的最優(yōu)裝包方式。在活動選擇問題中，如果子問題Sij的最優(yōu)解包含活動ak，那么它也一定包含子問題Sik和子問題Skj的最優(yōu)解。給定這個最優(yōu)子結(jié)構(gòu)，我們論證如果知道選擇哪一個活動作為ak，則可以通過選擇活動ak、子問題Sik和Skj的最優(yōu)解中的所有活動構(gòu)造Sij的最優(yōu)解。基于最優(yōu)子結(jié)構(gòu)這點觀察，我們可以設(shè)計描述問題最優(yōu)解值的遞歸方程(4.3)。

3.貪心法與動態(tài)規(guī)劃

3.2節(jié)的0-1背包問題與4.1節(jié)的背包問題，都展示了最

優(yōu)子結(jié)構(gòu)性質(zhì)。3.2節(jié)通過動態(tài)規(guī)劃解0-1背包問題，4.1節(jié)通過貪心法解背包問題。這兩個問題是如此相似，但在解法上卻有很大差異。以下詳細地表明了這種差異。

0-1背包問題：給定n個物品，第i個物品價值為vi，重量(或稱權(quán)值)為wi，其中vi和wi為非負數(shù)，背包的容量為W，W為一非負數(shù)。目標是如何選擇裝入背包的物品，使裝入背包的物品總價值最大?？蓪⑦@個問題形式描述為：

，約束條件為 。背包問題：背包問題與0-1背包問題的不同點在于，在選擇物品裝入背包時，可以只選擇物品的一部分，而不一定要選擇物品的全部?？蓪⑦@個問題形式描述為：

，約束條件為

盡管這兩個問題很相似，但是背包問題可用貪心法求解，而0-1背包問題卻不能。在解背包問題時，我們首先計算每個物品的每單位權(quán)重的價值vi/wi，按照貪心策略，將每單位權(quán)重價值最大的物品盡可能放入背包。因此，預(yù)先按照每單位權(quán)重價值將物品排成降序，算法的運行時間為O(nlbn)，包括排序時間和GREEDY-KNAPSACK運行時間。背包問題的貪心選擇性質(zhì)見定理4.1。

4.4哈夫曼編碼

假定待壓縮的數(shù)據(jù)為字符序列。已知字符在序列中出現(xiàn)的頻率，哈夫曼貪心算法利用每個字符出現(xiàn)的頻率建立一棵表示各字符的最優(yōu)二叉樹。假定有100000個字符組成的數(shù)據(jù)文件需要壓縮，該文件中字符出現(xiàn)的頻率如表4-4所示。文件只有6種不同字符，其中字符c出現(xiàn)12000次。表4-4字符頻率與編碼

1.前綴碼

如果我們只用0/1對字符進行編碼，并限定任一字符的編碼都不是另一個字符編碼的前綴，則稱這樣的編碼為前綴碼(prefixcode)。如果用一棵二叉樹表示字符的前綴編碼，則編碼就變得簡單了。

如前所述，我們用二叉樹表示字符的前綴編碼，二叉樹的葉子結(jié)點表示給定字符，這樣從根結(jié)點到葉結(jié)點的路徑就定義了字符的二進制編碼，其中0表示指向左孩子，1表示指向右孩子。圖4-2(a)和(b)表示表4-4中的兩種前綴編碼。圖4-2兩種前綴編碼的二叉樹表示如果我們將所建立的二叉樹限定到完全二叉樹上，C為字母表，所有字符取自該字母表，那么最優(yōu)前綴編碼樹恰好有|C|個葉子結(jié)點，|C|－1個內(nèi)部結(jié)點。給定前綴編碼對應(yīng)的二叉樹T，計算編碼文件所要求的位數(shù)就是一件不難的事情。對于字母表C中的每個字符c，設(shè)f(c)表示c在文件中出現(xiàn)的頻率，dT(c)表示c的葉子結(jié)點在樹中的深度，因而，dT(c)也是字符c的編碼長度。因此，對一個文件編碼所需要的位數(shù)是

這個位數(shù)定義為樹T的代價。(4.4)

2.哈夫曼編碼的構(gòu)造及HUFFMAN算法

哈夫曼提出的貪心算法可以構(gòu)造最優(yōu)前綴編碼，這樣產(chǎn)生的編碼稱為哈夫曼編碼。算法正確性的證明基于兩點觀察，就是貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)。我們首先給出算法，然后證明這些性質(zhì)。假設(shè)C為n個字符集，對于每個字符c∈C，定義一個出現(xiàn)頻率f(c)。算法按照自底向上的方式建立最優(yōu)前綴編碼樹T。首先從|C|個葉子結(jié)點開始，然后進行|C|－1次歸并操作后，建立最終編碼樹T。在歸并時，利用基于頻率f的最小優(yōu)先隊列(minimalpriorityqueue)Q，選出兩個當前頻率最小的樹。這兩個對象歸并的結(jié)果是一棵新樹，它的頻率是這兩個被歸并樹的頻率之和。歸并后產(chǎn)生的樹被插入優(yōu)先隊列Q中。在過程HUFFMAN中，第2行用字符集C中的字符初始化最小優(yōu)先隊列Q。第3～8行的for循環(huán)摘取隊列Q中頻率最小的兩個結(jié)點x和y(分別代表兩棵子樹的根)，并將這兩棵樹合并成為一棵根為z的新樹，z以x為左孩子，y為

右孩子。插入z到隊列Q中。z的頻率f［z］為x和y的頻率之和，即f［x］+f［y］。經(jīng)過n－1次合并之后，隊列中只剩下一個結(jié)點。在第9行返回前綴編碼樹的根。注意，我們用最小堆(minimalheap)表示最小優(yōu)先隊列的數(shù)據(jù)結(jié)構(gòu)，該最小堆用一維數(shù)組實現(xiàn)。對于上述給定的6個字符的頻率，HUFFMAN算法運行過程如圖4-3所示。因為字符表中只有6個字符，初始隊列大小為6。經(jīng)過5步之后，得到所求的樹。這棵樹表示最優(yōu)前綴編碼樹，其中字符的前綴編碼是從根到該字符所經(jīng)過路徑的邊上標號的序列。圖4-3哈夫曼算法運行示例

3.哈夫曼算法的正確性

哈夫曼算法中采用了貪心策略。我們證明最優(yōu)前綴編碼問題展示了貪心選擇和最優(yōu)子結(jié)構(gòu)的性質(zhì)。引理4.4證明了貪心選擇的性質(zhì)。

引理4.4設(shè)C是字符c的集合，且字符c的頻率為f［c］。假定x和y是C中兩個頻率最小的字符，那么，存在C的最優(yōu)前綴編碼，使得x和y具有相同的編碼長度，且它們的編碼只在最后一位不同。

證明：設(shè)T是任一最優(yōu)前綴編碼樹。我們逐步修改這棵樹，使得字符x和y成為新樹中深度最大的兄弟葉子結(jié)點。如果做到這一點，則x和y在新樹中具有相同的編碼長度，且它們的編碼只在最后一位不同。

設(shè)a和b為T中深度最大且互為兄弟的葉子結(jié)點。不失一般性，假設(shè)f［a］≤f［b］，f［x］≤f［y］。因為f［x］和f［y］為C中最小的兩個頻率，f［a］和f［b］是任意兩個頻率，則有f［x］≤f［a］，f［y］≤f［b］。借助圖4-4，我們交換樹T中的結(jié)點x和a，得到一棵樹T′，然后，交換T′中的結(jié)點b和y，得到另一棵樹T″。由方程(4.4)可得，樹T和樹T′的代價之差為

由于x為最小頻率的葉子結(jié)點，因而f［a］－f［x］非負，又由于a是樹T中深度最大的葉子結(jié)點，因而dT(a)－dT(x)非負。類似地，交換y和b也不增加代價，于是B(T′)－B(T″)非負。

因此，B(T'')≤B(T)。又由于T是最優(yōu)的，可得B(T)≤B(T'')，這蘊含著，B(T'')=B(T)。因此，T''是最優(yōu)樹，且x和y是互為兄弟且深度最大的葉子結(jié)點。由此，引理得證。圖4-4引理4.4證明中的關(guān)鍵步驟圖示

引理4.5設(shè)C是字符c的集合，且字符c的頻率為f［c］。

假定x和y是C中兩個頻率最小的字符。設(shè)C′是字符C中去掉字符x和y，并加入新字符z后的集合。因此C′=C－{x,y}∪{z}。C′中字符頻率的定義同C，但f［z］=f［x］+f［y］。設(shè)T′為C′的一棵最優(yōu)前綴編碼樹，那么，在T′中用以x和y為孩子結(jié)點的內(nèi)部結(jié)點代替葉結(jié)點z，所得到的樹T是字符表C的最優(yōu)前綴編碼。

證明：由方程(4.4)，我們可以根據(jù)樹T′的代價B(T′)表示樹T的代價B(T)。對于每個c∈C－{x,y}，有

dT(c)=dT′(c)

因此

f［c］dT(c)=f［c］dT′(c)

由于

dT(x)=dT(y)=dT′(z)+1

可得

f［x］dT(x)+f［y］dT(y)=(f［x］+f［y］)(dT′(z)+1)

=f［z］dT′(z)+(f［x］+f［y］)由此可得

重寫得

B(T′)=B(T)－f［x］－f［y］用反證法證明引理4.5。假定T不能表示字符集C的最優(yōu)前綴編碼樹，則存在樹T″，滿足B(T″)<B(T)。不失一般性(引理4.4)，T″以x和y作為兄弟結(jié)點。設(shè)在樹T″中用葉結(jié)點z代替x和y的父結(jié)點所得樹為T，且z的頻率為f［z］=f［x］+f［y］,則有

B(T''')

=B(T'')–f[x]–f[y] //由引理4.4

<B(T)–f[x]–f[y] //由假設(shè)

=B(T’) //由引理4.4

上式表明，樹T是一棵比樹T′代價更小的樹，這與T′是字符集C′的最優(yōu)前綴編碼相矛盾。因此，樹T一定是字符集C的最優(yōu)前綴編碼樹。

定理4.6

HUFFMAN算法產(chǎn)生最優(yōu)前綴編碼樹。

證明：由引理4.4和4.5可得。

4.哈夫曼解碼

在開始壓縮數(shù)據(jù)流之前，編碼器(壓縮器)必須根據(jù)字符頻率(或者概率)確定編碼。字符的頻率(或者概率)也需要放在編碼流中，以便讓任何哈夫曼解碼器都能夠解碼該壓縮流。因為頻率是整數(shù)，而概率也可以標定成整數(shù)，通常只要在壓縮流中添加幾百字節(jié)就可以了。也可以把變長碼本身寫入流中，由于碼長不同，這樣做并不好。還可以把哈夫曼樹寫到流中，但這比只寫頻率所花費的字節(jié)數(shù)多。無論哪一種情況，解碼器必須知道流的開頭是什么，然后讀入它，為字母表構(gòu)造哈夫曼樹，然后才能解碼流的其他部分。解碼從樹根開始，讀入壓縮流的第一位，如果是0，就沿樹的左分支進行；如果是1，就沿樹的右分支進行。讀入下一位，并向樹葉方向深入一層。當解碼器到達一個葉子結(jié)點時，它就找到了原始未壓縮的字符(通常是其ASCII碼)，并將其輸出。再從根開始，繼續(xù)這一過程，直至輸出所有字符。

4.5最小生成樹算法

4.5.1最小生成樹的基本原理

圖4-5說明了一個連通圖及其最小生成樹的實例。圖中標示了各邊的權(quán)，最小生成樹中的邊用粗線表示。這棵生成樹的總權(quán)值為37。最小生成樹并不是惟一的。如果去掉其中的邊(b,c)，并用邊(a,h)替代，則仍可得到總權(quán)值為37的另外一棵最小生成樹。圖4-5連通圖的最小生成樹假設(shè)G=(V,E)是一連通、無向圖，加權(quán)函數(shù)為w：E→R。目標是找出G的最小生成樹。本章所給出的三個算法都利用了貪心策略，但在具體運用時有所不同。下面的一般最小生成樹算法捕獲了貪心算法的實質(zhì)。每次向當前最小生成樹中添加一條邊。算法管理邊的一個子集，并維持循環(huán)不變式：在每次迭代之前，A是某些最小生成樹的子集。在每一步中，當要將一條邊(u,v)添加到最小生成樹中時，我們測試A∪{(u,v)}是否也是某個最小生成樹的子集。如果滿足條件，我們稱這樣的邊為A的安全邊(safeedge)。因為對于這樣的邊，我們可以將它添加到A中，同時又保持循環(huán)不變式。GRNERIC-MST(G,w)

1 A

2 whileAdoesnotformaspanningtree

3

dofindanedge(u,v)thatissafeforA

4

A

A

{(u,v)}

5 return

A例如，在圖4-6(a)中，集合A中的結(jié)點為黑色結(jié)點，V－S中的結(jié)點為白色結(jié)點，連接黑色結(jié)點與白色結(jié)點的那些邊為穿過割的邊，邊(d,c)是惟一的一條輕邊。在圖4-6(b)中，對于同一個圖，我們將集合S中的點放在左邊，集合V－S中的點放在右邊。如果某條邊將左邊的一個頂點與右邊的一個頂點相連，則這條邊穿過割。圖4-6從不同角度觀察同一圖的割

定理4.7設(shè)G＝(V,E)是連通、無向圖。它的實值權(quán)函

數(shù)w定義在E上。設(shè)A是E的子集，并且包含在G的某個最小生成樹中。設(shè)(S,V－S)是G的遵從A的任意割，(u,v)是穿過(S,V－S)的輕邊，那么邊(u,v)對A是安全的。

證明：設(shè)T是包含A的最小生成樹，假設(shè)T不包含輕邊(u,v)，否則定理得證。利用切割—粘貼技術(shù)，我們構(gòu)造另一棵包含A∪{(u,v)}的最小生成樹T′，從而證明邊(u,v)對A是安全的。邊(u,v)形成T中的回路，回路中的邊在從u到v的路徑上。正如圖4-7中表明的那樣,S中的頂點為黑色，V－S中的頂點為白色，圖中只顯示最小生成樹中的邊，A中的邊用粗線表示，(u,v)是穿過割(S,V－S)的一條輕邊，邊(x,y)是T中從u到v的惟一路徑p上的邊。從T中去掉邊(x,y)，再加上邊(u,v)形成最小生成樹T′。由于u和v處于割(S,V－S)所在邊的相對方向上，因而T中的路徑p上至少存在一條邊也穿過割。設(shè)(x,y)是這樣的任意一條邊，因為割遵從A，所以邊(x,y)不在A中。由于(x,y)位于T中從x到y(tǒng)的惟一路徑上，因此若去掉邊(x,y)，T將分成兩部分，將(u,v)加入，使得這兩部分重新連接，并形成一棵新樹T′=T－{(x,y)}∪{(u,v)}。圖4-7定理4.7證明圖示

推論4.8設(shè)G＝(V,E)是連通、無向圖。它的實值權(quán)函數(shù)w定義在E上。設(shè)A是E的子集，并且包含在G的某個最小生成樹中。C=(VC,EC)為森林GA=(V,A)中的連通分量，如果邊(u,v)是連接C與GA中的其他連通分量的一條輕邊，那么，邊(u,v)對A是安全的。

證明：割(VC,V－VC)遵從A，且(u,v)是這個割的輕邊。于是，邊(u,v)對A是安全的。證畢。

在4.5.2～4.5.4節(jié)中所介紹的最小生成樹算法中，均采用某種規(guī)則來確定GENERIC-MST第3行所描述的安全邊。4.5.2

Kruskal算法

1.Kruskal算法

在Kruskal(Kruskalalgorithm)算法中，對于森林中連接任意兩棵樹的所有邊，找出它們中權(quán)值最小的邊(u,v)作為安全邊，并把它添加到正在擴展的森林中。設(shè)T1和T2表示邊(u,v)連接的兩棵樹，由于(u,v)必定是連接T1和其他某棵樹的一條輕邊，因而，由推論4.8可知，邊(u,v)對T1是安全的。同時，Kruskal算法在每一步中，以添加到森林中的邊的權(quán)值盡可能小為貪心策略。Kruskal算法的實現(xiàn)類似于計算連通分量的算法，它使用了不相交集的數(shù)據(jù)結(jié)構(gòu)，維持若干個不相交元素的集合，每個集合包含當前森林中某棵樹的結(jié)點。過程FIND-SET(u)返回包含頂點u的連通分量的名字。因此，我們可以通過測試FIND-SET(u)和FIND-SET(v)是否相同來判斷u和v是否屬于同一連通分量。用過程UNION完成樹的合并。KRUSKAL(G,w)

1 A

//初始化

2 foreachvertexv

V[G] //2-3行建立|V|棵樹

3

doMAKE-SET(v)

4 sorttheedgesofEintonondecreasingorderbyweightw//按權(quán)值w對邊排序

5 foreachedge(u,v)

E,takeninnondecreasingorderbyweight

6

doifFIND-SET(u)

FIND-SET(v) //檢查u和v是否屬于同一棵樹

7

then

A

A

{(u,v)}

8 UNION(u,v)

9 return

A在Kruskal算法中，第1～3行初始化集合A為空，并建立|V|棵樹，每棵樹中有一個結(jié)點。第4行對E中的邊按照權(quán)值非降序排序。第5～8行的for循環(huán)，檢查每條邊(u,v)的端點u和v是否在同一棵樹中。如果u和v在同一棵樹中，那么就不能將邊(u,v)加入森林中，否則會形成環(huán)。此時，放棄這條邊，考慮下一條邊。如果u和v分別屬于不同的樹，則執(zhí)行第7行，將邊(u,v)加入A中。第8行將這兩棵樹中的結(jié)點合并。

圖4-8以圖4-5所示的最小生成樹為例，說明Kruskal算法的執(zhí)行過程。圖4-8(a)表示Kruskal算法第1～4行執(zhí)行后(初始化)，A及E中的結(jié)果。圖4-8(b)～(j)表示執(zhí)行第5～9行后，A

及E中的結(jié)果。圖4-8

Kruskal算法的執(zhí)行過程圖4-8

Kruskal算法的執(zhí)行過程(續(xù))

2.Kruskal算法的數(shù)據(jù)結(jié)構(gòu)

在Kruskal算法中，使用了不相交集中的三個過程。這些過程是MAKE-SET、FIND-SET和UNION。MAKE-SET創(chuàng)建一棵只含一個結(jié)點的樹。執(zhí)行FIND-SET操作時，跟蹤父指針直至找到樹的根，在此根的路徑上訪問過的結(jié)點構(gòu)成了尋找路徑。合并操作UNION使得一棵樹的根指向另一棵樹的根，如圖4-9所示。圖4-9不相交集合的森林及合并操作在實現(xiàn)合并操作UNION時，一個包含n-1次UNION操作的序列可能會構(gòu)造出一棵有n個結(jié)點線性鏈樹。我們對此進行改進。在進行UNION合并操作時，按照樹中結(jié)點多少進行合并，使得包含結(jié)點較少的樹的根指向包含結(jié)點較多的樹的根。對于每個結(jié)點，用rank表示這個結(jié)點高度的一個上界(可以設(shè)為該結(jié)點子樹中結(jié)點個數(shù)的對數(shù))，稱為秩。在按秩合并的UNION操作中，具有較小秩的根指向具有較大秩的根。同樣，在FIND-SET操作中，使用了路徑壓縮技術(shù)，在執(zhí)行FING-SET之后，使尋找路徑上的每個結(jié)點都直接指向根結(jié)點，如圖4-10所示。圖4-10

FIND-SET過程中使用的路徑壓縮技術(shù)MAKE-SET(x) //建立只有一個結(jié)點的樹

1 p[x]

x

2 rank[x]

0

UNION(x,y) //使某棵樹的根指向另一棵樹

1 LINK(FIND-SET(x),FIND-SET(y))LINK(x,y) //以兩個指向根的指針作為輸入

1ifrank[x]>rank[y]

2 thenp[y]

x

3 elsep[x]

y

4 ifrank[x]=rank[y]

5 thenrank[y]

rank[y]+1

FIND-SET(x) //返回x所在樹的根結(jié)點

1 ifx

p[x]

2 thenp[x]

FIND-SET(p[x])

3 returnp[x]

3.Kruskal算法的運行時間

Kruskal算法的運行時間取決于不相交集數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)。在分析這一算法復雜度時，假設(shè)采用按秩合并與路徑壓縮技術(shù)。第1行初始化A的運行時間為O(1)。第4行對邊上權(quán)值進行排序的時間為O(ElbE)。第5～8行的for循環(huán)對不相交集森林進行O(E)次FIND-SET和UNION操作，以及|V|次MAKE-SET操作。這些操作所需總時間為O((V+E)α(V))，其中α為圖中頂點個數(shù)|V|的緩慢增長函數(shù)。若2048≤|V|<1081，則α(V)=4。由于假設(shè)G為連通圖，即有|E|≥|V|－1，因而，不相交集的操作需要O(Eα(V))時間。此外，α(V)=O

(lbV)=O(lbE)。因此，Kruskal算法的運行時間為O(ElbE)。又因為|E|<|V|2，所以有l(wèi)b|E|=O(lbV)。因此，我們可以說，Kruskal算法的運行時間為O(ElbV)。由此可得，當圖G為稀疏圖，即|E|<<|V|2時，Kruskal算法更有效。4.5.3

Prim算法

在Prim算法(Primalgorithm)中，集合A形成一棵樹，添加到集合A中的安全邊總是連接樹與一非樹結(jié)點的最小權(quán)值邊。Prim算法類似于Dijkstra單源點最短路徑算法，我們將在第7章討論該算法。Prim算法具有這樣一個性質(zhì)：集合A中的邊總是形成一棵樹。如圖4-11所示，算法從任一頂點開始，不斷擴展直到這棵樹張成V中的所有頂點。算法在每一步執(zhí)行中，都將一條輕邊加入到樹A中，這條輕邊將A連向GA=(V,A)中的一個孤立頂點。由推論4.8可得，這條規(guī)則只

加入對A安全的邊。當算法終止時，A中的邊構(gòu)成一棵最小生成樹。貪心策略體現(xiàn)在算法的每一步驟中，是用對樹產(chǎn)生最小可能權(quán)值的邊擴展這棵樹的。圖4-11

Prim算法的執(zhí)行過程圖4-11

Prim算法的執(zhí)行過程(續(xù))

1.Prim算法

有效實現(xiàn)Prim算法的關(guān)鍵是，如何簡單地選擇一條新邊，加入到A中邊所形成的樹中。在以下描述的算法中，算法以連通圖G和要被擴展的最小生成樹的根r作為輸入?yún)?shù)。

在算法執(zhí)行過程中，所有不在樹中的頂點駐留在以key作為優(yōu)先級的最小優(yōu)先隊列Q中。對于每個頂點v，key［v］表示v與最小生成樹中結(jié)點相連邊的最小權(quán)值。若不存在滿足這樣條件的邊，則設(shè)key［v］=∞。π［v］表示v在樹中的父結(jié)點。算法執(zhí)行中，GENERIC-MST中的集合A隱含地保存為

A={(v,π［v］)：v∈V－{r}－Q}

算法終止時，最小優(yōu)先隊列為空；G的最小生成樹A為

A={(v,π［v］)：v∈V－{r}}

PRIM(G,w,r)

1 foreachu

V[G]

2

do

key[u]

//初始化頂點邊上權(quán)值

3

[u]

NIL //初始化頂點前驅(qū)

4 key[r]

0 //設(shè)置根r邊上權(quán)值為0

5 Q

V[G]

6 while

Q

7

do

u

EXTRACT-MIN(Q) //摘取優(yōu)先隊列中按key域的最小元素

8 foreachv

Adj[u] //考察頂點u的每個近鄰v

9 doif

v

Qandw(u,v)<key[v]//如果為真，則進行更新

10

then

[v]

u

11

key[v]

w(u,v)

2.Prim算法的數(shù)據(jù)結(jié)構(gòu)及運行時間

Prim算法的運行時間取決于最小優(yōu)先隊列Q的實現(xiàn)。如果優(yōu)先隊列Q的數(shù)據(jù)結(jié)構(gòu)用二叉堆(這里指最小堆)實現(xiàn)，我們就可以在第1～5行中采用BUILD-MIN-HEAP(詳細描述見4.4節(jié))進行初始化，所需時間為O(V)。while循環(huán)體執(zhí)行|V|次。每次摘取元素的操作EXTRACT-MIN需要O(lbV)時間，因此，調(diào)用所有EXTRACT-MIN操作的總時間為O(VlbV)。因為所有鄰接表的長度之和為2|E|，因此第8～11行的for循環(huán)總共執(zhí)行O(E)次。我們可以在每個頂點內(nèi)設(shè)置1位，用以說明該頂點是否在隊列Q中。這樣在for循環(huán)內(nèi)，第9行的條件測試就可以用常數(shù)時間實現(xiàn)。當該頂點被從隊列Q中刪除時，則對這一位進行更新。第11行的賦值隱含著調(diào)用基于最小堆的DECREASE-KEY過程，我們可以用最小二叉堆在O(lbV)時間實現(xiàn)DECREASE-KEY過程(詳細描述見4.4節(jié))。因此，Prim算法的運行時間為O(VlbV+ElbV)=O(ElbV)。從漸近意義上看，Prim算法的運行時間與Kruskal算法的運

行時間相同。如果使用Fibonacci堆(Fibonacciheap)而不是二叉堆作為隊列Q的數(shù)據(jù)結(jié)構(gòu)，可以改進Prim算法漸近意義上的運行時間。這時|V|個頂點按照Fibonacci堆進行組織，我們可以用

O(lbV)的分攤時間(amortizedtime)進行EXTRACT-MIN操作,用O(1)的分攤時間進行DECREASE-KEY操作來實現(xiàn)第11行。因此，如果利用Fibonacci堆作為隊列Q的數(shù)據(jù)結(jié)構(gòu)，則Prim算法的運行時間為O(E+VlbV)。4.5.4

Boruvka算法

Boruvka算法(Boruvkaalgorithm)也是最古老的MST算法之一，1926年由Boruvka提出，遠遠早于計算機的存在，甚至早于圖論(1936年D.K[AKo¨]nig出版第一本有關(guān)圖論的書)的發(fā)明。它類似于Kruskal算法，通過不斷地向最小生成樹的子樹森林添加邊來擴展最小生成樹。但這是分步完成的，每一步中可以向最小生成樹中添加數(shù)條邊。在每一步中，找出連接MST子樹與另一棵子樹的所有邊，再將所有這樣的邊添加到MST中。Boruvka算法的運行過程如圖4-12所示。圖4-12

Boruvka算法最小生成樹示例BORUVKA(G,w,r)

1 F

(V,

)

2 while

Fhasmorethanonecomponent//森林F不為空，即存在連通分量

3

dochooseleadersusingDFS //利用DFS選出每個連通分量的代表

4

FIND-SAFE-EDGES(V,E) //找出安全邊

5

foreachleaderv'

6 doaddsafe[v']toFFIND-SAFE-EDGES(V,E)

1 foreachleaderv'

2

dosafe[v']

3 foreachedge(u,v)

E

4

u'

leader[u]

5

v'

leader[v]

6

if

u'

v'

7

thenif

w(u,v)<w(safe[u'])

8

thensafe[u']

(u,v)

9 ifw(u,v)<w(safe[v'])

10

thensafe[v']

(u,v)4.5.5比較與改進

表4-5對4.5節(jié)討論的基本MST算法的運行時間進行了總結(jié)。結(jié)果表明：對于稠密圖，Prim算法的鄰接矩陣是其首選方法；對于中等密度的圖，所有其他方法的運行時間比最好的選擇(選取邊所需時間)僅多一個常數(shù)因子；對于稀疏圖，Kruskal算法是首選方法。表4-5各種MST算法的比較 4.6貪心算法的理論基礎(chǔ)

1.擬陣定義及性質(zhì)

一個擬陣是一個有序?qū)=(S,L)，它滿足以下條件:

(1)S是一個非空有限集。

(2)L是S的非空子集簇，稱為S的獨立子集(independentsubset)，如果B∈L且A

B，那么A∈L。如果L滿足這個性質(zhì)，則稱L是遺傳的(hereditary)。注意，空集必為L的一個成員。

(3)如果A∈L，B∈L，且|A|<|B|，那么，存在元素x∈B－A，滿足A∪{x}∈L。我們稱M滿足交換性質(zhì)。設(shè)S是給定矩陣中各行的集合，如果這些行是線性無關(guān)的，則它們是獨立的。容易證明(S,L)是一擬陣。

我們可以根據(jù)給定無向圖G=(V,E)，定義圖擬陣(graphicmatriod)MG=(SG,LG)，其中集合SG定義為G中邊的集合E。如果A是E的子集，則A∈LG，當且僅當A是無環(huán)的，即邊的集合A是獨立的，當且僅當子圖GA=(V,A)形成森林。

定理4.9如果G=(V,E)是一無向圖，那么MG=(SG,LG)是一擬陣。

證明：顯然，SG=E是有限集,并且森林的子集還是森林，因而L是遺傳的。換句話說，從邊的無環(huán)集合中刪除一些邊，并不會產(chǎn)生回路?，F(xiàn)在要證明，MG滿足交換性質(zhì)。假設(shè)GA=(V,A)和GB=(V,B)是G的森林，且|B|>|A|,即A和B都是邊的無環(huán)集合，B比A包含更多邊。由于k條邊的森林只含|V|－k棵樹，因此，森林GA包含|V|－|A|棵樹，森林GB包含|V|－|B|棵樹。

因為森林GB中包含的樹比GA中的要少，那么森林GB中一定包含某些樹T，其頂點在森林GA中的兩棵不同樹上。由于T連通，它一定包含一條邊(u,v)，滿足頂點u和v在森林

GA的不同樹上。因為邊(u,v)連接森林GA中兩棵不同樹中的頂點，所以可將邊(u,v)添加到森林GA中，而不形成回路。因而，MG滿足交換性質(zhì)，MG是擬陣。證畢。給定擬陣M=(S,L)，我們稱元素xA是L∈A的一個擴展(extension)元素，如果將x添加到A中，同時保持獨立性，即如果A∪{x}∈L，則x是A的一個擴展元素?？紤]圖擬陣MG,如果A是邊的獨立集，那么邊e是A的擴展元素，當且僅當e不在A中，且將e加入A后不會產(chǎn)生回路。

如果A是擬陣M中的獨立子集，而且它不存在擴張元素，則稱A是最大的。也就是說，如果它不被M中更大的子集包含，則它是最大的。

定理4.10擬陣中所有最大獨立子集大小相同。

證明：用反證法。假設(shè)A是M的最大獨立子集，存在M的另一個更大的獨立子集B,則由交換性質(zhì)可得，對于某些x∈B－A，A可擴展到更大集合A∪{x}。這與A是最大假設(shè)相矛盾。證畢。

作為這個定理的說明，考慮連通無向圖G=(V,E)的圖擬陣MG。MG的每個最大獨立子集一定是只有|V|－1條邊的自由樹，連接G中所有頂點,這樣的樹稱為G的生成樹(spanningtree)。如果存在相關(guān)權(quán)函數(shù)w，對每一個x∈S的元素賦予嚴格正權(quán)值，則稱擬陣M=(S,L)是加權(quán)的。對權(quán)函數(shù)w求和，擴展到S的子集A上, 。如果我們用w(e)表示圖擬陣MG中邊e的長度，那么w(A)是邊集A中所有邊的總長度。

2.加權(quán)擬陣的貪心算法

許多利用貪心算法得到最優(yōu)解的問題，可以歸結(jié)為求加權(quán)擬陣的最大加權(quán)獨立集，即給定加權(quán)擬陣M=(S,L)，我們希望找出獨立集A∈L，使得w(A)最大。我們稱這個獨立、具有最大權(quán)值的子集為擬陣的最優(yōu)子集。因為元素x∈S的權(quán)值w(x)為正，所以一個最優(yōu)子集總是一個最大獨立子集，它使得A盡可能地大。算法的貪心策略表現(xiàn)在，它按權(quán)值下降次序依次考慮每個元素x∈S，且如果A∪{x}獨立，則立即將該元素加入集合A。

GREEDY(M,w)

1 A

2 SortS[M] //將S[M]按權(quán)值w排成單調(diào)遞減的次序

3 foreachx

S[M]

4

doif

A

{x}

L[M]

5 thenA

A

{x}

6 return

A

引理4.11擬陣具有貪心選擇性質(zhì)。

假設(shè)M=(S,L)是權(quán)函數(shù)為w的加權(quán)擬陣，且S按照權(quán)值下降次序依次排列。設(shè)x是S中的第一個元素，滿足{x}是獨立的(如果存在這樣的元素)。如果存在元素x，那么存在包含x的S的最優(yōu)子集A。

證明：如果不存在這樣的x，那么惟一的獨立集A是空集，引理平凡成立。設(shè)B是任意非空最優(yōu)子集，假設(shè)x

B(如果x∈B，只需令A(yù)=B，引理成立)。

首先證明B中不存在大于w(x)的元素。注意y∈B，蘊含{y}是獨立的，因為B∈L且L是遺傳的。我們選擇的x保證了對于任意y∈B，有w(x)≥w(y)。集合A構(gòu)造如下。初始A={x}。由x的選擇可知，A是獨立的。利用交換性質(zhì)，不斷在B中尋找能夠添加到A中的新元素，同時保證A的獨立性。這一過程直到|A|=|B|為止。

這樣，對于某些y∈B，A=B－{y}∪{x}。于是有

w(A)=w(B)－w(y)+w(x)≥w(B)

因為B是最優(yōu)的，因而A也必定是最優(yōu)的。又因為x∈A，定理得證。證畢。

以下證明，如果元素在初始時未被選中，以后也不會被選中。

引理4.12設(shè)M=(S,L)是擬陣。如果x是S中的一個元素，該元素是S的獨立子集A的擴展元素，那么x也是空集的擴展元素。

證明：因為x是A的擴展元素，則有A∪{x}是獨立集。因為L是遺傳的，則{x}必定是獨立的。因此，x是空集的擴展元素。證畢。

推論4.13設(shè)M=(S,L)是擬陣。如果x是S中的一個元素，滿足x不是空集的擴展元素，那么x也不是S的獨立子集A的擴展元素。

證明：這是引理4.12的反命題。證畢。

推論表明，如果一個元素不能很快被利用，則它以后永遠也不會被利用。因而，若GREEDY算法對那些S中非空的擴展元素不予選擇，那么以后也不予選擇。

引理4.14擬陣具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

設(shè)x是S中第一個被GREEDY算法選擇的元素，用于加權(quán)擬陣M=(S,L)。找包含x的最大加權(quán)獨立子集的問題可以歸約為找加權(quán)擬陣M′=(S′,L′)的最大加權(quán)獨立子集的問題，其中:

S′={y∈S：{x,y}∈L}

L′={B

S－{x}：B∪{x}∈L}

且M′的權(quán)函數(shù)為受限于S′的M的權(quán)函數(shù)。我們稱M′為由x對M產(chǎn)生的收縮。

證明：如果A是包含x的最大加權(quán)獨立子集，那么，A′=A－{x}是M′的獨立子集。反之，由任何M′的獨立子集A′可得M的獨立子集A=A′∪{x}。因為在兩種情況下都有w(A)=w(A′)+w(x)，所以，由M中包含x的一個最大加權(quán)解可得M′中的一個最大加權(quán)解，反之亦然。證畢。

定理4.15擬陣貪心算法的正確性。

如果M=(S,L)是權(quán)函數(shù)為w的加權(quán)擬陣，則GREEDY返回最優(yōu)子集。

證明：由推論4.13可得，初始時被忽略的元素，不是的擴展元素，可以不予考慮,因為它們不會被用到。一旦第一個元素x被選,引理4.11蘊含將x添加到A中是正確的，因為存在包含x的最優(yōu)子集。引理4.14蘊含剩下的問題就是在M的由x引起的收縮M'中尋找一個最優(yōu)子集。在過程GREEDY將A設(shè)置為{x}之后，剩下的各步可看做是在M′=(S′,L′)中進行的，因為對于所有集合B∈L′，B在M′中是獨立的，當且僅當B∪{x}在M中是獨立的。因此，GREEDY的后續(xù)操作會找出M′的最大加權(quán)獨立子集，GREEDY的總操作將找出M的最大加權(quán)獨立子集。證畢。

4.7作業(yè)調(diào)度問題

單機上單位時間作業(yè)(unit-timejob)的最優(yōu)調(diào)度(scheduling)問題可用擬陣理論求解。假定每個作業(yè)有一個截止期及一個罰款，如果作業(yè)在截止期內(nèi)沒有被處理完，則要招致罰款。問題看似復雜，但用貪心算法求解卻出奇地簡單。

單位時間的作業(yè)可以是運行在計算機上的程序，它只需要一個單位運行時間。給定單位時間作業(yè)的有限集合S，S的一個調(diào)度是S的一個排列，它確定作業(yè)調(diào)度的一個次序。所調(diào)度的第一個作業(yè)在時刻0開始，在時刻1完成。第二個作業(yè)在時刻2完成，等等。一個處理器上具有截止期和罰款的單位時間的作業(yè)調(diào)度問題輸入如下：

(1)n個單位時間的作業(yè)集合S={a1,a2,…,an}。

(2)n個整數(shù)截止期d1,d2,…,dn的集合，滿足1≤di≤n，要求作業(yè)ai在di之前完成。

(3)n個非負罰款p1,p2,…,pn，滿足如果作業(yè)ai未在截止期di之前完成，則招致罰款pi，否則不會招致罰款。

引理4.16對于任意作業(yè)集合，以下聲明等價：

(1)集合A是獨立的。

(2)對于t=0,1,2,…,n，有Nt(A)≤t。

(3)如果A中作業(yè)按照截止期單調(diào)遞增的次序調(diào)度，則不存在遲的作業(yè)。

證明：顯然，如果對于某些t，Nt(A)>t，則一定存在遲的作業(yè)被調(diào)度，即不存在沒有遲作業(yè)的調(diào)度。這是因為在時刻t之前，有多于t個作業(yè)要完成。于是，(1)蘊含(2)。如果(2)成立，那么(3)也必然成立，因為(2)蘊含著第i個作業(yè)的最大截止期至多為i，當按照作業(yè)截止期單調(diào)遞增的次序調(diào)度作業(yè)時，不會出現(xiàn)問題。最后，(3)蘊含(1)是平凡的。證畢。利用引理4.16中的性質(zhì)(2)，我們可以容易地計算出給定的作業(yè)集合是否是獨立的。遲作業(yè)的罰款之和最小問題等同于早作業(yè)的罰款之和最大問題。定理4.17保證我們可以利用貪心算法找出具有最大總罰款的作業(yè)獨立集合A。

定理4.17如果S是具有截止期的單位時間作業(yè)集合，設(shè)L表示作業(yè)的所有獨立集的集合，那么，對應(yīng)的系統(tǒng)(S,L)是擬陣。

證明：作業(yè)獨立集的每個子集肯定是獨立的。為了證明交換性質(zhì)，假定B和A是作業(yè)的獨立集，且|B|>|A|。設(shè)k是滿足Nt(B)≤Nt(A)的最大整數(shù)，由于N0(B)=N0(A)=0，這樣的k是存在的。由于Nn(B)=|B|和Nn(A)=|A|，但是|B|>|A|，故必有k<n，且對于所有滿足k+1≤j≤n的j，有Nj(B)>Nj(A)。因此，在截止期k+1時刻，B中所含的作業(yè)數(shù)比A中的多。設(shè)ai是B－A中截止期為k+1的作業(yè)，設(shè)A′=A∪{ai}。利用引理4.16中的性質(zhì)(2)，我們可以證明A′必定是獨立的。對于0≤t≤k，有Nt(A′)=Nt(A)≤t，因為A是獨立的。對于k<t≤n，有Nt(A′)≤Nt(B)≤t，因為B是獨立的。由此，A′是獨立的，因而，(S,L)是擬陣。證畢。由定理4.15，我們可以利用貪心算法找出作業(yè)的最大加權(quán)獨立集A。