貪心算法淺析

《貪心算法淺析》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

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ì)存在，那么一定要

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

4、是，值得指出的是，當一個問題具有多個最優(yōu)解時，貪心算法并不能求出所有最優(yōu)解。另外，我們經(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哈夫曼編碼20-1背包問題3磁盤文件的存儲4生產(chǎn)調(diào)度問題5信息查詢貪心算法經(jīng)典應用舉例刪數(shù)問題問題提出：給定n位正整數(shù)a，去掉其中任意k<=n個數(shù)字后，剩下的數(shù)字按原次序排列組成一個新的正整數(shù)。對于給定的n位正整數(shù)a和正整數(shù)k，設計一

6、個算法找出剩下數(shù)字組成的新數(shù)最小的刪數(shù)方案。分析：n位數(shù)a可表示為x1x2…xixjxk…xn，要刪去k位數(shù)，使得剩下的數(shù)字組成的整數(shù)最小。設本問題為T，其最優(yōu)解A=(y1，y2…yk)表示依次刪去的k個數(shù)，在刪去k個數(shù)后剩下的數(shù)字按原次序排成的新數(shù)。即最優(yōu)值記為TA。本問題采用貪心算法求解，采用最近下降點優(yōu)先的貪心策略：即x1

7、相同，只是問題規(guī)模由n減小為n-1，刪去的數(shù)字個數(shù)由k減少為k-1?；诖朔N刪除策略，對新問題T’，選擇最近下降點的數(shù)進行刪除，如此進行下去，直至刪去k個數(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+x

8、2*10n