![Greedy[貪心算法]](/img/8/071/nBnauM3X4MDM2EDN5IzN0ETN1UTM1QDN5MjM5ADMwAjMwUzLyczL0UzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg "Greedy[貪心算法]")
貪心算法
算法思想
雖然設計一個好的求解算法更像是一門藝術，而不像是技術，但仍然存在一些行之有效的能夠用於解決許多問題的算法設計方法，你可以使用這些方法來設計算法，並觀察這些算法是如何工作的。一般情況下，為了獲得較好的性能，必須對算法進行細緻的調整。但是在某些情況下，算法經過調整之後性能仍無法達到要求，這時就必須尋求另外的方法來求解該問題。Greedy Algorithm在設計方面不能保證求得的最後解是最佳的和不能用來求最大或最小解問題，只能求滿足某些約束條件的可行解的範圍。
事例1
例1-4 [找零錢] 一個小孩買了價值少於1美元的糖，並將1美元的錢交給售貨員。售貨員希望用數目最少的硬幣找給小孩。假設提供了數目不限的面值為2 5美分、1 0美分、5美分、及1美分的硬幣。售貨員分步驟組成要找的零錢數，每次加入一個硬幣。選擇硬幣時所採用的貪婪準則如下：每一次選擇應使零錢數儘量增大。為保證解法的可行性（即：所給的零錢等於要找的零錢數），所選擇的硬幣不應使零錢總數超過最終所需的數目。
假設需要找給小孩6 7美分，首先入選的是兩枚2 5美分的硬幣，第三枚入選的不能是2 5美分的硬幣，否則硬幣的選擇將不可行（零錢總數超過6 7美分），第三枚應選擇1 0美分的硬幣，然後是5美分的，最後加入兩個1美分的硬幣。
貪婪算法有種直覺的傾向，在找零錢時，直覺告訴我們應使找出的硬幣數目最少（至少是接近最少的數目）。可以證明採用上述貪婪算法找零錢時所用的硬幣數目的確最少（見練習1）。
事例2
例1-5 [機器調度] 現有n 件任務和無限多台的機器，任務可以在機器上得到處理。每件任務的開始時刻為si，完成時刻為fi ，si < fi 。[si , fi ] 為處理任務i 的時間範圍。兩個任務i，j 重指兩個任務的時間範圍區間有重疊，而並非是指i，j 的起點或終點重合。例如：區間[ 1，4 ]與區間[ 2，4 ]重疊，而與區間[ 4，7 ]不重疊。一個可行的任務分配是指在分配中沒有兩件重疊的任務分配給同一台機器。因此，在可行的分配中每台機器在任何時刻最多只處理一個任務。最優分配是指使用的機器最少的可行分配方案。
假設有n= 7件任務，標號為a 到g。它們的開始與完成時間如圖13-1a 所示。若將任務a分給機器M1，任務b 分給機器M2，. . .，任務g 分給機器M7，這種分配是可行的分配，共使用了七台機器。但它不是最優分配，因為有其他分配方案可使利用的機器數目更少，例如：可以將任務a、b、d分配給同一台機器，則機器的數目降為五台。
一種獲得最優分配的貪婪方法是逐步分配任務。每步分配一件任務，且按任務開始時間的非遞減次序進行分配。若已經至少有一件任務分配給某台機器，則稱這台機器是舊的；若機器非舊，則它是新的。在選擇機器時，採用以下貪婪準則：根據欲分配任務的開始時間，若此時有舊的機器可用，則將任務分給舊的機器。否則，將任務分配給一台新的機器。 根據例子中的數據，貪婪算法共分為n = 7步，任務分配的順序為a、f、b、c、g、e、d。第一步沒有舊機器，因此將a 分配給一台新機器（比如M1）。這台機器在0到2時刻處於忙狀態。在第二步，考慮任務f。由於當f 啟動時舊機器仍處於忙狀態，因此將f 分配給一台新機器(設為M2 )。第三步考慮任務b, 由於舊機器M1在Sb = 3時刻已處於閒狀態，因此將b分配給M1執行，M1下一次可用時刻變成fb = 7，M2的可用時刻變成ff = 5。第四步，考慮任務c。由於沒有舊機器在Sc = 4時刻可用，因此將c 分配給一台新機器（M3），這台機器下一次可用時間為fc = 7。第五步考慮任務g，將其分配給機器M2，第六步將任務e 分配給機器M1, 最後在第七步，任務2分配給機器M3。（注意：任務d 也可分配給機器M2）。
上述貪婪算法能導致最優機器分配的證明留作練習（練習7）。可按如下方式實現一個複雜性為O (nl o gn)的貪婪算法：首先採用一個複雜性為O (nl o gn)的排序算法（如堆排序）按Si 的遞增次序排列各個任務，然後使用一個關於舊機器可用時間的最小堆。
事例3
例1-6 [最短路徑] 給出一個有向網路，路徑的長度定義為路徑所經過的各邊的耗費之和。要求找一條從初始頂點s 到達目的頂點d 的最短路徑。
貪婪算法分步構造這條路徑，每一步在路徑中加入一個頂點。假設當前路徑已到達頂點q，
且頂點q 並不是目的頂點d。加入下一個頂點所採用的貪婪準則為：選擇離q 近且不在路徑中的頂點。
這種貪婪算法並不一定能獲得最短路徑。例如，假設在圖1 3 - 2中希望構造從頂點1到頂點5的最短路徑，利用上述貪婪算法，從頂點1開始並尋找目前不在路徑中的離頂點1最近的頂點。到達頂點3，長度僅為2個單位，從頂點3可以到達的頂點為4，從頂點4到達頂點2，最後到達目的頂點5。所建立的路徑為1 , 3 , 4 , 2 , 5，其長度為1 0。這條路徑並不是有向圖中從1到5的最短路徑。事實上，有幾條更短的路徑存在，例如路徑1，4，5的長度為6。
總結
根據上面三個例子，回想一下前幾章所考察的一些套用，其中有幾種算法也是貪婪算法。例如，霍夫曼樹算法，利用n- 1步來建立最小加權外部路徑的二叉樹，每一步都將兩棵二叉樹合併為一棵，算法中所使用的貪婪準則為：從可用的二叉樹中選出權重最小的兩棵。L P T調度規則也是一種貪婪算法，它用n 步來調度n 個作業。首先將作業按時間長短排序，然後在每一步中為一個任務分配一台機器。選擇機器所利用的貪婪準則為：使目前的調度時間最短。將新作業調度到最先完成的機器上（即最先空閒的機器）。
存在問題
注意到在機器調度問題中，貪婪算法並不能保證最優，然而，那是一種直覺的傾向且一般情況下結果總是非常接近最優值。它利用的規則就是在實際環境中希望人工機器調度所採用的規則。算法並不保證得到最優結果，但通常所得結果與最優解相差無幾，這種算法也稱為啟發式方法（ h e u r i s t i c s )。因此L P T方法是一種啟發式機器調度方法。定理9 - 2陳述了L P T調度的完成時間與最佳調度的完成時間之間的關係，因此L P T啟發式方法具有限定性
能（ bounded performance ）。具有限定性能的啟發式方法稱為近似算法（ a p p r o x i m a t i o na l g o r i t h m）。
本章的其餘部分將介紹幾種貪婪算法的套用。在有些套用中，貪婪算法所產生的結果總是最優的解決方案。但對其他一些套用，生成的算法只是一種啟發式方法，可能是也可能不是近似算法。
兩大難點
貪心方法
怎樣才能從眾多可行解中找到最優解呢？其實，大部分都是有規律的。在樣例中，貪心就有很明顯的規律。但你得到了[font lang=EN-US] N = 5 時的最優解後，你只需要在已用上的5塊木板中尋找最靠近的兩塊，然後貼上中間的幾個牛棚，使兩塊木板變成一塊。這樣生成的 N = 4 的解必定最優。因為這樣木板的浪費最少。同樣，其他的貪心題也會有這樣的性質。正因為貪心有如此性質，它才能比其他算法要快。
正確性
要證明貪心性質的正確性，才是貪心算法的真正挑戰，因為並不是每次局部最優解都會與整體最優解之間有聯繫，往往靠貪心生成的解不是最優解。這樣，貪心性質的證明就成了貪心算法正確的關鍵。一個你想出的貪心性質也許是錯的，即使它在大部分數據中都是可行的，你必須考慮到所有可能出現的特殊情況，並證明你的貪心性質在這些特殊情況中仍然正確。這樣經過千錘百鍊的性質才能構成一個正確的貪心。
在樣例中，我們的貪心性質是正確的。如下：
假設我們的答案蓋住了較大的空牛棚連續列，而不是較小的。那么我們把那部分蓋空牛棚的木板鋸下來，用來把較小的空牛棚連續列蓋住，還會有剩餘。那么鋸掉它們！還給木材商！同時我們的解也變小了。也就是說，我們獲得更優的解。所以，靠蓋住較大空牛棚連續列的方法無法獲得最優解，我們也應該儘量貪心那些距離小的木板合併。
如果仍有一個空牛棚連續列與我們的答案蓋住的那個相同，我們同樣使用上述的方法。會發現獲得的新解與原解相同，那么不論我們選哪個，結果都將一樣。
由此可見，如果我們合併的兩塊木板間距離最短，那么總能獲得最優解。所以，在解題的每一步中，我們都只需要尋找兩塊距離最小的木板併合並它們。這樣，我們獲得的解必定最優。
結論
如果有貪心性質存在，那么一定要採用！因為它容易編寫，容易調試，速度極快，並且節約空間。幾乎可以說，它是所有算法中最好的。但是應該注意，別陷入證明不正確貪心性質的泥塘中無法自拔，因為貪心算法的適用範圍並不大，而且有一部分極難證明，若是沒有把握，最好還是不要冒險，因為還有其他算法會比它要保險。
and so on.
以上內容的部分總結來自網民和網頁摘抄。
Michael Scofield L Q
