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

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

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

4、能求出所有最優解。另外，我們經過實踐發現，單純的貪心算法是順序處 理問題的；而且每個結果是可以在處理完一個數據后即時輸出的。(2)貪心的正確性要證明貪心性質的正確性，才是貪心算法的真正挑戰，因為并不是每次局部 最優解都會與整體最優解之間有聯系， 往往靠貪心算法生成的解不是最優解。 這 樣，貪心性質的證明就成了貪心算法正確的關鍵。 對某些問題貪心性質也許是錯 的，即使它在大部分數據中都是可行的，但還必須考慮到所有可能出現的特殊情 況，并證明該貪心性質在這些特殊情況中仍然正確。而這樣容易陷入證明不正確 貪心性質的泥塘中無法自拔，因為貪心算法的適用范圍并不大，而且有一部分極 難證明，若是沒有把握，最

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

6、 xn,要刪去k位數，使得剩下的數 字組成的整數最小。設本問題為 T,其最優解A=(y1, y2, yk)表示依次刪去的k 個數，在刪去k個數后剩下的數字按原次序排成的新數。即最優值記為 TAo本問題采用貪心算法求解，采用最近下降點優先的貪心策略：即 x1x2, xixj ；如果xkxj ,則刪去xj ,即得到一個新的數且這個數為 n 1位中為最 小的數Nl,可表示為x1x2, xixkxm, xn。對N1而言，即刪去了 1位數后，原問 題T變成了需對n-1位數刪去k-1個數新問題。新問題和原問題相同，只是 問題規模由n減小為n-1 ,刪去的數字個數由k減少為k-1?；诖朔N刪除策略， 對新問

7、題，選擇最近下降點的數進行刪除，如此進行下去，直至刪去 k個數 為止。證明：先來證明該問題具有貪心選擇性質，即對問題T刪除最近下降點的數 xj后得到的N1是n 1位數是中最小的數。根據數的進制特點，對a按權展開得：a=x1*10n-1+x2*10n-2+, +xi*10n-i+xj*10n-j+xk*10n-k+, +xn貝U有：Nl=x1*10 n-2+x2*10n-3+, +xi*10n-i-1+xk*10n-k+, +xn假設刪去的不是xj而是其它位，則有N2=x1*10n-2+x2*10n-3+, +xi*10 n-i-1 +xj*10 n-k+, +xn因為有 x1x2, xixk

8、,貝U有 NlN2o 因此刪數問題滿足貪心選擇性質。刪數問題的C+弋碼： #include #include using namespace std;int main() string n;int s,i,x,l,m;printf(請輸入一個正整數和將要刪去的個數！n);while(cinns)i=-1,m=0,x=0;l=n.length();while(xni+1)/出現遞減，刪除遞減的首數字n=n.erase(i,1);x+;/ x統計刪除數字的個數i=-1;/從頭開始查遞減區間if(i=l-x-2&xs)m=1;/ 已經無遞減區間，m=1脫離循環printf(最后結果為:n);cout

9、n.substr(0,l-s+x);/只打印剩下的左邊l-(s-x) 個數字 問題的最優子結構性質在進行了貪心選擇后，原問題T就變成了對N1如何刪去k-1個數的問題， 是原問題的子問題。若 A=(xj , A)是原問題T的最優解，則A是子問題 的最優解，其最優值為TA。證明：假設A不是子問題 的最優解，其子問題的最優解為 B,其最 優值記為TB,則有TB TA。而根據TA的定義可知：TA= TA +xj*1On-j , 而 TB TA,因此有 TB +xj*1On-jTA +xj*1On-j=TA。即存在一個由數 a 刪去1位數后得到的n-1位數比最優值TA更小。這與TA為問題T的最優值相矛

10、盾。因此，A是子問題廠的最優值。因此，刪數問題滿足最優子結構性質。從以上貪心選擇及最優子結構性質的證明可知刪數問題用貪心算法可以求 得最優解活動安排問題問題：設有n個活動的集合E=1,2，,n，其中每個活動都要求使用同一資源， 如演講會場等，而在同一時間內只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間 Si和一個結束時間Fi ,且Si=Fj或Sj=Fi時，活 動i與活動j相容。活動安排問題就是要在所給的活動集合中選擇出最大的相容 活動子集合。證明：這個問題可以使用貪心算法進行求解。其實這個問題的關鍵并不是如何用貪心算法求解，而是如何證明這個問題可以用貪心算法求解。鑒于證

11、明的復雜性，還是不在此討論證明問題。其實貪心算法問題的證明無非都是用數學歸納法證 明，不錯就是那個傳說中萬能證明法，數學歸納法。還是直接討論實現過程吧。實現：首先將活動按照活動的結束時間非遞減：F1=F2=.=Fn排序。如果所給的活動未排序，則先將活動按此序排列，時間復雜度一般為 O(nlogn)可解決。 以下是解決問題的算法。1 /貪心算法-活動安排的實現23 #include stdafx.h4 #include stdio.h56 template7 void GreedySelector(int n,Type s口,Type f口,bool A)8 9 A0=1; /第一個直接選取10

12、 int j=0;11 for(int i=1;i=fj)Ai=true產i； 如果第 i+1 的活動的開始時間大于或等于第i個活動的結束時間，則標記該活動14 else Ai=false;15 16 1718 int _tmain(int argc, _TCHAR* argv口)19 20 / 初始化數據21 int n=3;開始時間結束時間數組A用于標記是否選擇活動，1表示選擇,22int s3=1,2,4;/23int f3=3,3,5;/24 bool A3=0,0,0; / 0表示不選擇 2526 GreedySelector(n,s,f,A);27 for(int i=0;in;i

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