算法系列—貪心算法

關鍵字：局部最優

引言

     貪婪是一種人類本能的東西，貪心算法也是最接近人類日常思維的一種解題政策。比如，找零錢問題：

     假設提供了數目不限的面值為25美分、10美分、5美分、1美分的硬币。一個小孩買了價值少于1美元的糖，并将1美元交給售貨員，售貨員希望用最少的硬币數找錢給小孩。假設小孩買了33美分的糖果。（需要找錢67美分）

      找錢的方法：25+25+10+5+1+1.

      我們有種直覺傾向：在找零時，直覺告訴我們使用面值越大的硬币找零，還差找零的剩餘金額最少，用的硬币也越少。

一、基本概念：      所謂貪心算法是指，在對問題求解時，總是做出在目前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。      貪心算法沒有固定的算法架構，算法設計的關鍵是貪心政策的選擇。必須注意的是，貪心算法不是對所有問題都能得到整體最優解，選擇的貪心政策必須具備無後效性，即某個狀态以後的過程不會影響以前的狀态，隻與目前狀态有關。      是以對所采用的貪心政策一定要仔細分析其是否滿足無後效性。

二、算法基本思路：     1.建立數學模型來描述問題。     2.把求解的問題分成若幹個子問題。     3.對每一子問題求解，得到子問題的局部最優解。

    4.把子問題的解局部最優解合成原來解問題的一個解。

三、算法特點：

    1. 不能保證求得的最後解是最佳的；

    2. 不能用來求最大或最小解問題；

    3. 隻能求滿足某些限制條件的可行解的範圍。

    4. 速度快，通常是線性二次式，不需要多少額外的記憶體。

    5. 程式運作過程中無回溯過程，後面的每一步都是目前看似最佳的選擇，這種選擇依賴于已做出的選擇，不依賴于未作出的選擇。

四、适用問題       适合貪心法求解的問題一般具有兩個重要性質：貪心選擇性質和最優子結構性質。

     1.貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動态規劃算法的主要差別。

        與動态規劃算法相同的是，都具有最優子結構性質（相同點）；不同的是，動态規劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行，以疊代的方式作出相繼的貪心選擇，每作一次貪心選擇就将所求問題簡化為規模更小的子問題（不同點）。

     2.當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。問題的最優子結構性質是該問題可用動态規劃算法或貪心算法求解的關鍵特征。

  五、貪心算法的實作架構     從問題的某一初始解出發；     while （能朝給定總目标前進一步）     {            利用可行的決策，求出可行解的一個解元素；     }     由所有解元素組合成問題的一個可行解；    六、執行個體分析

    貪心算法可以求解很多問題，比如哈夫曼樹問題、單源最短路徑問題、最小生成樹問題等，現就著名的背包問題，采用貪心法分析之。

    問題描述：給定n個物品和一個容量為C的背包，物品i的重量是Wi,其價值為Vi,背包問題是如何選擇入背包的物品，使得裝入背包的物品的總價值最大，注意和0/1背包的差別，在背包問題中可以将物品的一部分裝入背包，但不能重複裝入。

    算法分析思路：用貪心法求解背包問題的關鍵是如何標明貪心政策，使得按照一定的順序選擇每個物品，并盡可能的裝入背包，知道背包裝滿。至少有三種看似合适的貪心政策。

1. 選擇價值最大的物品，因為這可以盡可能快的增加背包的總價值，但是，雖然每一步選擇獲得了背包價值的極大增長，但背包容量卻可能消耗的太快，使得裝入背包的物品個數減少，進而不能保證目标函數達到最大。
2. 選擇重量最輕的物品，因為這可以裝入盡可能多的物品，進而增加背包的總價值。但是，雖然每一步選擇使背包的容量消耗的慢了，但背包的價值卻沒能保證迅速的增長，進而不能保證目标函數達到最大。
3. 以上兩種貪心政策或者隻考慮背包價值的增長，或者隻考慮背包容量的消耗，而為了求得背包問題的最優解，需要在背包價值增長和背包容量消耗二者之間尋找平衡。正确的貪心政策是選擇機關重量價值最大的物品。

    例如：有三個物品，其重量分别為{20,30,10}，價值分别為{60,120,50}，背包的容量為50，應用三種貪心政策裝入背包的物品和獲得的價值如下圖所示：（部分轉載）

    設背包容量為C，共有n個物品，物品重量存放在數組W[n]中，價值存放在數組V[n]中，問題的解存放在數組X[n]中，貪心法求解背包問題的算法如下：

算法：貪心法求解背包問題 輸入：背包的容量C,物品重量W[n]，物品價值V[n] 輸出：數組X[n] 改變數組W和V的排列順序，使其按機關重量價值V[i]/W[i]降序排列； 将數組X[n]初始化為0； i=0； 循環直到（W[i]>C）     4.1   将第i個物品放入背包：X[i]=1;     4.2    C=C-W[i];     4.3    i++; X[i]=C/W[i]。

    算法分析：算法的時間主要消耗在将各種物品按照機關重量的價值從大到小的排序，是以，其時間複雜性為O(nlog2n)。

    背包問題與0/1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇該物品的一部分【分割物品】，不一定要全部裝入背包。而0/1背包問題必須保證物品的完整性，即要麼整體放入，要麼不放，非0即1。背包問題可以用貪心法求解，而0/1背包問題卻不能用貪心法求解，下圖給出了一個貪心法求解0/1背包問題的示例。從下圖可以看出，對于0/1背包問題，貪心法之是以不能得到最優解，是由于物品不允許分割，是以，無法保證最終能将背包裝滿，部分閑置的背包容量使背包的機關重量價值降低了。事實上，在考慮0/1背包問題時，應比較選擇該物品和不選擇該物品所導緻的方案，然後再做出最優選擇，由此導出許多互相重疊的子問題，是以，0/1背包問題合适用動态規劃法求解。

   算法實作：實作函數KnapSacks實作貪心法求解背包問題，簡單起見，假設物品已按機關重量降序排列，算法C++語言描述如下：

int KnapSack (int W[],int V[],int N,int C)  
    {  
        double X[10]={0};  
        int maxValue=0;  
        for(int i=0;W[i]<C;i++)  
        {  
            X[i]=1;  
            maxValue+=V[i];  
            C=C-W[i];  
              
        X[i]=(double)C/W[i];  
        maxValue+=X[i]*V[i];  
        return maxValue;  
        }  
    }
           

七、總結

     貪心法并不是從整體最優考慮，它所做出的選擇隻是某種意義的局部最優，貪心算法對于大部分的優化問題都能産生最優解，但不能總獲得整體最優解，通常可以獲得近似最優解。

轉載請注明出處：http://blog.csdn.net/daijin888888/article/details/53079358