貪心算法概述及研討

對(duì)貪心算法的概述和研討福州第一中學(xué)高一（8）班汪濤指導(dǎo)老師：陳穎算法總覽當(dāng)一個(gè)問題具有“最優(yōu)子結(jié)構(gòu)”時(shí)，我們可以采用動(dòng)態(tài)規(guī)劃法解決該問題。但是有的時(shí)候，貪心算法可以更好的處理該類問題?？傮w上看，貪心算法是一種高效的、不穩(wěn)定的算法；但是它在解決問題時(shí)有很多獨(dú)特的優(yōu)良性質(zhì)，掌握貪心算法有時(shí)可以非常迅速的獲得最優(yōu)解或近似最優(yōu)解。關(guān)鍵字：貪心算法（貪婪算法），貪心算法的應(yīng)用舉例，ObjectPascal,快速算法，不穩(wěn)定算法，信息學(xué)奧賽。何時(shí)采用何時(shí)能，又何時(shí)應(yīng)該采用貪心算法呢？一般認(rèn)為，凡是經(jīng)過數(shù)學(xué)歸納法證明可以采用貪心算法的情況，都應(yīng)該采用它。因?yàn)樗男适呛芨叩?。貪心算法的弱點(diǎn)在于它的不穩(wěn)定性，即有時(shí)它不總能返回最優(yōu)解。那么能采用貪心算法的問題具有怎樣的性質(zhì)呢？（何時(shí)采用貪心算法）1、 它具有和動(dòng)態(tài)規(guī)劃問題相似的性質(zhì)，即分治法中的“最優(yōu)子結(jié)構(gòu)”性質(zhì)，即每個(gè)子問題的最優(yōu)解的集合就是整體最優(yōu)解。這是必須的性質(zhì)，因?yàn)樨澬乃惴ń鉀Q的問題流程就需要依序研究每個(gè)子問題，然后綜合之得出最后結(jié)果。不能采用分治法解決的問題，是理論上是不能使用貪心算法的。而且，必須擁有最優(yōu)子結(jié)構(gòu)性質(zhì)，才能保證貪心算法返回最優(yōu)解。2、 它必須具有一種特殊的“貪心選擇性”。這種性質(zhì)類同于“最優(yōu)子結(jié)構(gòu)”性質(zhì)，但又有一些小的差別。我們知道，在動(dòng)態(tài)規(guī)劃中，每一個(gè)父問題結(jié)果的得出需要它的子問題作為條件；但是“貪心選擇性”則不需要；貪心選擇性所做的是一個(gè)非線性的子問題處理過程，即一個(gè)子問題并不依賴于另一個(gè)子問題，但是子問題間有嚴(yán)格的順序性。要證明一個(gè)問題具有“貪心選擇性”，就必須證明每一步所做的貪心選擇最終導(dǎo)致一個(gè)問題的整體最優(yōu)解。這也是必須的性質(zhì)。如果一個(gè)問題具有上述兩個(gè)性質(zhì)，理論上就應(yīng)該采用貪心算法。處理流程經(jīng)由貪心算法處理的問題需要經(jīng)過排序。即把“最貪心”的子結(jié)果排在序列的最前面，一直到“最不貪心的”。這是處理問題的第一步。然后依序解決問題而得出最終結(jié)果。歸納起來，貪心算法處理問題需要下面四步：1、讀入一個(gè)問題2、 進(jìn)行貪心排序3、 處理問題4、綜合結(jié)果并輸出“進(jìn)行貪心排序”和“處理問題”這兩步，是貪心算法的核心部分，甚至能有子問題的重疊和多個(gè)貪心問題的重疊。一般的，經(jīng)過快速排序產(chǎn)生子問題結(jié)果序列的時(shí)間復(fù)雜度為O(nlogn)。應(yīng)用舉例貪心算法所應(yīng)用的問題都具有“最優(yōu)子結(jié)構(gòu)”和“貪心選擇性”。它的應(yīng)用范圍是比較廣泛的。在一些不好解決的問題中，貪心算法也可以被采用從而很方便的得出近似最優(yōu)解。下面是最簡單的例子，主要是為了加深對(duì)算法的應(yīng)用的認(rèn)識(shí)：例1找零錢問題一個(gè)小孩買了價(jià)值少于1美元的糖，并將1美元的錢交給售貨員。售貨員希望用數(shù)目最少的硬幣找給小孩。假設(shè)提供了數(shù)目不限的面值為25美分、10美分、5美分、及1美分的硬幣。售貨員分步驟組成要找的零錢數(shù)，每次加入一個(gè)硬幣。選擇硬幣時(shí)所采用的貪心準(zhǔn)則如下：每一次選擇應(yīng)使零錢數(shù)盡量增大。為保證解法的可行性(即：所給的零錢等于要找的零錢數(shù))，所選擇的硬幣不應(yīng)使零錢總數(shù)超過最終所需的數(shù)目。假設(shè)需要找給小孩67美分，首先入選的是兩枚25美分的硬幣，第三枚入選的不能是25美分的硬幣，否則硬幣的選擇將不可行(零錢總數(shù)超過67美分)，第三枚應(yīng)選擇10美分的硬幣，然后是5美分的，最后加入兩個(gè)1美分的硬幣。貪心算法有種直覺的傾向，在找零錢時(shí)，直覺告訴我們應(yīng)使找出的硬幣數(shù)目最少(至少是接近最少的數(shù)目)?？梢宰C明采用上述貪心算法找零錢時(shí)所用的硬幣數(shù)目的確最少。下面是一個(gè)ObjectPascal語言的例子，為了簡便起見，我們僅保留Form_Create事件中的代碼：procedureTForiri1.FormCreat-e(Sencler:TObject-):var匸o匸曰丄_rvalue,rchangefcur_change「left:i門匚eger;conipletecl:tooolean;begin//Tnput￡'.31-3totai:=100;va1ue:=33;chang已：=□;t-ot-al:=StrToInt-(Input-Box(1Requiredtoinput匸口匚曰 曰日已input-totalint-hefo1lowingt-ext-box:1f11001));value:=StrToInt-(Inpi.it-Box(1RequirEdtoinputvalue1f'Pleaseinput-valueint-hefo1loTijingr.ext.box:1,r1331));//ProcessTn0utputD.31.3completed:=false;repeatleft-:=匸口匚曰丄-value-change;ifleft.<=0thencomple匸已匸1:=r.rueelseifleft.>=25thencur_change:=25elseif丄已ft>=10thencur_change:=10elseiflef匸>=5thencur_cliatige:=5elseifleft.>=1thencur_cliang已：=1;ifnotcompletedthenbeginchange:=chang已+cur_cliatige;ShoTiTMessage(Int.ToStr(cur_cliange)：i;end;untilcornplet.eel;App1i匚日匸i□口■T已rniinat-e;end;上面的程序運(yùn)行結(jié)果如下圖：

