一．貪心算法的基本概念

    當(dāng)一個問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)時，我們會想到用動態(tài)規(guī)劃法去解它。但有時會有更簡單有效的算法。我們來看一個找硬幣的例子。假設(shè)有四種硬幣，它們的面值分別為二角五分、一角、五分和一分?，F(xiàn)在要找給某顧客六角三分錢。這時，我們會不假思索地拿出2個二角五分的硬幣，1個一角的硬幣和3個一分的硬幣交給顧客。這種找硬幣方法與其他的找法相比，所拿出的硬幣個數(shù)是最少的。這里，我們下意識地使用了這樣的找硬幣算法：首先選出一個面值不超過六角三分的最大硬幣，即二角五分；然后從六角三分中減去二角五分，剩下三角八分；再選出一個面值不超過三角八分的最大硬幣，即又一個二角五分，如此一直做下去。這個找硬幣的方法實際上就是貪心算法。顧名思義，貪心算法總是作出在當(dāng)前看來是最好的選擇。也就是說貪心算法并不從整體最優(yōu)上加以考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，我們希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。上面所說的找硬幣算法得到的結(jié)果就是一個整體最優(yōu)解。找硬幣問題本身具有最優(yōu)子結(jié)構(gòu)性質(zhì)，它可以用動態(tài)規(guī)劃算法來解。但我們看到，用貪心算法更簡單，更直接且解題效率更高。這利用了問題本身的一些特性。例如，上述找硬幣的算法利用了硬幣面值的特殊性。如果硬幣的面值改為一分、五分和一角一分3種，而要找給顧客的是一角五分錢。還用貪心算法，我們將找給顧客1個一角一分的硬幣和4個一分的硬幣。然而3個五分的硬幣顯然是最好的找法。雖然貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當(dāng)廣的許多問題它能產(chǎn)生整體最優(yōu)解。如圖的單源最短路徑問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，但其最終結(jié)果卻是最優(yōu)解的很好的近似解。

