版權聲明：本文為博主原創文章，遵循 CC 4.0 BY-SA 版權協議，轉載請附上原文出處鏈接和本聲明。 本文鏈接：https://blog.csdn.net/m0_37609579/article/details/100024908
一、一種很貪婪的算法定義
貪心是人類自帶的能力，貪心算法是在貪心決策上進行統籌規劃的統稱。
【百度百科】貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。
二、貪心跟動態規劃
貪心選擇
貪心選擇是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態規劃算法的主要區別。貪心選擇是采用從頂向下、以迭代的方法做出相繼選擇，每做一次貪心選擇就將所求問題簡化為一個規模更小的子問題。對于一個具體問題，要確定它是否具有貪心選擇的性質，我們必須證明每一步所作的貪心選擇最終能得到問題的最優解。通常可以首先證明問題的一個整體最優解，是從貪心選擇開始的，而且作了貪心選擇后，原問題簡化為一個規模更小的類似子問題。然后，用數學歸納法證明，通過每一步貪心選擇，最終可得到問題的一個整體最優解。
最優子結構
當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。運用貪心策略在每一次轉化時都取得了最優解。問題的最優子結構性質是該問題可用貪心算法或動態規劃算法求解的關鍵特征。貪心算法的每一次操作都對結果產生直接影響，而動態規劃則不是。貪心算法對每個子問題的解決方案都做出選擇，不能回退；動態規劃則會根據以前的選擇結果對當前進行選擇，有回退功能。動態規劃主要運用于二維或三維問題，而貪心一般是一維問題 。
總結
貪心算法是自頂向下的，而動態規劃則是自底向上的。動態規劃是自底向上求出各子問題的有化解，最后匯集有化解從而得出問題的全局最優解（可以想象成各個小河流入大海） 。貪心算法是自頂下向下，以迭代的方式一步一步做出貪心選擇，從而把問題簡化成規模更小的問題 。狹義的貪心算法指的是解最優化問題的一種特殊方法，解決過程中總是做出當下最好的選擇，因為具有最優子結構的特點，局部最優解可以得到全局最優解；這種貪心算法是動態規劃的一種特例。能用貪心解決的問題，也可以用動態規劃解決。 三、貪婪算法的思想
貪心算法的基本思路是從問題的某一個初始解出發一步一步地進行，以盡可能快的地求得更好的解。根據某個優化測度，每一步都要確保能獲得局部最優解。每一步只考慮一個數據，他的選取應該滿足局部優化的條件。若下一個數據和部分最優解連在一起不再是可行解時，就不把該數據添加到部分解中，直到把所有數據枚舉完，或者不能再添加時，算法停止。
該算法存在問題：
不能保證求得的最后解是最佳的； 不能用來求最大或最小解問題； 只能求滿足某些約束條件的可行解的范圍。 實現該算法的過程：
從問題的某一初始解出發；while 能朝給定總目標前進一步；do 求出可行解的一個解元素；由所有解元素組合成問題的一個可行解。 四、貪心算法能解決哪些問題呢？
貪婪算法可解決的問題通常大部分都有如下的特性：
- 隨著算法的進行，將積累起其它兩個集合：一個包含已經被考慮過并被選出的候選對象，另一個包含已經被考慮過但被丟棄的候選對象。
- 有一個函數來檢查一個候選對象的集合是否提供了問題的解答。該函數不考慮此時的解決方法是否最優。
- 還有一個函數檢查是否一個候選對象的集合是可行的，也即是否可能往該集合上添加更多的候選對象以獲得一個解。和上一個函數一樣，此時不考慮解決方法的最優性。
- 選擇函數可以指出哪一個剩余的候選對象最有希望構成問題的解。
- 最后，目標函數給出解的值。
- 為了解決問題，需要尋找一個構成解的候選對象集合，它可以優化目標函數，貪婪算法一步一步的進行。起初，算法選出的候選對象的集合為空。接下來的每一步中，根據選擇函數，算法從剩余候選對象中選出最有希望構成解的對象。如果集合中加上該對象后不可行，那么該對象就被丟棄并不再考慮；否則就加到集合里。每一次都擴充集合，并檢查該集合是否構成解。如果貪婪算法正確工作，那么找到的第一個解通常是最優的。
具體而言，0-1背包、單源最短路徑、馬踏棋盤、均分紙牌等問題都可以使用貪心算法來解決。
五、使用貪心算法如何解決霍夫曼編碼
1.回顧一下霍夫曼編碼
霍夫曼編碼是廣泛地用于數據文件壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間。哈夫曼編碼算法用字符在文件中出現的頻率表來建立一個用0，1串表示各字符的最優表示方式。
霍夫曼編碼中，每個字符用唯一的一個0,1串表示，并且采用變長編碼來表示每個字符，使用頻率高的字符用較短的編碼；使用頻率低的字符用較長的編碼，以達到整體文本編碼縮小的目的。
對于霍夫曼解碼，我們引入前綴碼的概念：對每一個字符規定一個0,1串作為其代碼，并要求任一字符的代碼都不是其他字符代碼的前綴。編碼的前綴性質可以使譯碼方法非常簡單；例如001011101可以唯一的分解為0,0,101,1101，因而其譯碼為aabe。
譯碼過程需要方便的取出編碼的前綴，因此需要表示前綴碼的合適的數據結構。為此，可以用二叉樹作為前綴碼的數據結構：樹葉表示給定字符；從樹根到樹葉的路徑當作該字符的前綴碼；代碼中每一位的0或1分別作為指示某節點到左兒子或右兒子的“路標”。
從上圖可以看出，表示最優前綴碼的二叉樹總是一棵完全二叉樹，即樹中任意節點都有2個兒子。圖a表示定長編碼方案不是最優的，其編碼的二叉樹不是一棵完全二叉樹。在一般情況下，若C是編碼字符集，表示其最優前綴碼的二叉樹中恰有|C|個葉子。每個葉子對應于字符集中的一個字符，該二叉樹有|C|-1個內部節點。
2.構造哈弗曼編碼
哈夫曼提出構造最優前綴碼的貪心算法，由此產生的編碼方案稱為哈夫曼編碼。其構造步驟如下：
哈夫曼算法以自底向上的方式構造表示最優前綴碼的二叉樹T。算法以|C|個葉結點開始，執行|C|－1次的“合并”運算后產生最終所要求的樹T。假設編碼字符集中每一字符c的頻率是f(c)。以f為鍵值的優先隊列Q用在貪心選擇時有效地確定算法當前要合并的2棵具有最小頻率的樹。一旦2棵具有最小頻率的樹合并后，產生一棵新的樹，其頻率為合并的2棵樹的頻率之和，并將新樹插入優先隊列Q。經過n－1次的合并后，優先隊列中只剩下一棵樹，即所要求的樹T。應該將概率低的元素放置到樹的底部，將概率高的元素放置到樹的頂部。 構造過程如圖所示：
具體代碼實現如下：
import java.util.ArrayList;/*** 貪心算法解哈夫曼編碼問題* * @author wly* */
public class HuffmanCode {public static void main(String[] args) {ArrayList<HuffmanNode> list = new ArrayList<HuffmanNode>();list.add(new HuffmanNode(null, null, "A", 0.3f));list.add(new HuffmanNode(null, null, "B", 0.1f));list.add(new HuffmanNode(null, null, "C", 0.35f));list.add(new HuffmanNode(null, null, "D", 0.05f));list.add(new HuffmanNode(null, null, "E", 0.2f));print(getHuffmanCodeNode(list));}/*** 得到表示當前輸入節點的樹結構* @param list* @return*/public static HuffmanNode getHuffmanCodeNode(ArrayList<HuffmanNode> list) {while (list.size() >= 2) {//1.排序元素srotNodeListByKey(list);//2.合并key值最小的兩個節點(因為已經排序過了，此處就是列表的前兩項)HuffmanNode newNode = combine2SmallestNode(list.get(0), list.get(1));list.remove(0);list.remove(0); //注意ArrayList中remove元素時的索引移動slist.add(0, newNode);}return list.get(0);}/*** 打印某個節點的樹結構，即以該節點為根節點的子樹結構s* @param node*/public static void print(HuffmanNode node) {System.out.print("| " + node.getData() + "," + node.getPercent() + " |");if(node.getLeftN() != null) {print(node.getLeftN());} if(node.getRightN() != null) {print(node.getRightN());} } /*** 使用冒泡排序，按key值單調遞增排序* * @param list*/public static void srotNodeListByKey(ArrayList<HuffmanNode> list) {for (int i = 0; i < list.size(); i++) {for (int j = i+1; j < list.size(); j++) {if (list.get(i).getPercent() > list.get(j).getPercent()) {// 交換位置list.add(i, list.get(j));list.remove(j+1);list.add(j, list.get(i + 1));list.remove(i + 1);}}}}/*** 將兩個子節點合成為一個父節點* * @param leftNode* @param rightNode* @return*/private static HuffmanNode combine2SmallestNode(HuffmanNode leftNode,HuffmanNode rightNode) {HuffmanNode parentNode = new HuffmanNode(leftNode, rightNode,leftNode.getData() + rightNode.getData(), leftNode.getPercent()+ rightNode.getPercent());return parentNode;}
}/*** 用于表示哈夫曼編碼的二叉樹的節類* * @author wly* */
class HuffmanNode {private HuffmanNode leftN; //左子節點private HuffmanNode rightN; //右子節點private String data; // 包含的數據，本程序中指的是字符private float percent; // 檢索key值public HuffmanNode(HuffmanNode leftN, HuffmanNode rightN, String data,float key) {super();this.leftN = leftN;this.rightN = rightN;this.data = data;this.percent = key;}public float getPercent() {return percent;}public void setPercent(float percent) {this.percent = percent;}public HuffmanNode getLeftN() {return leftN;}public void setLeftN(HuffmanNode leftN) {this.leftN = leftN;}public HuffmanNode getRightN() {return rightN;}public void setRightN(HuffmanNode rightN) {this.rightN = rightN;}public String getData() {return data;}public void setData(String data) {this.data = data;}}
運行結果：
| DBEAC,1.0 || DBE,0.35000002 || DB,0.15 || D,0.05 || B,0.1 || E,0.2 || AC,0.65 || A,0.3 || C,0.35 |
從運行結果可以得到二叉樹如下:
結論：
- 即各個字符的編碼分別是:D:000、D:001、E:01、A:10、C:11
- 若不進行編碼按相同字長編碼，則至少需要3位，那么需要存儲ABCDE的尺寸為:3*1=3
- 編碼后，存儲ABCDE的尺寸為:3*0.05+3*0.1+2*0.2+2*0.3+2*0.2=1.85
- 可見使用哈夫曼編碼能夠在一定程度上實現數據的無損壓縮。
六、總結
貪婪算法就是算法的每一步都是上一步條件下的最好選擇。 貪婪算法得到的是一個近似最優解。 求最小生成樹的Prim算法和Kruskal算法都是漂亮的貪心算法。貪心法的應用算法有Dijkstra的單源最短路徑和Chvatal的貪心集合覆蓋啟發式。貪心算法可以與隨機化算法一起使用，具體的例子就不再多舉了。其實很多的智能算法（也叫啟發式算法），本質上就是貪心算法和隨機化算法結合——這樣的算法結果雖然也是局部最優解，但是比單純的貪心算法更靠近了最優解。例如遺傳算法，模擬退火算法。貪婪算法可以尋找局部最優解，并嘗試與這種方式獲得全局最優解。得到的可能是近似最優解，但也可能便是最優解(區間調度問題，最短路徑問題(廣度優先、狄克斯特拉))。對于完全NP問題，目前并沒有快速得到最優解的解決方案。面臨NP完全問題，最佳的做法就是使用近似算法。貪婪算法(近似算法)在大部分情況下易于實現，并且效率不錯。
我的微信公眾號：架構真經（id：gentoo666），分享Java干貨，高并發編程，熱門技術教程，微服務及分布式技術，架構設計，區塊鏈技術，人工智能，大數據，Java面試題，以及前沿熱門資訊等。每日更新哦！
參考資料：
https://blog.csdn.net/jeffleo/article/details/53526721https://blog.csdn.net/ftl111/article/details/79707452https://www.jianshu.com/p/b613ae9d77ffhttps://www.cnblogs.com/hust-chen/p/8646009.htmlhttps://blog.csdn.net/likunkun__/article/details/80747566https://blog.csdn.net/likunkun__/article/details/80258515https://blog.csdn.net/liufeng_king/article/details/8720896https://blog.csdn.net/u011638883/article/details/16857309
總結
以上是生活随笔為你收集整理的哈夫曼编码压缩率计算_程序员的算法课（8）-贪心算法：理解霍夫曼编码的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
