1、貪心算法淺析摘 要：本文講述了貪心算法的基本思路及實(shí)現(xiàn)過程，貪心算法的特點(diǎn)、存在的問題以及應(yīng)用。并通過貪心算法的特點(diǎn)舉例列出了幾個(gè)經(jīng)典問題，通過對(duì)問題的探討和研究，對(duì)貪心算法有了更加深入的了解。關(guān)鍵詞：貪心算法；最優(yōu)解；最優(yōu)子結(jié)構(gòu)問題；刪數(shù)問題；活動(dòng)安排問題貪心算法的基本思路及實(shí)現(xiàn)過程1 貪心的基本思想用局部解構(gòu)造全局解，即從問題的某一個(gè)初始解逐步逼近給定的目標(biāo)，以盡可能快地求得更好的解。當(dāng)某個(gè)算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。貪心算法思想的本質(zhì)就是分治，或者說：分治是貪心的基礎(chǔ)。每次都形成局部最優(yōu)解，換一種方法說，就是每次都處理出一個(gè)最好的方案。利用貪心策略解題，需要解決兩個(gè)問題：（

2、1）該題是否適合于用貪心策略求解；（2）如何選擇貪心標(biāo)準(zhǔn)，以得到問題的最優(yōu)/較優(yōu)解。2貪心算法的實(shí)現(xiàn)過程（1）應(yīng)用同一規(guī)則F，將原問題變?yōu)橐粋€(gè)相似的、但規(guī)模更小的子問題；（2）從問題的某一初始解出發(fā)：While（能朝給定目標(biāo)前進(jìn)一步） 求出可行解的一個(gè)解元素；（3）由所有解元素組合成問題的一個(gè)可行解。貪心算法的特點(diǎn)貪心算法的最大特點(diǎn)就是快，通常是線性二次式，不需要多少額外的內(nèi)存。一般二次方級(jí)的存儲(chǔ)要浪費(fèi)額外的空間，而且那些空間經(jīng)常得不出正解。但是，使用貪心算法時(shí)，這些空間可以幫助算法更容易實(shí)現(xiàn)且更快執(zhí)行。如果有正確貪心性質(zhì)存在，那么一定要采用。因?yàn)樗菀拙帉懀菀渍{(diào)試，速度極快，并且節(jié)約空間。

3、幾乎可以說，此時(shí)它是所有算法中最好的。但是應(yīng)該注意，貪心算法有兩大難點(diǎn)：（1）如何貪心怎樣用一個(gè)小規(guī)模的解構(gòu)造更大規(guī)模的解呢?總體上，這與問題本身有關(guān)。但是大部分都是有規(guī)律的。正因?yàn)樨澬挠腥绱诵再|(zhì)，它才能比其他算法快。具有應(yīng)當(dāng)采用貪心算法的問題，當(dāng)“貪心序列”中的每項(xiàng)互異且當(dāng)問題沒有重疊性時(shí)，看起來總能通過貪心算法取得（近似）最優(yōu)解的。或者，總有一種直覺在引導(dǎo)我們對(duì)一些問題采用貪心算法。其中“找零錢”這個(gè)問題就是一個(gè)例子。題中給出的硬幣面值事實(shí)上具有特殊性，如果面值發(fā)生變化，可能貪心算法就不能返回最優(yōu)解了。但是，值得指出的是，當(dāng)一個(gè)問題具有多個(gè)最優(yōu)解時(shí)，貪心算法并不能求出所有最優(yōu)解。另外，我們

4、經(jīng)過實(shí)踐發(fā)現(xiàn)，單純的貪心算法是順序處理問題的；而且每個(gè)結(jié)果是可以在處理完一個(gè)數(shù)據(jù)后即時(shí)輸出的。（2）貪心的正確性要證明貪心性質(zhì)的正確性，才是貪心算法的真正挑戰(zhàn)，因?yàn)椴⒉皇敲看尉植孔顑?yōu)解都會(huì)與整體最優(yōu)解之間有聯(lián)系，往往靠貪心算法生成的解不是最優(yōu)解。這樣，貪心性質(zhì)的證明就成了貪心算法正確的關(guān)鍵。對(duì)某些問題貪心性質(zhì)也許是錯(cuò)的，即使它在大部分?jǐn)?shù)據(jù)中都是可行的，但還必須考慮到所有可能出現(xiàn)的特殊情況，并證明該貪心性質(zhì)在這些特殊情況中仍然正確。而這樣容易陷入證明不正確貪心性質(zhì)的泥塘中無法自拔，因?yàn)樨澬乃惴ǖ倪m用范圍并不大，而且有一部分極難證明，若是沒有把握，最好不要冒險(xiǎn)，還有其他算法會(huì)比它要保險(xiǎn)。貪心算法存

