1樓：鄭啟威
雖然Huffman編碼的策略是出現次數多的字元具有短的編碼，但是這並不是乙個貪心策略。
貪心策略必須具備無後效性,即某個狀態以前的過程不會影響以後的狀態,只與當前狀態有關。
但是在使用字首碼的情況下，按照該策略，前乙個頻繁的字元的編碼，會影響後面字元編碼的選擇。
比如 a b c d e f
次數為 10 8 5 3 2 1
按照貪心策略 a取最短的1bit 比如0 接下來 b就只能出取2bit 比如 10
但是實際上最優編碼是 a與b都應編碼為 2bit
所以這個策略並不是乙個貪心策略。如果沒有字首碼的約束，那麼這個策略是貪心的，這樣a,b兩個最大的就使用1bit來編碼。
如果仔細觀察會發現，按照這種策略構造編碼樹的過程是一種自上而下的過程。
《演算法設計》120頁裡面還提到了一種自頂向下的策略，它每次將字符集分成兩個集合，使得兩個集合中字元的頻率之和盡可能的相等。但也是失敗的策略。
而最終使用的Huffman演算法，則是一種自下向上的構造方法，演算法設計123頁，講到了貪心規則——把兩個最小頻率的字母合併。我談談我個人的理解，也不知道是否正確。
實際上體現的就是頻率低的字元具有長的編碼。雖然這個描述與前面的策略是一樣的。但是關鍵之處在於每一步執行的時候，我並不知道這個低頻率的字元會編碼為多少，我只保證它在樹的最小面，使用最長的編碼，這樣就不會影響頻率高的字元的編碼了。
而每一步貪心的過程，都將兩個頻率低的字元合成乙個父字元，減小了問題的規模，這樣這個策略就在不影響其它字元編碼的情況下，不斷縮小問題的規模。
2樓：嘿-姑娘
樓上講的太過複雜了~~~~
簡單講就是 ：讓出現次數多的字元用盡量短的編碼，但是為了保證整個資料空間的完備性只能讓那些出現次數少的用長的編碼。
上面講的盡量就是貪心
3樓：
通過自己在網上查資料，大概有了一些了解，這裡解釋一下自己的想法，希望有相同疑問的同學可以有乙個參考，同時謬誤之處希望各位指正。
華麗的分割線
霍夫曼編碼本身並不是乙個很難的技巧，我想到這個問題主要也是因為看到的某篇文裡提到了其中用到了貪心的思想，鑑於本人渣渣的英文以及懶B的心態，於是跑到知乎來提了這麼乙個沒頭沒腦的問題。好了，題外話說完，言歸正傳，霍夫曼編碼是一種廣泛的用於資料檔案壓縮的十分有效的編碼方法，其壓縮率通常在20%~90%之間。
假設我有乙個有10000個字元的文字，那麼每個字元就是1位元組(1byte=8bit)，一共就是80000bit，現在我要把它壓縮，OK，假設這個文字中一共出現的只有六個字元如下(k=千次)
a(45k) b(13k) c(12k) d(16k) e(9k) f(5k)
按照最直觀的思路，既然只有6個字元，那我們就把每個字元用3個bit位來表示(3個bit位足夠表示7個字元)，那這樣文字就可以用30000bit表示出來，壓縮率為37.5%。
a b c d e f
45k 13k 12k 16k 9k 5k
000 001 010 011 100 101
按照霍夫曼編碼的思路，基於字元出現的頻率，我們這裡可以用貪婪的思想，把頻率出現的高的數字用少一些的bit位表示，頻率低的字元用多一些的bit位表示，並保證互相之間不會出現字首的情況，這樣總共 (45*1+13*3+12*3+16*3+9*4+5*4)*1000=224000bit。壓縮率達到了22.4%，比之前的演算法壓縮率提高了15%，可以看見確實是比原來更優的演算法。
a b c d e f
45k 13k 12k 16k 9k 5k
0 101 100 110 1111 1110
貪心演算法 啟發式演算法 近似演算法 區別？
Coldwings 近似演算法是乙個大類。所有對於有確切最優解但是並不能保證得到最優解的演算法都可以稱之為近似演算法。貪心演算法不一定就是近似演算法，如果可以證明決策既不受之前決策的影響，也不影響後續決策，則貪心演算法就是確定的最優解演算法。除此之外都不可以保證貪心演算法是最優的。這裡有個很有意思的...
刷題時，遇見過哪些巧妙的貪心演算法的題目？
lndjy EZEC 6 造樹 洛谷 比較巧妙的貪心，把看起來很難搞的樹限制和度數限制變成乙個容易處理的合併策略，然後可以暴力 資料結構優化 單調性優化，對應30 80 100分的做法。比較有趣和巧妙吧，被 rqy 表揚過 我是出題人，但是這個做法是乙個神仙花了很長時間想出來的。 疏簾淡月 lc 9...
生物演化是類似貪心演算法嗎？如果是，那麼在演化出完整功能前為什麼知道這個功能有利？
老董 生物演化是遺傳加變異加自然選擇的結果，遺傳加變異得到的性狀是隨機的，小概率得到有利的性狀，大概率得到不利的性狀。有利的性狀更容易獲得生存優勢，不利的性狀容易被自然選擇淘汰 一代代篩選下來，保留下來的性狀就幾乎或者全部是有利的。 生物演化是變異 自然選擇的結果啊！變異是沒有方向的，有好的變異也有...