貪心算法

算法思路

貪心算法的基本思路是從問題的某一個初始解出發(fā)一步一步地進行，根據(jù)某個優(yōu)化測度，每一 步都要確保能獲得局部最優(yōu)解。每一步只考慮一 個數(shù)據(jù)，其選取應(yīng)該滿足局部優(yōu)化的條件。若下 一個數(shù)據(jù)和部分最優(yōu)解連在一起不再是可行解時， 就不把該數(shù)據(jù)添加到部分解中，直到把所有數(shù)據(jù)枚舉完，或者不能再添加算法停止。9

貪心算法一般按如下步驟進行：2

①建立數(shù)學模型來描述問題2。

②把求解的問題分成若干個子問題2。

③對每個子問題求解，得到子問題的局部最優(yōu)解2。

④把子問題的解局部最優(yōu)解合成原來解問題的一個解2。

貪心算法是一種對某些求最優(yōu)解問題的更簡單、更迅速的設(shè)計技術(shù)。貪心算法的特點是一步一步地進行，常以當前情況為基礎(chǔ)根據(jù)某個優(yōu)化測度作最優(yōu)選擇，而不考慮各種可能的整體情況，省去了為找最優(yōu)解要窮盡所有可能而必須耗費的大量時間。貪心算法采用自頂向下，以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇，就將所求問題簡化為一個規(guī)模更小的子問題，通過每一步貪心選擇，可得到問題的一個最優(yōu)解。雖然每一步上都要保證能獲得局部最優(yōu)解，但由此產(chǎn)生的全局解有時不一定是最優(yōu)的，所以貪心算法不要回溯2。

算法特性

貪心算法的核心問題是選擇能產(chǎn)生問題最優(yōu)解的最優(yōu)度量標準，即具體的貪心策略。9

貪心算法可解決的問題通常大部分都有如下的特性：3

1、有一個以最優(yōu)方式來解決的問題。為了構(gòu)造問題的解決方案，有一個候選的對象的集合：比如不同面值的硬幣3。

2、隨著算法的進行，將積累起其他兩個集合：一個包含已經(jīng)被考慮過并被選出的候選對象，另一個包含已經(jīng)被考慮過但被丟棄的候選對象3。

3、有一個函數(shù)來檢查一個候選對象的集合是否提供了問題的解答。該函數(shù)不考慮此時的解決方法是否最優(yōu)3。

4、還有一個函數(shù)檢查是否一個候選對象的集合是可行的，即是否可能往該集合上添加更多的候選對象以獲得一個解。和上一個函數(shù)一樣，此時不考慮解決方法的最優(yōu)性3。

5、選擇函數(shù)可以指出哪一個剩余的候選對象最有希望構(gòu)成問題的解3。

6、最后，目標函數(shù)給出解的值3。

使用條件

利用貪心法求解的問題應(yīng)具備如下2個特征4。

1、貪心選擇性質(zhì)

一個問題的整體最優(yōu)解可通過一系列局部的最優(yōu)解的選擇達到，并且每次的選擇可以依賴以前作出的選擇，但不依賴于后面要作出的選擇。這就是貪心選擇性質(zhì)。對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導致問題的整體最優(yōu)解4。

2、最優(yōu)子結(jié)構(gòu)性質(zhì)

當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用貪心法求解的關(guān)鍵所在。在實際應(yīng)用中，至于什么問題具有什么樣的貪心選擇性質(zhì)是不確定的，需要具體問題具體分析4。

解題策略

貪心算法不從整體最優(yōu)上加以考慮，所做出的僅是在某種意義上的局部最優(yōu)選擇。使用貪心策略要注意局部最優(yōu)與全局最優(yōu)的關(guān)系，選擇當前的局部最優(yōu)并不一定能推導出問題的全局最優(yōu)。貪心策略解題需要解決以下兩個問題：5

1、該問題是否適合使用貪心策略求解，也就是該問題是否具有貪心選擇性質(zhì)5；

2、制定貪心策略，以達到問題的最優(yōu)解或較優(yōu)解5。

要確定一個問題是否適合用貪心算法求解，必須證明每一步所作的貪心選擇最終導致問題的整體最優(yōu)解。證明的大致過程為：首先考察問題的一個整體最優(yōu)解，并證明可修改這個最優(yōu)解，使其以貪心選擇開始，做了貪心選擇后，原問題簡化為規(guī)模更小的類似子問題。然后用數(shù)學歸納法證明通過每一步做貪心選擇，最終可得到問題的整體最優(yōu)解5。

存在問題

貪心算法也存在如下問題：6

1、不能保證解是最佳的。因為貪心算法總是從局部出發(fā)，并沒從整體考慮6；

2、貪心算法一般用來解決求最大或最小解6；

3、貪心算法只能確定某些問題的可行性范圍6。

應(yīng)用實例

例如，平時購物找零錢時，為使找回的零錢的硬幣數(shù)最少，不要求找零錢的所有方案，而是從最大面值的幣種開始，按遞減的順序考慮各面額，先盡量用大面值的面額，當不足大面值時才去考慮下一個較小面值，這就是貪心算法7。

有很多經(jīng)典的應(yīng)用，比如霍夫曼編碼，普利姆和克魯斯卡爾最小生成樹算法，還有迪杰斯特拉單源最短路徑算法，都是使用了這種思維。8