貪心算法：貪心選擇性與優化子結構
【問題提出】
學習《算法設計與分析》課程，有一整章講貪心算法。坦率地講，貪心算法本身並不很難，像是任務安排問題、哈夫曼編碼，算法的思想都十分」單刀直入「，編碼上對於熟練掌握數據結構的准「碼農」們也沒有太大問題。然而貪心法的難度並不在算法本身，最有挑戰之處還是證明算法的正確性。
貪心法的設計與證明有一套完整的方法論。在我參加的課程中，老師的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上的一個最優編碼樹。