輸入Total和Value以后，程序?qū)⒔o出數(shù)個(gè)MessageBox，給出找錢的方案。由于這個(gè)程序的硬幣面值是給定的，所以無須排序的操作。但是仔細(xì)看程序會(huì)發(fā)現(xiàn)，其中判斷找錢的順序是由大面額到小面額的，這就是貪心算法的核心；上面程序中的暗紅色框中的代碼段就是。本題中的硬幣面值實(shí)際上具有特殊性，詳細(xì)說明請參閱“深入探討”一節(jié)。例2機(jī)器調(diào)度問題現(xiàn)有n件任務(wù)和無限多臺(tái)的機(jī)器，任務(wù)可以在機(jī)器上得到處理。每件任務(wù)的開始時(shí)間為si，完成時(shí)間為fi，si<fi。[si,fi]為處理任務(wù)i的時(shí)間范圍。兩個(gè)任務(wù)i,j沖突是指兩個(gè)任務(wù)的時(shí)間范圍區(qū)間有重疊，而并非是指i,j的起點(diǎn)或終點(diǎn)重合。例如：區(qū)間（1，4）與區(qū)間（2，4）重疊，而與區(qū)間（4，7）不重疊。一個(gè)可行的任務(wù)分配是指在分配中沒有兩件重疊的任務(wù)分配給同一臺(tái)機(jī)器。因此，在可行的分配中每臺(tái)機(jī)器在任何時(shí)刻最多只處理一個(gè)任務(wù)。最優(yōu)分配是指使用的機(jī)器最少的可行分配方案。一種獲得最優(yōu)分配的貪心方法是逐步分配任務(wù)。每步分配一件任務(wù)，且按任務(wù)開始時(shí)間的非遞減次序進(jìn)行分配。若已經(jīng)至少有一件任務(wù)分配給某臺(tái)機(jī)器，則稱這臺(tái)機(jī)器是舊的；若機(jī)器非舊，則它是新的。在選擇機(jī)器時(shí)，采用以下貪心準(zhǔn)則：根據(jù)欲分配任務(wù)的開始時(shí)間，若此時(shí)有舊的機(jī)器可用，則將任務(wù)分給舊的機(jī)器。否則，將任務(wù)分配給一臺(tái)新的機(jī)器。上述貪心算法能導(dǎo)致最優(yōu)機(jī)器分配的證明；可按如下方式實(shí)現(xiàn)一個(gè)復(fù)雜性為O（nlogn）的貪心算法：首先采用一個(gè)復(fù)雜性為0（nlogn）的排序算法（如堆排序）按si的遞增次序排列各個(gè)任務(wù)，然后找出一個(gè)關(guān)于舊機(jī)器可用時(shí)間的最小堆。簡單的說，就是先按排序任務(wù)，然后盡可能的用舊機(jī)器。下面是一個(gè)ObjectPascal語言的例子；為了簡便，假設(shè)用戶輸入的數(shù)據(jù)已經(jīng)按si的遞增次序排序過了。首先來看看程序運(yùn)行效果。程序還會(huì)依次提示用戶輸入每個(gè)任務(wù)的開始時(shí)間點(diǎn)和結(jié)束點(diǎn)。下面是程序的代碼，同樣為了簡便，僅保留Form_Create事件的代碼：procedureTFonn1?F□匸mC匸已曰匸已1：￡已口匚1已匸：TObject.);variriissicn:array[1??1匚i□□』：!.??2]ofinteger;比|_|二匸|口門匸』i,j,rk,cur_i[iachine:integer;machine:array[1??1匚i匚i匚i』1??1000]ofIjuulean;availszLljle.rdist.ribut.ed.rpreinc:boulean;begin//InputDataMessageDlg(availszLljle.rdist.ribut.ed.rpreinc:boulean;begin//InputDataMessageDlg(1Thefulluwingdat.ayouinput-eclrnust.nit.Infijrniat.i□n』[nfciOK],u：i;iri_cuunt.:=St.rTuInt.(Input.Bcxi：1Requiredt.□input.1Pleaseinput.t.hefori:=1toni_c□unt.beginrnissiun[「1] :=1Pleaseinputrnissiun[「2] :=1Pleaseinput.end;}jesort,bytheirstart,puint.s?t.hem.urfcierufinissicns1』m.uriljerufinissions1』1101：i：i;doSt.rTuInt.(Input.Boxi：1Requiredthestartpoint,ofitiissiun1St.rTuInt.(Input.Boxi：1Requiredtheendpoint,ufrnissiun1+t.uinput,start,point.1,+IntToStr(i),1l1));t.uinput,endpuint.1fInt.ToSt.ri：i),121));//Znitr22P-L?CC655cur_i[iachine:=1;preinc:=false;fori:=1toluuudoforj:=1to1UUUdomachine[i,rj]:=true;fori:=1toiri_.dobeginifpreinctheninci：cur_i[iachine：i;clist.rilji.it.ed:=false;preinc:=false;forj:=1tocur_i[iachinedobeginifnotdist.ribut.edthenbeginavail；5i}jle:=t.rue;fork:=rnissiun[i,r1]tornissiun[1,2]doifmachine[j,k]=falsethenavail；5i}jle:=false;ifavai丄曰上11ethenfork:=(rnissiun[i,r1] +1)to(rnissiunEi,r2]一1)dobeginrnachine[i.rk]:=false;clist.ribut.ed:=t.rue;endelseif(j=cur_ttiachine)thenbecjinpreinc:=true;fork:=(i[ii33iun[i,1] +1)to(niissiunE1,2]一1)domachine[1+l.rk]:=false;end;end;end;end;//OutputD.31-3ShuTijMessage(Int.ToSt.r(cur_i[iachinej：i;Applicat.ion?Terrninat.e;end;end?上面程序中，最后將用MessageBox輸出需要的最少機(jī)器數(shù)量。其實(shí)考察二維數(shù)組machine還可以了解到每臺(tái)機(jī)器的工作和非工作的時(shí)間段。在本文的附件中，您可以找到由本文作者編寫的上述程序的完整源代碼，作為參考。上述應(yīng)用舉例程序在Windows2000，Delphi7.0Build4.453下測試通過。深入探討貪心算法最優(yōu)解問題一直是備受程序員們的關(guān)注的。到底什么時(shí)候可以獲得最優(yōu)解，目前似乎也只能針對(duì)具體的問題進(jìn)行歸納討論得出結(jié)果。一般性的結(jié)果也只能參照貪心問題的兩個(gè)性質(zhì)來推測了。通過研究許多適合采用貪心算法的例子，我們提出這樣一個(gè)假設(shè)：具有應(yīng)當(dāng)采用貪心算法的問題，當(dāng)“貪心序列”中的每項(xiàng)互異且當(dāng)問題沒有重疊性時(shí)，看起來總能通過貪心算法取得（近似）最優(yōu)解的?；蛘撸傆幸环N直覺在引導(dǎo)我們對(duì)一些問題采用貪心算法。在剛才應(yīng)用舉例中的“找零錢”問題就是一個(gè)例子。題中給出的硬幣面值事實(shí)上具有特殊性，如果面值發(fā)生變化，可能貪心算法就不能返回最優(yōu)解了。但是，值得指出的是，當(dāng)一個(gè)問題具有多個(gè)最優(yōu)解時(shí)，貪心算法并不能求出所有最優(yōu)解。上述兩個(gè)問題只需要一個(gè)很簡單的例子就能證明。比如說我們要用一些代表體積的液體填充一個(gè)箱子，怎樣才能使剩余空間最??？箱子容積已知。第一個(gè)假設(shè)，就是“貪心序列”的互異性，當(dāng)我們的容積是4，而液體的體積分別是3，2，2時(shí)，按貪心算法我們一定會(huì)取3，然后就不能再取任何其它液體了。但是取2，2才是最優(yōu)解。但是如果去掉相同的2中的其中一個(gè)，就能取得最優(yōu)解了。因?yàn)橹蝗∫粋€(gè)2不是最優(yōu)解；而取3才是最優(yōu)的。這是一個(gè)簡單的例子，也只是在證明我們剛剛提出的假說；至于假說的正確性還有待進(jìn)一步證明。但是作為一種直覺，對(duì)我們解決問題應(yīng)該是有幫助的。第二個(gè)假設(shè)，就是貪心算法能否取得全部最優(yōu)解的問題，也舉與證明第一個(gè)假設(shè)相同的例子，比如容積是8，而液體的體積分別是5，4，3，1的情況。貪心算法會(huì)取的是5，3從而取得其中一個(gè)最優(yōu)解。但是取4，3，1也能得到另一個(gè)最優(yōu)解。但是，這類問題有時(shí)可以通過產(chǎn)生貪心序列的變式（在本例中是截取其中的一個(gè)部分）來解決。另外，我們經(jīng)過實(shí)踐發(fā)現(xiàn)，單純的貪心算法是順序處理問題的；而且每個(gè)結(jié)果是可以在處理完一個(gè)數(shù)據(jù)后即時(shí)輸出的。最后我們來討論一下貪心算法返回最優(yōu)解的情況。注意這里我們說的最優(yōu)解不含近似最優(yōu)解；也就是說，怎樣具體來詮釋貪心算法的兩個(gè)性質(zhì)。雖然在很多時(shí)候解決問題時(shí)程序員會(huì)毫不猶豫的采用貪心算法而并不總是考慮它返回的是否最優(yōu)解，因?yàn)楹芏鄷r(shí)候近似最優(yōu)解已經(jīng)夠他們用了。程序員更愿意把精力花在其他程序完善上也不會(huì)把大量時(shí)間花費(fèi)在計(jì)算貪心算法的局限性上。但是信息學(xué)奧賽中的一些題目是明確要求最優(yōu)解的，因此在此我們就再多花一些時(shí)間來研究貪心算法的完全最優(yōu)解問題。但是對(duì)于絕大多數(shù)程序員來說，研究這個(gè)問題是沒有必要的。首先我們從找零錢的例子可以觀察到