二．求解活動安排問題算法

    活動安排問題是可以用貪心算法有效求解的一個很好的例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。

    設(shè)有n個活動的集合e={1，2，…，n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結(jié)束時間f_i,且s_i<f_i。如果選擇了活動i，則它在半開時間區(qū)間[s_i，f_i]內(nèi)占用資源。若區(qū)間[s_i，f_i]與區(qū)間[s_j，f_j]不相交，則稱活動i與活動j是相容的。也就是說，當(dāng)s_i≥fi或s_j≥f_j時，活動i與活動j相容?；顒影才艈栴}就是要在所給的活動集合中選出最大的相容活動子集合。

    在下面所給出的解活動安排問題的貪心算法gpeedyselector中，各活動的起始時間和結(jié)束時間存儲于數(shù)組s和f{中且按結(jié)束時間的非減序：．f1≤f2≤…≤fn排列。如果所給出的活動未按此序排列，我們可以用o(nlogn)的時間將它重排。

template< class type>

void greedyselector(int n, type s[ 1, type f[ ], bool a[ ] ]

 { a[ 1 ] = true;

 int j = 1;

 for (int i=2;i< =n;i+ + ) {

     if (s[i]>=f[j]) {

        a[i] = true;

        j=i;

}

else a[i]= false;

}

}

    算法greedyselector中用集合a來存儲所選擇的活動。活動i在集合a中，當(dāng)且僅當(dāng)a[i]的值為true。變量j用以記錄最近一次加入到a中的活動。由于輸入的活動是按其結(jié)束時間的非減序排列的，f_j總是當(dāng)前集合a中所有活動的最大結(jié)束時間，即：

     

    貪心算法greedyselector一開始選擇活動1，并將j初始化為1。然后依次檢查活動i是否與當(dāng)前已選擇的所有活動相容。若相容則將活動i加人到已選擇活動的集合a中，否則不選擇活動i，而繼續(xù)檢查下一活動與集合a中活動的相容性。由于f_i

總是當(dāng)前集合a中所有活動的最大結(jié)束時間，故活動i與當(dāng)前集合a中所有活動相容的充分且必要的條件是其開始時間s 不早于最近加入集合a中的活動j的結(jié)束時間f_j，s_i≥f_j。若活動i與之相容，則i成為最近加人集合a中的活動，因而取代活動j的位置。由于輸人的活動是以其完成時間的非減序排列的，所以算法greedyselector每次總是選擇具有最早完成時間的相容活動加入集合a中。直觀上按這種方法選擇相容活動就為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時間段極大化，以便安排盡可能多的相容活動。算法greedyselector的效率極高。當(dāng)輸人的活動已按結(jié)束時間的非減序排列，算法只需g(n)的時間來安排n個活動，使最多的活動能相容地使用公共資源。

例：設(shè)待安排的11個活動的開始時間和結(jié)束時間按結(jié)束時間的非減序排列如下：

i	1	2	3	4	5	6	7	8	9	10	11
s[i]	1	3	0	5	3	5	6	8	8	2	12
f[i]	4	5	6	7	8	9	10	11	12	13	14

 

算法greedyselector的計算過程如圖所示。

 

    圖中每行相應(yīng)于算法的一次迭代。陰影長條表示的活動是已選人集合a中的活動，而空白長條表示的活動是當(dāng)前正在檢查其相容性的活動。若被檢查的活動i的開始時間s_i小于最近選擇的活動了的結(jié)束時間f_j，則不選擇活動i，否則選擇活動i加入集合a中。

三．算法分析

    貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題，貪心算法greedyse—1ector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合a的規(guī)模最大。我們可以用數(shù)學(xué)歸納法來證明這個結(jié)論。

    事實上，設(shè)e={1，2，…，n}為所給的活動集合。由于正中活動按結(jié)束時間的非減序排列，故活動1具有最早的完成時間。首先我們要證明活動安排問題有一個最優(yōu)解以貪心選擇開始，即該最優(yōu)解中包含活動1。設(shè) 是所給的活動安排問題的一個最優(yōu)解，且a中活動也按結(jié)束時間非減序排列，a中的第一個活動是活動k。若k=1，則a就是一個以貪心選擇開始的最優(yōu)解。若k>1，則我們設(shè) 。由于f1≤f_k，且a中活動是互為相容的，故b中的活動也是互為相容的。又由于b中活動個數(shù)與a中活動個數(shù)相同，且a是最優(yōu)的，故b也是最優(yōu)的。也就是說b是一個以貪心選擇活動1開始的最優(yōu)活動安排。因此，我們證明了總存在一個以貪心選擇開始的最優(yōu)活動安排方案。

    進一步，在作了貪心選擇，即選擇了活動1后，原問題就簡化為對e中所有與活動1相容的活動進行活動安排的子問題。即若a是原問題的一個最優(yōu)解，則a’=a—{i}是活動安排問題 的一個最優(yōu)解。事實上，如果我們能找到e’的一個解b’，它包含比a’更多的活動，則將活動1加入到b’中將產(chǎn)生e的一個解b，它包含比a更多的活動。這與a的最優(yōu)性矛盾。因此，每一步所作的貪心選擇都將問題簡化為一個更小的與原問題具有相同形式的子問題。對貪心選擇次數(shù)用數(shù)學(xué)歸納法即知，貪心算法greedyselector最終產(chǎn)生原問題的一個最優(yōu)解。

四．貪心算法的基本要素

    貪心算法通過一系列的選擇來得到一個問題的解。它所作的每一個選擇都是當(dāng)前狀態(tài)下某種意義的最好選擇，即貪心選擇。希望通過每次所作的貪心選擇導(dǎo)致最終結(jié)果是問題的一個最優(yōu)解。這種啟發(fā)式的策略并不總能奏效，然而在許多情況下確能達(dá)到預(yù)期的目的。解活動安排問題的貪心算法就是一個例子。下面我們著重討論可以用貪心算法求解的問題的一般特征。

    對于一個具體的問題，我們怎么知道是否可用貪心算法來解此問題，以及能否得到問題的一個最優(yōu)解呢?這個問題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問題中

我們看到它們一般具有兩個重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。

1．貪心選擇性質(zhì)

    所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。在動態(tài)規(guī)劃算法中，每步所作的選擇往往依賴于相關(guān)子問題的解。因而只有在解出相關(guān)子問題后，才能作出選擇。而在貪心算法中，僅在當(dāng)前狀態(tài)下作出最好選擇，即局部最優(yōu)選擇。然后再去解作出這個選擇后產(chǎn)生的相應(yīng)的子問題。貪心算法所作的貪心選擇可以依賴于以往所作過的選擇，但決不依賴于將來所作的選擇，也不依賴于子問題的解。正是由于這種差別，動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行,以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為一個規(guī)模更小的子問題。

對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，我們必須證明每一步所作的貪心選擇最終導(dǎo)致問題的一個整體最優(yōu)解。通常可以用我們在證明活動安排問題的貪心選擇性質(zhì)時所采用的方法來證明。首先考察問題的一個整體最優(yōu)解，并證明可修改這個最優(yōu)解，使其以貪心選擇開始。而且作了貪心選擇后，原問題簡化為一個規(guī)模更小的類似子問題。然后，用數(shù)學(xué)歸納法證明，通過每一步作貪心選擇，最終可得到問題的一個整體最優(yōu)解。其中，證明貪心選擇后的問題簡化為規(guī)模更小的類似子問題的關(guān)鍵在于利用該問題的最優(yōu)子結(jié)構(gòu)性質(zhì)。

2．最優(yōu)子結(jié)構(gòu)性質(zhì)

    當(dāng)一個問題的最優(yōu)解包含著它的子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題所具有的這個性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的一個關(guān)鍵特征。在活動安排問題中，其最優(yōu)子結(jié)構(gòu)性質(zhì)表現(xiàn)為：若a是對于正的活動安排問題包含活動1的一個最優(yōu)解,則相容活動集合a’=a—{1}是對于e’={i∈e:s_i≥f₁}的活動安排問題的一個最優(yōu)解。

3．貪心算法與動態(tài)規(guī)劃算法的差異

    貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是兩類算法的一個共同點。但是，對于一個具有最優(yōu)子結(jié)構(gòu)的問題應(yīng)該選用貪心算法還是動態(tài)規(guī)劃算法來求解?是不是能用動態(tài)規(guī)劃算法求解的問題也能用貪心算法來求解?下面我們來研究兩個經(jīng)典的組合優(yōu)化問題，并以此來說明貪心算法與動態(tài)規(guī)劃算法的主要差別。

五． ０－背包問題

給定n種物品和一個背包。物品i的重量是w ，其價值為v ，背包的容量為c.問應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價值最大? 在選擇裝入背包的物品時，對每種物品i只有兩種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。

    此問題的形式化描述是，給定c>0，w_i>0，v_i>0，1≤i≤n，要求找出一個n元0—1向

量(xl，x2，…，x_n)， ，使得 ≤c，而且 達(dá)到最大。

      背包問題：與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包。

    此問題的形式化描述是，給定c>0，w_i>0，v_i>0，1≤i≤n，要求找出一個n元向量

(x1,x2,...x_n)，0≤x_i≤1，1≤i≤n 使得 ≤c，而且 達(dá)到最大。

    這兩類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)。對于0—1背包問題，設(shè)a是能夠裝入容量為c的背包的具有最大價值的物品集合，則a_j=a-{j}是n-1個物品1，2，…，j—1，j+1，…，n可裝入容量為c-w_i叫的背包的具有最大價值的物品集合。對于背包問題，類似地，若它的一個最優(yōu)解包含物品j，則從該最優(yōu)解中拿出所含的物品j的那部分重量w_i，剩余的將是n-1個原重物品1，2，…，j-1，j+1，…，n以及重為w_j-w_i的物品j中可裝入容量為c-w的背包且具有最大價值的物品。

    雖然這兩個問題極為相似，但背包問題可以用貪心算法求解，而0·1背包問題卻不能用貪心算法求解。用貪心算法解背包問題的基本步驟是，首先計算每種物品單位重量的價值

v_j／w_i然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過c，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直進行下去直到背包裝滿為止。具體算法可描述如下：

 void knapsack(int n, float m, float v[ ], float w[ ], float x[ ] )

 sort(n,v,w);

 int i;

 for(i= 1;i<= n;i++) x[i] = o;

 float c = m;

 for (i = 1;i < = n;i ++) {

     if (w[i] > c) break;

    x[i] = 1;

    c-= w[i];

    }

 if (i < = n) x[i] = c/w[i];

} 

