【問題提出】
學習《演算法設計與分析》課程，有一整章講貪心演算法，坦率地講，貪心演算法本身并不很難，像是任務安排問題、哈夫曼編碼，演算法的思想都十分”單刀直入“，編碼上對于熟練掌握資料結構的準“碼農”們也沒有太大問題，然而貪心法的難度并不在演算法本身，最有挑戰之處還是證明演算法的正確性，
貪心法的設計與證明有一套完整的方法論，在我參加的課程中，老師的PPT是這么講的：
貪心選擇性：若一個優化問題的全域優化解可以通過區域優化選擇得到，則該問題稱為具有貪心選擇性，
最優子結構：若一個優化問題的優化解包含它的子問題的優化解，則稱其具有優化子結構，
PPT上并沒有顯式表明最優子結構和貪心選擇性之間的關系，筆者當時聽課的時候也是云里霧里，一整節課下來，感覺也是精神恍惚，雖然老師的講解基本上都是圍繞著這兩者，但總覺得這兩者之間缺少一些必要的聯系，
例如：在圍繞哈夫曼編碼進行講解時，貪心選擇性和最優子結構引理的證明都很巧妙，一個運用了“剪切-拼貼”法，另一個則是利用了反證法，然而在由引理（貪心選擇性和最優子結構）證明定理（哈夫曼編碼是最優編碼）時，只有短短一句話：
由于引理2（貪心選擇性）、引理3（最優子結構）都成立，而且Huffman演算法按照引理2的貪心選擇性確定的規則進行區域優化選擇，所以Huffman演算法產生一個優化前綴編碼樹，
感覺就是一個“因為1+1=2，所以地球繞著太陽轉”式的句子，那時課程緊張，想要徹底搞清也是有心無力，只好暫且放過了，
【問題解決】
后來復習到這塊，曾經的問題還在那里，必須把這事情搞清楚了！就在網上查找相關資料，查了半天，網上很多博客寫的也是不明不白，照本宣科，沒有自己的思考，后來看到一篇博客對筆者啟發很大，重點主要是開篇兩句：
貪心選擇性：每一步貪心選出來的一定是原問題的最優解的一部分，
最優子結構：每一步貪心選完后會留下子問題，子問題的最優解和貪心選出來的解可以湊成原問題的最優解，
這就明白多了，下面談談筆者的理解：
-
子問題是與原問題相似的一個規模較小的問題，
-
每次在某個問題上進行貪心選擇后，就會產生原問題的一個子問題，打個比方：在任務安排問題中，“在某一個時間段上選擇盡可能多個相容的任務”是原問題，經過“貪心選擇”出一個任務后，余下的時間就比原來變少了，“在余下的時間段上選擇盡可能多個相容的任務”就是一個子問題，
-
貪心選擇性保證了：依照給定演算法，在原問題上進行貪心選擇時，選出的區域優化選擇一定是（整體）最優解的一部分，例如任務安排問題中，選擇結束時間最早的任務，對于整體而言一定是最好的，（當然這是從感性角度理解的貪心選擇性，實際上需要嚴格證明）
-
而優化子結構則保證了：由貪心選擇性得到的區域優化解和子問題的優化解相結合，可以獲得整體優化解，這里可能有些難理解，其實從遞回的角度來理解可能比較好，
在某一個問題上，給定演算法可以通過貪心來生成一個區域最優和一個子問題，遞回地呼叫給定演算法，作用在子問題上，可以獲得子問題的優化解，
然而子問題優化解，和當前問題的區域優化解拼在一起，一定是整體優化解嗎？未必，（筆者暫時找不到好的例子）而優化子結構就解決了這個問題，原問題的區域優化解與子問題的優化解拼湊起來，經過優化子結構的保證，就是原問題整體的最優解，
【一個栗子】
說到這，相比讀者心中的疑惑也能解開一二，具體來看哈夫曼編碼正確性證明的栗子，幫助讀者理解，
【演算法】
在字符集Charset中，回圈地選擇具有最低頻率的兩個字符x y作為兩片葉子，建立父節點節點z，生成一棵子樹，
將z作為新字符插入Charset中，并在Charset中洗掉x y，z的頻率為x y頻率之和，
繼續上述回圈，直至所有結點形成一棵樹，此時葉子結點為初始Charset中的字符，而形成的樹則為一棵最優二叉樹，
【貪心選擇性】
令Charset為給定字符集，且x y為其中頻率最低的兩個字符，則Charset上存在一個最優編碼樹T滿足：x y的碼字長度相同，且僅有最后一位不同，（x y對應結點為兄弟節點）
【最優子結構】
令Charset為給定字符集，且x y為其中頻率最低的兩個字符，令Charset'為去掉字符x y，加入字符z得到的字符集，不同之處僅在于z的頻率為x y頻率之和，令T'為Charset'上的一個最優編碼樹，將T' 中z對應的結點替換為一個孩子為x y的內部結點，得到樹T，則T為字符集Charset的一個最優編碼樹，
【對于總證明的說明】
對于一個在字符集Charset上的最優編碼問題，根據【貪心選擇性】，可以先找到Charset 之中頻率最低的兩個字符x y，將x y按照【最優子結構】中的方法替換為z，得到規模減1的字符集Charset'，在Charset'之中遞回呼叫本演算法，即可得到Charset'上的最優編碼樹，再將Charset'上的最優編碼樹按照【最優子結構】的方法替換為含x y的子樹，就得到了Charset上的一個最優編碼樹，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/196896.html
標籤：其他
上一篇：前端面試題