37贪心算法:如何用贪心算法实现Huffman压缩编码?.pdf
《37贪心算法:如何用贪心算法实现Huffman压缩编码?.pdf》由会员分享,可在线阅读,更多相关《37贪心算法:如何用贪心算法实现Huffman压缩编码?.pdf(14页珍藏版)》请在三一文库上搜索。
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 全局最优解了。 贪心算法实战分析 对于贪心算法,你是不是还有点
8、懵?如果死抠理论的话,确实很难理解透彻。掌握贪心算法的关键是多练习。只要多练习几道题,自然就有感觉了。所以,我带 着你分析几个具体的例子,帮助你深入理解贪心算法。 1.分糖果 我们有m个糖果和n个孩子。我们现在要把糖果分给这些孩子吃,但是糖果少,孩子多(mn),所以糖果只能分配给一部分孩子。 每个糖果的大小不等,这m个糖果的大小分别是s1,s2,s3,sm。除此之外,每个孩子对糖果大小的需求也是不一样的,只有糖果的大小大于等于孩子的对 糖果大小的需求的时候,孩子才得到满足。假设这n个孩子对糖果大小的需求分别是g1,g2,g3,gn。 我的问题是,如何分配糖果,能尽可能满足最多数量的孩子? 我们
9、可以把这个问题抽象成,从n个孩子中,抽取一部分孩子分配糖果,让满足的孩子的个数(期望值)是最大的。这个问题的限制值就是糖果个数m。 我们现在来看看如何用贪心算法来解决。对于一个孩子来说,如果小的糖果可以满足,我们就没必要用更大的糖果,这样更大的就可以留给其他对糖果大小需求 更大的孩子。另一方面,对糖果大小需求小的孩子更容易被满足,所以,我们可以从需求小的孩子开始分配糖果。因为满足一个需求大的孩子跟满足一个需求小 的孩子,对我们期望值的贡献是一样的。 我们每次从剩下的孩子中,找出对糖果大小需求最小的,然后发给他剩下的糖果中能满足他的最小的糖果,这样得到的分配方案,也就是满足的孩子个数最多的 方案
10、。 2.钱币找零 这个问题在我们的日常生活中更加普遍。假设我们有1元、2元、5元、10元、20元、50元、100元这些面额的纸币,它们的张数分别 是c1、c2、c5、c10、c20、c50、c100。我们现在要用这些钱来支付K元,最少要用多少张纸币呢? 在生活中,我们肯定是先用面值最大的来支付,如果不够,就继续用更小一点面值的,以此类推,最后剩下的用1元来补齐。 在贡献相同期望值(纸币数目)的情况下,我们希望多贡献点金额,这样就可以让纸币数更少,这就是一种贪心算法的解决思路。直觉告诉我们,这种处理方法 就是最好的。实际上,要严谨地证明这种贪心算法的正确性,需要比较复杂的、有技巧的数学推导,我不
11、建议你花太多时间在上面,不过如果感兴趣的话,可以 自己去研究下。 3.区间覆盖 假设我们有n个区间,区间的起始端点和结束端点分别是l1, r1,l2, r2,l3, r3,ln, rn。我们从这n个区间中选出一部分区间,这部分区间满足两两不相 交(端点相交的情况不算相交),最多能选出多少个区间呢? 37|贪心算法:如何用贪心算法实现Huffman压缩编码? file:/F/temp/geektime/数据结构与算法之美/37贪心算法:如何用贪心算法实现Huffman压缩编码?.html2019/1/15 15:36:23 这个问题的处理思路稍微不是那么好懂,不过,我建议你最好能弄懂,因为这个处
12、理思想在很多贪心算法问题中都有用到,比如任务调度、教师排课等等问题。 这个问题的解决思路是这样的:我们假设这n个区间中最左端点是lmin,最右端点是rmax。这个问题就相当于,我们选择几个不相交的区间,从左到右将lmin, rmax覆盖上。我们按照起始端点从小到大的顺序对这n个区间排序。 我们每次选择的时候,左端点跟前面的已经覆盖的区间不重合的,右端点又尽量小的,这样可以让剩下的未覆盖区间尽可能的大,就可以放置更多的区间。这实 际上就是一种贪心的选择方法。 37|贪心算法:如何用贪心算法实现Huffman压缩编码? file:/F/temp/geektime/数据结构与算法之美/37贪心算法:
13、如何用贪心算法实现Huffman压缩编码?.html2019/1/15 15:36:23 解答开篇 今天的内容就讲完了,我们现在来看开篇的问题,如何用贪心算法实现霍夫曼编码? 假设我有一个包含1000个字符的文件,每个字符占1个byte(1byte=8bits),存储这1000个字符就一共需要8000bits,那有没有更加节省空间的存储方式呢? 37|贪心算法:如何用贪心算法实现Huffman压缩编码? file:/F/temp/geektime/数据结构与算法之美/37贪心算法:如何用贪心算法实现Huffman压缩编码?.html2019/1/15 15:36:23 假设我们通过统计分析发现
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 37 贪心 算法 何用 实现 Huffman 压缩 编码
链接地址:https://www.31doc.com/p-5529886.html