春节7天练Day1:数组和链表.pdf
《春节7天练Day1:数组和链表.pdf》由会员分享,可在线阅读,更多相关《春节7天练Day1:数组和链表.pdf(16页珍藏版)》请在文库网上搜索。
1、37|贪心算法:如何用贪心算法实现Huffman压缩编码? file:/F/temp/geektime/数据结构与算法之美/37贪心算法:如何用贪心算法实现Huffman压缩编码?.html2019/1/15 15:36:23 37|贪心算法:如何用贪心算法实现Huffman压缩编码? 基础的数据结构和算法我们基本上学完了,接下来几节,我会讲几种更加基本的算法。它们分别是贪心算法、分治算法、回溯算法、动态规划。更加确切地说, 它们应该是算法思想,并不是具体的算法,常用来指导我们设计具体的算法和编码等。 贪心、分治、回溯、动态规划这4个算法思想,原理解释起来都很简单,但是要真正掌握且灵活应用,并
2、不是件容易的事情。所以,接下来的这4个算法思想的讲 解,我依旧不会长篇大论地去讲理论,而是结合具体的问题,让你自己感受这些算法是怎么工作的,是如何解决问题的,带你在问题中体会这些算法的本质。我 觉得,这比单纯记忆原理和定义要更有价值。 今天,我们先来学习一下贪心算法(greedy algorithm)。贪心算法有很多经典的应用,比如霍夫曼编码(Huffman Coding)、Prim和Kruskal最小生成树算法、还 有Dijkstra单源最短路径算法。最小生成树算法和最短路径算法我们后面会讲到,所以我们今天讲下霍夫曼编码,看看它是如何利用贪心算法来实现对数据压缩编 码,有效节省数据存储空间的
3、。 如何理解“贪心算法”? 关于贪心算法,我们先看一个例子。 假设我们有一个可以容纳100kg物品的背包,可以装各种物品。我们有以下5种豆子,每种豆子的总量和总价值都各不相同。为了让背包中所装物品的总价值最 大,我们如何选择在背包中装哪些豆子?每种豆子又该装多少呢? 37|贪心算法:如何用贪心算法实现Huffman压缩编码? file:/F/temp/geektime/数据结构与算法之美/37贪心算法:如何用贪心算法实现Huffman压缩编码?.html2019/1/15 15:36:23 实际上,这个问题很简单,我估计你一下子就能想出来,没错,我们只要先算一算每个物品的单价,按照单价由高到低
4、依次来装就好了。单价从高到低排列,依 次是:黑豆、绿豆、红豆、青豆、黄豆,所以,我们可以往背包里装20kg黑豆、30kg绿豆、50kg红豆。 这个问题的解决思路显而易见,它本质上借助的就是贪心算法。结合这个例子,我总结一下贪心算法解决问题的步骤,我们一起来看看。 第一步,当我们看到这类问题的时候,首先要联想到贪心算法:针对一组数据,我们定义了限制值和期望值,希望从中选出几个数据,在满足限制值的情况下, 期望值最大。 类比到刚刚的例子,限制值就是重量不能超过100kg,期望值就是物品的总价值。这组数据就是5种豆子。我们从中选出一部分,满足重量不超过100kg,并且总价 值最大。 第二步,我们尝试
5、看下这个问题是否可以用贪心算法解决:每次选择当前情况下,在对限制值同等贡献量的情况下,对期望值贡献最大的数据。 类比到刚刚的例子,我们每次都从剩下的豆子里面,选择单价最高的,也就是重量相同的情况下,对价值贡献最大的豆子。 37|贪心算法:如何用贪心算法实现Huffman压缩编码? file:/F/temp/geektime/数据结构与算法之美/37贪心算法:如何用贪心算法实现Huffman压缩编码?.html2019/1/15 15:36:23 第三步,我们举几个例子看下贪心算法产生的结果是否是最优的。大部分情况下,举几个例子验证一下就可以了。严格地证明贪心算法的正确性,是非常复杂 的,需要涉
6、及比较多的数学推理。而且,从实践的角度来说,大部分能用贪心算法解决的问题,贪心算法的正确性都是显而易见的,也不需要严格的数学推导证 明。 实际上,用贪心算法解决问题的思路,并不总能给出最优解。 我来举一个例子。在一个有权图中,我们从顶点S开始,找一条到顶点T的最短路径(路径中边的权值和最小)。贪心算法的解决思路是,每次都选择一条跟当前 顶点相连的权最小的边,直到找到顶点T。按照这种思路,我们求出的最短路径是S-A-E-T,路径长度是1+4+4=9。 但是,这种贪心的选择方式,最终求的路径并不是最短路径,因为路径S-B-D-T才是最短路径,因为这条路径的长度是2+2+2=6。为什么贪心算法在这个
7、问题 上不工作了呢? 在这个问题上,贪心算法不工作的主要原因是,前面的选择,会影响后面的选择。如果我们第一步从顶点S走到顶点A,那接下来面对的顶点和边,跟第一步从顶 点S走到顶点B,是完全不同的。所以,即便我们第一步选择最优的走法(边最短),但有可能因为这一步选择,导致后面每一步的选择都很糟糕,最终也就无缘 37|贪心算法:如何用贪心算法实现Huffman压缩编码? file:/F/temp/geektime/数据结构与算法之美/37贪心算法:如何用贪心算法实现Huffman压缩编码?.html2019/1/15 15:36:23 全局最优解了。 贪心算法实战分析 对于贪心算法,你是不是还有点
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 春节 Day1 数组