贪婪算法 - 简书

贪婪算法分阶段工作，在每一个阶段，可以认为所做决定是好的，而不考虑将来的后果。通常，这意味着选择的是某个局部最优。当算法终止时，我们希望局部最优等于全局最优。如果是这样的话，那么算法就是正确的；否则，算法得到的是一个次最优解。

下面介绍一些贪婪算法的应用。

哈夫曼编码

哈夫曼编码可用于文件压缩。

假设我们有一个文件，它只包含字符a，e，i，s，t，空格，换行（newline）。设该文件有10个a，15个e，12个i，3个s，4个t，13个空格，1个换行。如下图所示，次文件需要174比特来表示，因为共有58个字符，而每个字符需要3个比特。

考虑如何对上述编码进行改进，从而用更少的比特数表示该文件。我们首先将上述的标准编码方案使用字典树（trie树）表示。用0表示左分支，用1表示右分支，所有的字符都在叶子节点上，节点的深度即对应字符的编码的长度。

一种比上述稍好一点的编码是将newline符号放到其更高一层的父节点上。newline符号仍然处于叶子节点上，保证了所有字符都只放在树叶上。之所要保证所有的字符都只放在树叶上，是为了使得所有字符的编码都不会是另外一个编码的前缀，从而使得任何比特序列总能够被毫不含糊地译码。这样的编码又叫做前缀码（prefix code）。

对于一种编码方案，用其表示一个文件，所需要的总比特数（cost）为： $cost = \sum d_{i}f_{i}$ 其中 $d_{i}$ 表示字符i的深度， $f_{i}$ 表示字符在文件中出现的次数（频率）。所以为了使得cost取得最小值，一种思路是 $f_{i}$ 越大的字符，我们令其 $d_{i}$ 越小。即出现频率越高的字符，在编码中，令其编码长度越小。这就是哈夫曼算法的思想。

哈夫曼算法（Huffman's algorithm）描述如下：
算法是针对由树组成的一个森林进行（一个字符就是一棵单节点树，上面的例子中有7个字符，就是7棵单节点树构成的森林），假设初始森林中共有C棵单节点树，即C个字符。
1.一棵树的权等于它的所有叶子节点的频率的和。（单节点的树即该节点的频率）。
2.选取最小权的两棵树T1和T2，并任意形成以T1和T2位子树的新树，将这样的过程进行C-1次。算法结束时，得到一颗树。

最后得到的二叉树的编码方式，其实就是最优前缀码，如下图所示。

该算法是贪婪算法的原因在于，在每一阶段我们都进行一次合并而没有进行全局的考虑，我们只是选择两颗最小的树。

近似装箱问题

考虑解决装箱问题的算法。这些算法将运行得很快，单未必产生最优解，然而，可以证明所产生的解距离最优解不太远。

设给定N项物品，大小为 $s_{1},s_{2},...,s_{N}$ ，所有大小都满足 $0<s_{i}<1$ 。问题是把这些物品装到最下数目的箱子中去，每个箱子的容量为1个单位。举例如下。

联机装箱问题（on-line bin packing problem）
在这种问题中，每一件物品必须放入一个箱子之后才能处理下一件物品。

脱机装箱问题（off-line bin packing problem）
在一个脱机装箱算法中，我们做任何事都需要等到所有的输入数据全被读取之后才进行。

联机算法
对于联机装箱问题，可证明，及时允许无限计算能力，也不总能够给出最优解。
1.首次适合算法
依序扫描所有箱子，并把新的一项物品放入足能盛下它的第一个箱子中。只有当前面那些放置物品的箱子已经容不下当前物品的时候，才开辟一个新的箱子。
可证明，假设M是最优箱子数，使用首次适合算法使用箱子数绝不多余 $\left \lceil \frac{17}{10}M \right \rceil$ 。
2.最佳适合算法
该算法不是把一项新物品放入所发现的第一个能够容纳它的箱子，而是放到所有箱子中能够容纳它的最满的箱子中。
此算法的使用箱子数的上届与首次适合算法相同。

脱机算法
所有联机算法的主要问题在于将大项物品装箱困难，特别是在输入的后期出现的时候。所以围绕这个问题的自然解决办法是先将各项物品排序，把最大的物品先装箱。
1.首次适合递减算法
先排序，然后应用首次适合算法装箱。
2.最佳适合递减算法
先排序，然后应用最佳适合算法装箱。
以上两种算法使用的箱子数绝不超过 $\frac{4M+1}{3}M$ 。