貪心算法淺析

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

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

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

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

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

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

7、個數(shù)為止。證明：先來證明該問題具有貪心選擇性質(zhì)，即對問題T刪除最近下降點的數(shù)xj后得到的N1是n一1位數(shù)是中最小的數(shù)。 根據(jù)數(shù)的進制特點，對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假設刪去的不是xj而是其它位，則有N2=x1*10n-2+x2*10n-3+xi*10n-i-1+xj*10n-k+xn因為有x1<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("請輸入一個正整數(shù)和將要刪去的個數(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)計刪除數(shù)字

9、的個數(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)個數(shù)字 問題的最優(yōu)子結(jié)構(gòu)性質(zhì)在進行了貪心選擇后，原問題T就變成了對N1如何刪去k-1個數(shù)的問題T，是原問題的子問題。若A=(xj，A)是原問題T的最優(yōu)解，則A是子問題T的最優(yōu)解，其最優(yōu)值為TA。 證明：假設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。即存在一個由數(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ì)的證明可知刪數(shù)問題用貪心算法可以求得最優(yōu)解?；顒影才艈栴}問題：設有n個活動的集合E=1,2,.,n，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間Si和一個結(jié)束時間Fi，且Si<Fi。如果選擇了活動i

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

12、.<=Fn排序。如果所給的活動未排序，則先將活動按此序排列，時間復雜度一般為O(nlogn)可解決。以下是解決問題的算法。 1 /貪心算法-活動安排的實現(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; /第一個直接選取10 int j=0;11 for(int i=1;i<n;i+)12 13 if(si>=fj)

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