貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，算法得到的是在某種意義上的局部最優解。
貪心算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇。也就是說，不從整體最優上加以考慮，做出的只是在某種意義上的局部最優解。
基本介紹
- 中文名：貪心算法
- 外文名：greedy algorithm
- 別稱：貪婪算法
- 定義：做出在當前看來是最好的選擇
- 核心：根據題意選取一種量度標準
- 領域：數理科學
算法思路,算法特性,使用條件,解題策略,存在問題,套用實例,
算法思路
貪心算法一般按如下步驟進行：
①建立數學模型來描述問題。
②把求解的問題分成若干個子問題。
③對每個子問題求解，得到子問題的局部最優解。
④把子問題的解局部最優解合成原來解問題的一個解。
貪心算法是一種對某些求最優解問歡朽趨題的更簡單、更迅速的設計技術。貪心算法的特點是一步一步地進行，常以當前情況為基礎根據某個最佳化測度作最優選擇，而不考慮各種可能的整體情況，省去了為找最優解要窮盡所有可能而必須耗費的大量時間。貪心算法採用自頂向下，以疊代的方法做出相繼的貪心選擇，每做一次貪心選擇，就將所求問題簡化為一個規模更小的子問題，通過每一步貪心選擇，可得到問題的一個最優解。雖然每一步上都要保證能獲得局部最優解，但由此產生的全局解有時不一定是最優的，所以貪心算法不要回溯。
算法特性
貪心算法可解決的問題通常大部分都有如下的特性：
1、有一個以最優方式來解決的問題。為了構造問題的解決方案，有一個候選的對象的集合：比如不同面值的硬幣。
2、隨著算法的進行，將積累起其他兩個集合：一個包含已經被考慮過並被選出的候選對象，另一個包含已經被考慮過但被丟棄的候選對象。
3、有一個函式來檢查一個候選對象的集合是否提供了問題的解答。該函式不考慮此時的解決方法是否最優。
4、還有一個函促影數檢查是否一個候選對象的集合是可行的，即是否可能往該集合上添加更多的候選對象以獲得一個解。和上一個函式一樣，此時不考慮解決方法的最優性。
5、選擇函式可以指出哪一個剩餘的候選對象最有希望構成問題的解。
6、最後，目標函式給出解的值。
使用條件
利用貪心法求解的問題應具備如下2個特徵。
1、貪心選擇性質
一個問題的整體最優解可艱諒疊通過一系列局部的最優解的選擇達到，並且每次的選擇可以依賴以前作出的選擇，但不依賴於後面要作出的選擇。這就是貪心選擇性質。對於一個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整體最優解。
2、最優子結構性質
當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。問題的最優子結構性質是該問題可用貪心法求解的關鍵所在。在實際套用中，至於什麼問題具有什麼樣的貪心選擇性質是不確定的，需要具體問題具體分析。
解題策略
貪心算法不從整體最優上加以考慮，所做出的僅是在某種意義上的局部最優選擇。使用貪心策略要注意局部最優與全局最優的關係，選擇當前的局部最優並不一定能推導出問題的全局最優。貪心策略解題需要解決以下兩個問題：
1、該問題是否適合使用貪心策略求解，也就是該問題是否具有貪心選擇性質；
2、制定貪心策略，以達到問題的最優解或較優解。
要確定一個問題是否適合用貪心算法求解，必須證明每一步辣仔腳所作的貪心選擇最終導致問題的整體最優解。證明的大致過程為：首先考察問題的一個整體最優解，並證明可修改這個最優解，使其以貪心選擇開始，做了貪心選擇後，原問題簡化為規模更小的類似子問題。然後用數學歸納法證明通過每一步做貪心選擇，最終可得到問題的整體最優解。
存在問題
貪心算法也存在如下問題：
1、不能棕祖判保證解是最佳的。因為貪心算法總是從局部出發，並沒從整體考慮；
2、貪心算法一般用來解決求最大或最小解牛笑鴉想；
3、貪心算法只能確定某些問題的可行性範圍。
套用實例
例如，平時購物找零錢時，為使找回的零錢的硬甩洪踏騙幣數最少，不要求找零錢的所有方案，而是從最大面值的幣種開始，按遞減的順序考慮各面額，先儘量用大面值的面額，當不足大面值時才去考慮下一個較小面值，這就是貪心算法。
要確定一個問題是否適合用貪心算法求解，必須證明每一步所作的貪心選擇最終導致問題的整體最優解。證明的大致過程為：首先考察問題的一個整體最優解，並證明可修改這個最優解，使其以貪心選擇開始，做了貪心選擇後，原問題簡化為規模更小的類似子問題。然後用數學歸納法證明通過每一步做貪心選擇，最終可得到問題的整體最優解。
存在問題
貪心算法也存在如下問題：
1、不能保證解是最佳的。因為貪心算法總是從局部出發，並沒從整體考慮；
2、貪心算法一般用來解決求最大或最小解；
3、貪心算法只能確定某些問題的可行性範圍。
套用實例
例如，平時購物找零錢時，為使找回的零錢的硬幣數最少，不要求找零錢的所有方案，而是從最大面值的幣種開始，按遞減的順序考慮各面額，先儘量用大面值的面額，當不足大面值時才去考慮下一個較小面值，這就是貪心算法。
