什么是贪心算法

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

实例理解贪心算法

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

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

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

• 贪心选择

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

• 最优子结构

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

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

编码原理

哈夫曼编码是一种变长编码方式，通俗来说就是如果给定一段文字或者一段字符，在这里面出现次数多的字符的编码长度更短，比如给定“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中只有一棵二叉树为止。