算法knapsack的主要計算時間在于將各種物品依其單位重量的價值從大到小排序。因此，算法的計算時間上界為o(nlogn)。當(dāng)然，為了證明算法的正確性，我們還必須證明背包問題具有貪心選擇性質(zhì)。 

這種貪心選擇策略對0—1背包問題就不適用了?？磮D2(a)中的例子，背包的容量為50千克；物品1重10千克；價值60元；物品2重20千克，價值100元；物品3重30千克；價值120元。因此，物品1每千克價值6元，物品2每千克價值5元，物品3每千克價值4元。若依貪心選擇策略，應(yīng)首選物品1裝入背包，然而從圖4—2(b)的各種情況可以看出，最優(yōu)的選擇方案是選擇物品2和物品3裝入背包。首選物品1的兩種方案都不是最優(yōu)的。對于背包問題，貪心選擇最終可得到最優(yōu)解，其選擇方案如圖2(c)所示。

 

    對于0—1背包問題，貪心選擇之所以不能得到最優(yōu)解是因為它無法保證最終能將背包裝滿，部分背包空間的閑置使每千克背包空間所具有的價值降低了。事實上，在考慮0—1背包問題的物品選擇時，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終結(jié)果，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的于問題。這正是該問題可用動態(tài)規(guī)劃算法求解的另一重要特征。動態(tài)規(guī)劃算法的確可以有效地解0—1背包問題。