5、在的問題（1）不能保證求得的最后解是最佳的。由于貪心策略總是采用從局部看來是最優(yōu)的選擇，因此并不從整體上加以考慮；（2）貪心算法只能用來求某些最大或最小解的問題；（3）貪心算法只能確定某些問題的可行性范圍貪心算法的應(yīng)用1哈夫曼編碼2 0-1背包問題3磁盤文件的存儲(chǔ)4生產(chǎn)調(diào)度問題5信息查詢貪心算法經(jīng)典應(yīng)用舉例刪數(shù)問題問題提出：給定n位正整數(shù)a，去掉其中任意k<=n個(gè)數(shù)字后，剩下的數(shù)字按原次序排列組成一個(gè)新的正整數(shù)。對(duì)于給定的n位正整數(shù)a和正整數(shù)k，設(shè)計(jì)一個(gè)算法找出剩下數(shù)字組成的新數(shù)最小的刪數(shù)方案。分析：n位數(shù)a可表示為x1x2xixjxkxn，要?jiǎng)h去k位數(shù)，使得剩下的數(shù)字組成的整數(shù)最小。設(shè)

6、本問題為T，其最優(yōu)解A=(y1，y2yk)表示依次刪去的k個(gè)數(shù)，在刪去k個(gè)數(shù)后剩下的數(shù)字按原次序排成的新數(shù)。即最優(yōu)值記為TA。 本問題采用貪心算法求解，采用最近下降點(diǎn)優(yōu)先的貪心策略：即x1<x2<<xi<xj；如果xk<xj，則刪去xj，即得到一個(gè)新的數(shù)且這個(gè)數(shù)為n一1位中為最小的數(shù)Nl，可表示為x1x2xixkxmxn。對(duì)N1而言，即刪去了1位數(shù)后，原問題T變成了需對(duì)n-1位數(shù)刪去k-1個(gè)數(shù)新問題T。新問題和原問題相同，只是問題規(guī)模由n減小為n-1，刪去的數(shù)字個(gè)數(shù)由k減少為k-1。基于此種刪除策略，對(duì)新問題T，選擇最近下降點(diǎn)的數(shù)進(jìn)行刪除，如此進(jìn)行下去，直至刪去k

7、個(gè)數(shù)為止。證明：先來證明該問題具有貪心選擇性質(zhì)，即對(duì)問題T刪除最近下降點(diǎn)的數(shù)xj后得到的N1是n一1位數(shù)是中最小的數(shù)。 根據(jù)數(shù)的進(jìn)制特點(diǎn)，對(duì)a按權(quán)展開得： a=x1*10n-1+x2*10n-2+xi*10n-i+xj*10n-j+xk*10n-k+xn 則有：Nl=x1*10n-2+x2*10n-3+xi*10n-i-1+xk*10n-k+xn假設(shè)刪去的不是xj而是其它位，則有N2=x1*10n-2+x2*10n-3+xi*10n-i-1+xj*10n-k+xn因?yàn)橛衳1<x2<<xi<xj且xj>xk，則有Nl<N2。 因此刪數(shù)問題滿足貪心選擇性質(zhì)。 刪

8、數(shù)問題的C+代碼：#include<iostream> #include <string> using namespace std; int main() string n; int s,i,x,l,m; printf("請(qǐng)輸入一個(gè)正整數(shù)和將要?jiǎng)h去的個(gè)數(shù)!n"); while(cin>>n>>s) i=-1,m=0,x=0; l=n.length(); while(x<s&&m=0) i+; if(ni>ni+1)/出現(xiàn)遞減,刪除遞減的首數(shù)字 n=n.erase(i,1); x+;/ x統(tǒng)計(jì)刪除數(shù)字

9、的個(gè)數(shù) i=-1;/從頭開始查遞減區(qū)間 if(i=l-x-2&&x<s) m=1;/已經(jīng)無遞減區(qū)間,m=1脫離循環(huán) printf("最后結(jié)果為:n"); cout<<n.substr(0,l-s+x);/只打印剩下的左邊l-(s-x)個(gè)數(shù)字 問題的最優(yōu)子結(jié)構(gòu)性質(zhì)在進(jìn)行了貪心選擇后，原問題T就變成了對(duì)N1如何刪去k-1個(gè)數(shù)的問題T，是原問題的子問題。若A=(xj，A)是原問題T的最優(yōu)解，則A是子問題T的最優(yōu)解，其最優(yōu)值為TA。 證明：假設(shè)A不是子問題T的最優(yōu)解，其子問題的最優(yōu)解為B，其最優(yōu)值記為TB，則有TB<TA。而根據(jù)TA的定義可知

