一．貪心算法的基本概念

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

二．求解活動(dòng)安排問(wèn)題算法

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

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

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

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來(lái)存儲(chǔ)所選擇的活動(dòng)?；顒?dòng)i在集合a中，當(dāng)且僅當(dāng)a[i]的值為true。變量j用以記錄最近一次加入到a中的活動(dòng)。由于輸入的活動(dòng)是按其結(jié)束時(shí)間的非減序排列的，f_j總是當(dāng)前集合a中所有活動(dòng)的最大結(jié)束時(shí)間，即：

     

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

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

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

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的計(jì)算過(guò)程如圖所示。

 

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

三．算法分析

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

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

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

四．貪心算法的基本要素

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

    對(duì)于一個(gè)具體的問(wèn)題，我們?cè)趺粗朗欠窨捎秘澬乃惴▉?lái)解此問(wèn)題，以及能否得到問(wèn)題的一個(gè)最優(yōu)解呢?這個(gè)問(wèn)題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問(wèn)題中

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

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

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

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

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

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

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

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

五． ０－背包問(wèn)題

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

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

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

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

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

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

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

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

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

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

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

 

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