贪心算法 greedy algorithm

如何理解“贪心算法”？

假设我们有一个可以容纳 100kg 物品的背包，可以装各种物品。我们有以下 5 种豆子，每种豆子的总量和总价值都各不相同。为了让背包中所装物品的总价值最大，我们如何选择在背包中装哪些豆子？每种豆子又该装多少呢？

解题思路：我们只要先算一算每个物品的单价，按照单价由高到低依次来装就好了。单价从高到低排列，依次是：黑豆、绿豆、红豆、青豆、黄豆，所以，我们可以往背包里装 20kg 黑豆、30kg 绿豆、50kg 红豆。

贪心算法解决问题的步骤：

• 当我们看到这类问题的时候，首先要联想到贪心算法：
  • 针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。
  • 类比到刚刚的例子，限制值就是重量不能超过 100kg，期望值就是物品的总价值。这组数据就是 5 种豆子。我们从中选出一部分，满足重量不超过 100kg，并且总价值最大。
• 我们尝试看下这个问题是否可以用贪心算法解决：
  • 每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。
  • 类比到刚刚的例子，我们每次都从剩下的豆子里面，选择单价最高的，也就是重量相同的情况下，对价值贡献最大的豆子。
• 我们举几个例子看下贪心算法产生的结果是否是最优的：
  • 大部分情况下，举几个例子验证一下就可以了。
    • 严格地证明贪心算法的正确性，是非常复杂的，需要涉及比较多的数学推理。
    • 而且，从实践的角度来说，大部分能用贪心算法解决的问题，贪心算法的正确性都是显而易见的，也不需要严格的数学推导证明。

为什么用贪心算法解决问题的思路，并不总能给出最优解。

• 在一个有权图中，我们从顶点 S 开始，找一条到顶点 T 的最短路径（路径中边的权值和最小）。
  • 贪心算法的解决思路是，每次都选择一条跟当前顶点相连的权最小的边，直到找到顶点 T。
  • 按照这种思路，我们求出的最短路径是 S->A->E->T，路径长度是 1+4+4=9。
  • 但是，这种贪心的选择方式，最终求的路径并不是最短路径，因为路径 S->B->D->T 才是最短路径，因为这条路径的长度是 2+2+2=6。
• 为什么贪心算法在这个问题上不工作了呢？
  • 贪心算法不工作的主要原因是，前面的选择，会影响后面的选择。
    • 如果我们第一步从顶点 S 走到顶点 A，那接下来面对的顶点和边，跟第一步从顶点 S 走到顶点 B，是完全不同的。
    • 所以，即便我们第一步选择最优的走法（边最短），但有可能因为这一步选择，导致后面每一步的选择都很糟糕，最终也就无缘全局最优解了。

用贪心算法实现Huffman压缩编码

假设我有一个包含 1000 个字符的文件，每个字符占 1 个 byte（1byte=8bits），存储这 1000 个字符就一共需要 8000bits，那有没有更加节省空间的存储方式呢？

假设我们通过统计分析发现，这 1000 个字符中只包含 6 种不同字符，假设它们分别是 a、b、c、d、e、f。而 3 个二进制位（bit）就可以表示 8 个不同的字符，所以，为了尽量减少存储空间，每个字符我们用 3 个二进制位来表示。那存储这 1000 个字符只需要 3000bits 就可以了，比原来的存储方式节省了很多空间。不过，还有没有更加节省空间的存储方式呢？

这是时候就需要霍夫曼编码了，霍夫曼编码是一种十分有效的编码方法，广泛用于数据压缩中，其压缩率通常在 20%～90% 之间。

霍夫曼编码不仅会考察文本中有多少个不同字符，还会考察每个字符出现的频率，根据频率的不同，选择不同长度的编码。

• 霍夫曼编码试图用这种不等长的编码方法，来进一步增加压缩的效率。
• 如何给不同频率的字符选择不同长度的编码呢？
  • 根据贪心的思想，我们可以把出现频率比较多的字符，用稍微短一些的编码；出现频率比较少的字符，用稍微长一些的编码。
  • 霍夫曼编码是不等长的，每次应该读取 1 位还是 2 位、3 位等等来解压缩呢？这个问题就导致霍夫曼编码解压缩起来比较复杂。
    • 为了避免解压缩过程中的歧义，霍夫曼编码要求各个字符的编码之间，不会出现某个编码是另一个编码前缀的情况。

假设这 6 个字符出现的频率从高到低依次是 a、b、c、d、e、f。我们把它们编码下面这个样子，任何一个字符的编码都不是另一个的前缀，在解压缩的时候，我们每次会读取尽可能长的可解压的二进制串，所以在解压缩的时候也不会歧义。经过这种编码压缩之后，这 1000 个字符只需要 2100bits 就可以了。

如何根据字符出现频率的不同，给不同的字符进行不同长度的编码呢？

• 我们把每个字符看作一个节点，将它们按频率大小放到优先级队列(小顶堆)中。

• 我们从队列中取出频率最小的两个节点 A、B，
• 然后新建一个节点 C，把频率设置为两个节点的频率之和，并把这个新节点 C 作为节点 A、B 的父节点。

• 最后再把 C 节点放入到优先级队列中。

重复这个过程，直到队列中没有数据。最后，我们可以得到一颗二叉树，

• 给每一条边加上画一个权值，
  • 指向左子节点的边我们统统标记为 0，
  • 指向右子节点的边，我们统统标记为 1，
• 那从根节点到叶节点的路径就是叶节点对应字符的霍夫曼编码。

上一篇 « 二分查找 下一篇 » 分治算法 divide and conquer