贪心算法：贪心选择性？优化子结构？

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了贪心算法：贪心选择性？优化子结构？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3843字，纯文字阅读大概需要6分钟。

内容图文

【问题提出】

学习《算法设计与分析》课程，有一整章讲贪心算法。坦率地讲，贪心算法本身并不很难，像是任务安排问题、哈夫曼编码，算法的思想都十分”单刀直入“，编码上对于熟练掌握数据结构的准“码农”们也没有太大问题。然而贪心法的难度并不在算法本身，最有挑战之处还是证明算法的正确性。

贪心法的设计与证明有一套完整的方法论。在我参加的课程中，老师的PPT是这么讲的：

1. 贪心选择性：若一个优化问题的全局优化解可以通过局部优化选择得到，则该问题称为具有贪心选择性。

2. 最优子结构：若一个优化问题的优化解包含它的子问题的优化解，则称其具有优化子结构。

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上的一个最优编码树。

内容总结

以上是互联网集市为您收集整理的贪心算法：贪心选择性？优化子结构？全部内容，希望文章能够帮你解决贪心算法：贪心选择性？优化子结构？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---