贪心算法

  • 时间:2019-03-26 01:10 作者:于无声处听 来源:于无声处听 阅读:39
  • 扫一扫,手机访问
摘要:什么是贪心算法贪心算法是一种求可行解的算法,它并不像遗传算法一样可以求出全局最优解,贪心算法只是为了求出可行解,并不肯定是最优的。实例了解贪心算法有一堆大小不同的包裹需要装到箱子里,假如用贪心算法实现的话,那么方式就是先拣大个的包裹往箱子里塞,至于以后的事他就不论了,每次都是先挑出最大的包裹装在箱子

什么是贪心算法

贪心算法是一种求可行解的算法,它并不像遗传算法一样可以求出全局最优解,贪心算法只是为了求出可行解,并不肯定是最优的。

实例了解贪心算法

有一堆大小不同的包裹需要装到箱子里,假如用贪心算法实现的话,那么方式就是先拣大个的包裹往箱子里塞,至于以后的事他就不论了,每次都是先挑出最大的包裹装在箱子里。

如何确定一个问题能否能采用贪心算法求解呢

首先,贪心算法有两个性质

  • 贪心选择

什么叫贪心选择?从字义上就是贪心也就是目光短线。贪图眼前利益。在算法中就是仅仅依据当前已有的信息就做出选择,并且以后都不会改变这次选择。(这是和动态规划法的主要差别)  
所以对于一个详细问题。要确定它能否具备贪心选择性质,必需证实每做一步贪心选择能否终于导致问题的总体最优解。

  • 最优子结构

当一个问题的最优解包括其子问题的最优解时,称此问题具备最优子结构性质。
这个性质和动态规划法的一样,最优子结构性质是可用动态规划算法或者贪心算法求解的关键特征。

贪心算法实例-------哈夫曼编码

编码原理

哈夫曼编码是一种变长编码方式,浅显来说就是假如给定一段文字或者者一段字符,在这里面出现次数多的字符的编码长度更短,比方给定“ABABDGDBAAA”这样一段字符串,显著看出A出现的次数最多,所以他的权重值更大。按照权重值从小到大的顺序先进行排列,取出权重值最小的两个构成一棵二叉树的左右孩子节点,父节点的权重值就是两个孩子节点权重值的加和。将两个孩子节点删除,让新的父节点加入到排列顺序当中,继续选出新的两个最小权重值重复上述动作,直到最后形成一个根节点。而后将最终形成的树的根节点编码为0,所有的左孩子节点也编码为0,右孩子节点为1,则每个字符的编码就是从根节点到该字符节点的路径编码。

图文解释

image
image

关于具体的哈夫曼树的数据结构可以参考数据结构书上的二叉树章节。

编码步骤

哈夫曼编码步骤:

  • 对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空。(为方便在计算机上实现算 法,一般还要求以Ti的权值Wi的升序排列。)
  • 在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和。
  • 从F中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中。
  • 重复二和三两步,直到集合F中只有一棵二叉树为止。
  • 全部评论(0)
最新发布的资讯信息
【系统环境|服务器应用】前台开发入门到实战:HTML5语义化元素你真的用的正确吗?(2019-08-22 04:16)
【系统环境|服务器应用】Vue仿微信app页面跳转动画(2019-08-22 04:16)
【系统环境|服务器应用】webstorm使用快捷键快速修正单个文件的style(2019-08-22 04:16)
【系统环境|服务器应用】程序员从学生到阿里经历的5次蜕变:海阔凭鱼跃,天高任鸟飞(2019-08-22 04:16)
【系统环境|服务器应用】var、let、const的区别(2019-08-22 04:16)
【系统环境|服务器应用】mini-ui加载框Indicator 被遮挡问题(2019-08-22 04:15)
【系统环境|服务器应用】【对讲机的那点事】玩对讲机,对于对讲机的亚音你理解吗?(2019-08-22 04:15)
【系统环境|服务器应用】前台中高级面试,内功心法(上)(2019-08-22 04:15)
【系统环境|服务器应用】17、改进轮播图之功能封装(2019-08-22 04:15)
【系统环境|服务器应用】第10题- 你不知道的delete操作符(2019-08-22 04:15)
手机二维码手机访问领取大礼包
返回顶部