演算法(六):圖解貪婪演算法
貪心演算法和動態規劃有什麼區別
演算法（六）：圖解貪婪演算法
演算法簡介
參考：www。cnblogs。com/steven_oyj/…
貪婪演算法(貪心演算法)是指在對問題進行求解時，在每一步選擇中都採取最好或者最優(即最有利)的選擇，從而希望能夠導致結果是最好或者最優的演算法。
貪婪演算法所得到的結果往往不是最優的結果(有時候會是最優解)，但是都是相對近似(接近)最優解的結果。
貪婪演算法並
沒有固定的演算法解決框架
，演算法的關鍵是貪婪策略的選擇，根據不同的問題選擇不同的策略。
必須注意的是策略的選擇必須具備無後效性，即某個狀態的選擇不會影響到之前的狀態，只與當前狀態有關，所以對採用的貪婪的策略一定要仔細分析其是否滿足無後效性。
比如前邊介紹的最短路徑問題（廣度優先、狄克斯特拉）都屬於貪婪演算法，只是在其問題策略的選擇上，剛好可以得到最優解。
基本思路
其基本的解題思路為：
1。建立數學模型來描述問題
2。把求解的問題分成若干個子問題
3。對每一子問題求解，得到子問題的區域性最優解
4。把子問題對應的區域性最優解合成原來整個問題的一個近似最優解
案例
這邊的案例來自“演算法圖解”一書
案例一
區間排程問題：
假設有如下課程，希望儘可能多的將課程安排在一間教室裡：
課程開始時間結束時間美術9AM10AM英語9：30AM10：30AM數學10AM11AM計算機10：30AM11：30AM音樂11AM12PM
這個問題看似要思考很多，實際上演算法很簡單：
1。選擇
結束最早
的課，便是要在這教室上課的第一節課 2。接下來，選擇第一堂課結束後才開始的課，並且結束最早的課，這將是第二節在教室上的課。
重複這樣做就能找出答案，這邊的選擇策略便是結束最早且和上一節課不衝突的課進行排序，因為每次都選擇結束最早的，所以留給後面的時間也就越多，自然就能排下越多的課了。
每一節課的選擇都是策略內的區域性最優解（留給後面的時間最多），所以最終的結果也是近似最優解（這個案例上就是最優解）。 （該案例的程式碼實現，就是一個簡單的時間遍歷比較過程）
案例二
揹包問題：有一個揹包，容量為35磅 ， 現有如下物品
物品重量價格吉他151500音響303000膝上型電腦202000顯示器292999筆1200
要求達到的目標為裝入的揹包的總價值最大，並且重量不超出。
方便計算所以只有3個物品，實際情況可能是成千上萬。
同上使用貪婪演算法，因為要總價值最大，所以每次每次都裝入最貴的，然後在裝入下一個最貴的，選擇結果如下：
選擇： 音響 + 筆，總價值 3000 + 200 = 3200
並不是最優解： 吉他 + 膝上型電腦， 總價值 1500 + 2000 = 3500
當然選擇策略有時候並不是很固定，可能是如下：
（1）每次挑選價值最大的，並且最終重量不超出：
選擇： 音響 + 筆，總價值 3000 + 200 = 3200
（2）每次挑選重量最大的，並且最終重量不超出（可能如果要求裝入最大的重量才會優先考慮）：
選擇： 音響 + 筆，總價值 3000 + 200 = 3200
（3）每次挑選單位價值最大的（價格/重量），並且最終重量不超出：
選擇： 筆+ 顯示器，總價值 200 + 2999 = 3199
如上最終的結果並不是最優解，在這個案例中貪婪演算法並無法得出最優解，只能得到近似最優解，也算是該演算法的
侷限性之一
。該類問題中需要得到最優解的話可以採取動態規劃演算法（後續更新，也可以關注我的公眾號第一時間獲取更新資訊）。
案例三
集合覆蓋問題：
假設存在如下表的需要付費的廣播臺，以及廣播臺訊號可以覆蓋的地區。 如何選擇最少的廣播臺，讓所有的地區都可以接收到訊號。
廣播臺覆蓋地區K1ID，NV，UTK2WA，ID，MTK3OR，NV，CAK4NV，UTK5CA，AZ……
如何找出覆蓋所有地區的廣播臺的集合呢，聽起來容易，實現起來很複雜，使用窮舉法實現：
（1） 列出每個可能的廣播臺的集合，這被稱為冪集。假設總的有n個廣播臺，則廣播臺的組合總共有2ⁿ個
（2） 在這些集合中，選出覆蓋全部地區的最小的集合，假設n不在，但是當n非常大的時候，假設每秒可以計算10個子集
廣播臺數量n子集總數2ⁿ需要的時間5323。2秒101024102。4秒32429496729613。6年1001。26*100³º4x10²³年
目前並沒有演算法可以快速計算得到準備的值， 而使用貪婪演算法，則可以得到非常接近的解，並且效率高：
選擇策略上，因為需要覆蓋全部地區的最小集合：
（1） 選出一個廣播臺，即它覆蓋了最多未覆蓋的地區即便包含一些已覆蓋的地區也沒關係 （2） 重複第一步直到覆蓋了全部的地區
這是一種近似演算法（approximation algorithm，貪婪演算法的一種）。在獲取到精確的最優解需要的時間太長時，便可以使用近似演算法，判斷近似演算法的優劣標準如下：
速度有多快
得到的近似解與最優解的接近程度
在本例中貪婪演算法是個不錯的選擇，不僅執行速度快，本例執行時間O（n²），最壞的情況，假設n個廣播臺，每個廣播臺就覆蓋1個地區，n個地區，總計需要查詢n*n=O（n²），實現可檢視後面的java程式碼實現
廣播臺數量n子集總數2ⁿ窮舉需要時間貪婪演算法5323。2秒2。5秒1032102。4秒10秒323213。6年102。4秒100324x10²³年1000秒
此時演算法選出的是K1， K2， K3， K5，符合覆蓋了全部的地區，可能不是預期中的K2， K3，K4，K5（也許預期中的更便宜，更便於實施等等）
NP完全問題
案例四：
旅行商問題
假設有旅行商需要從下面三個城市的某一個城市出發，如何規劃路線獲取行程的最短路徑。
存在3！（階乘）=6種可能情況：
A->B->CA->C->BB->A->CB->C->AC->A->BC->B->A複製程式碼
這邊和之前求最短路徑的演算法（廣度搜索、狄克斯特拉、貝爾曼-福特），最大的差別是沒有固定源點（起點），，每一個節點都可能是源點，並且需要經過每一個節點，所以若窮舉法則不得不找出每一種可能並進行比較。
當城市數量為n，則可能性為n！，假設每秒處理判斷一個路線
數量n總數n！窮舉需要時間5120120秒103242天
而使用貪婪演算法，隨機選擇從一個城市出發，比如A，每次選擇從最近的還沒去過的城市出發，則可以得到近似最優解。
第一次比較n-1個城市 第二次比較n-2個城市 。。。 第n-1次比較1個城市 第n次不存在需要比較的了個
0+1+2+3+。。+（n-1） ≈ O（n²/2）
數量n總數n！窮舉需要時間貪婪需要時間5120120秒12。5秒103242天50秒
類似上述集合覆蓋問題、旅行商問題，都屬於NP完全問題，在數學領域上並沒有快速得到最優解的方案，貪婪演算法是最適合處理這類問題的了。
如何判斷是NP完全問題的：
1。元素較少時，一般執行速度很快，但隨著元素數量增多，速度會變得非常慢 2。涉及到需要計算比較“所有的組合”情況的通常是NP完全問題 3。無法分割成小問題，必須考慮各種可能的情況。這可能是NP完全問題 4。如果問題涉及序列（如旅行商問題中的城市序列）且難以解決，它可能就是NP完全問題 5。如果問題涉及集合（如廣播臺集合）且難以解決，它可能就是NP完全問題 6。如果問題可轉換為集合覆蓋問題或旅行商問題，那它肯定是NP完全問題
小結
1。貪婪演算法可以尋找區域性最優解，並嘗試與這種方式獲得全域性最優解
2。得到的可能是近似最優解，但也可能便是最優解（區間排程問題，最短路徑問題（廣度優先、狄克斯特拉））
3。對於完全NP問題，目前並沒有快速得到最優解的解決方案
4。面臨NP完全問題，最佳的做法就是使用近似演算法
5。貪婪演算法（近似演算法）在大部分情況下易於實現，並且效率不錯
java實現
貪婪演算法需要根據具體問題，選擇對應的策略來實現，所以這邊只取集合覆蓋問題做個示例：
/** * 貪婪演算法 - 集合覆蓋問題 * @author Administrator * */public class Greedy { public static void main（String［］ args）{ //初始化廣播臺資訊 HashMap
參考文獻：K碼農-http：//kmanong。top/kmn/qxw/form/home？top_cate=28