10、：TA= TA+xj*1On-j，而TB<TA，因此有TB+xj*1On-j<TA+xj*1On-j=TA。即存在一個(gè)由數(shù)a刪去1位數(shù)后得到的n-1位數(shù)比最優(yōu)值TA更小。這與TA為問題T的最優(yōu)值相矛盾。因此，A是子問題T的最優(yōu)值。 因此，刪數(shù)問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。 從以上貪心選擇及最優(yōu)子結(jié)構(gòu)性質(zhì)的證明可知?jiǎng)h數(shù)問題用貪心算法可以求得最優(yōu)解。活動(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í)間Fi，且Si<Fi。如果選擇了活動(dòng)i

11、，則它在半開時(shí)間區(qū)間Si,Fi)內(nèi)占用資源。若區(qū)間Si,Fi)與區(qū)間Sj，F(xiàn)j）不相交，則稱活動(dòng)i與活動(dòng)j是相容的。也就是說Si>=Fj或Sj>=Fi時(shí)，活動(dòng)i與活動(dòng)j相容。活動(dòng)安排問題就是要在所給的活動(dòng)集合中選擇出最大的相容活動(dòng)子集合。證明：這個(gè)問題可以使用貪心算法進(jìn)行求解。其實(shí)這個(gè)問題的關(guān)鍵并不是如何用貪心算法求解，而是如何證明這個(gè)問題可以用貪心算法求解。鑒于證明的復(fù)雜性，還是不在此討論證明問題。其實(shí)貪心算法問題的證明無非都是用數(shù)學(xué)歸納法證明，不錯(cuò)就是那個(gè)傳說中萬能證明法，數(shù)學(xué)歸納法。還是直接討論實(shí)現(xiàn)過程吧。實(shí)現(xiàn)：首先將活動(dòng)按照活動(dòng)的結(jié)束時(shí)間非遞減：F1<=F2<=

12、.<=Fn排序。如果所給的活動(dòng)未排序，則先將活動(dòng)按此序排列，時(shí)間復(fù)雜度一般為O(nlogn)可解決。以下是解決問題的算法。 1 /貪心算法-活動(dòng)安排的實(shí)現(xiàn) 2 3 #include "stdafx.h" 4 #include "stdio.h" 5 6 template<class Type> 7 void GreedySelector(int n,Type s,Type f,bool A) 8 9 A0=1; /第一個(gè)直接選取10 int j=0;11 for(int i=1;i<n;i+)12 13 if(si>=fj)

13、Ai=true;j=i; /如果第i+1的活動(dòng)的開始時(shí)間大于或等于第i個(gè)活動(dòng)的結(jié)束時(shí)間，則標(biāo)記該活動(dòng)14 else Ai=false;15 16 17 18 int _tmain(int argc, _TCHAR* argv)19 20 /初始化數(shù)據(jù)21 int n=3;22 int s3=1,2,4; /開始時(shí)間23 int f3=3,3,5; /結(jié)束時(shí)間24 bool A3=0,0,0; /數(shù)組A用于標(biāo)記是否選擇活動(dòng)，1表示選擇，0表示不選擇25 26 GreedySelector<int>(n,s,f,A);27 for(int i=0;i<n;i+)28 29 pri

14、ntf("%dn",Ai);30 31 該算法的貪心選擇的意義是使剩余的可安排的時(shí)間段極大化，以便安排盡可能多的相容活動(dòng)。也就是說，每次選擇完了之后，保證這次的選擇之后留下的時(shí)間是最多的。時(shí)間復(fù)雜度：GreedySelector算法效率極高。當(dāng)輸入的數(shù)據(jù)是已經(jīng)按照結(jié)束時(shí)間非遞減排序好的時(shí)候，算法只需要O(n)的時(shí)間安排n個(gè)活動(dòng)，使最多的活動(dòng)能相容地使用公共資源。總結(jié)貪心算法是很常見的算法，貪心策略是最接近人的日常思維的一種解題策略，雖然它不能保證求得的最后解一定是最佳的，但是它可以為某些問題確定一個(gè)可行性范圍。貪心算法所作的選擇依賴于以往所作過的選擇，但決不依賴于將來的選擇，這使得算法在編碼和執(zhí)行過程中都有一定的速度優(yōu)勢(shì)。對(duì)于一個(gè)問題的最優(yōu)解只能用窮舉法得到時(shí)，用貪心算法是尋找問題最優(yōu)解的較好算法。對(duì)一個(gè)問題可以同時(shí)用幾種方法解決，貪心算法并不是對(duì)所有的問題都能得到整體最優(yōu)解或是最理想的近似解時(shí)，就需判斷貪心性質(zhì)的正確性了。與回溯法、動(dòng)態(tài)規(guī)劃法等比較，它的適用區(qū)域相對(duì)狹窄許多。總之，如果一個(gè)貪心解決方案存在，就可以使用它。參考文獻(xiàn)1 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(c語言版)M.北京:清