算法设计技巧: 贪心算法(Greedy Algorithm)

贪心算法是一种启发式(Heuristic)算法, 它的基本思想是在每一步决策时选择局部最优的策略. 贪心算法一般在设计和实现上比较容易, 因此在求解实际问题中应用广泛.

编码问题

考虑如下的编码问题: 给定字符的集合$C$, 例如 C = { a , b , c , d , e } C=\{a, b, c, d, e\} C={ a,b,c,d,e}. 每个字符$\alpha \in C$的使用频次为$f_{\alpha }$. 我们需要给每个字符$\alpha \in C$进行二进制编码(字符$\alpha$对应的编码长度记作$l_{\alpha }$). 总的编码长度的计算公式为: $L={\sum }_{\alpha \in C}{f}_{\alpha }?l_{\alpha }$. 我们的目标是设计一种编码使得总的编码长度最小.

如上表所示, 考虑两种编码: 定长编码和变长编码. 其中变长编码为前缀码: 任一字符的编码不是另一字符编码的前缀.

• 定长编码总长度: 300bits
• 变长编码总长度: 224bits

变长编码的解码过程如下: 根据字符编码构造一棵二叉树, 每一个二进制位代表一个分支(和对应的节点), 其中0代表向左分支, 1代表向右分支, 叶子节点代表字符. 解码时从根节点开始搜索直到叶子节点, 则完成一个字符的解码. 例如: 110001001101 = face.

Huffman编码

为了方便理解, 我们把上述编码问题换一种表达方式. 令$T$代表变长码对应的二叉树, $d_{\alpha }^T$代表叶子节点$\alpha$的深度(Depth, 即编码长度). 我们的目标是构造二叉树$T^{?}$, 使得${\sum }_{\alpha \in C}{d}_{\alpha }^{T^{?}}{f}_{\alpha }$最小化.

通过分析(过程省略, 详细请参考¹), 我们有如下结论

• Lemma1. $T^{?}$的每个内部点(即非叶子节点)有两个节点. （反证法)
• Lemma2. $T^{?}$有|C|个叶子节点(对应每个字符)和$|C|?1$个内部点(Lemma1).

根据Lemma2, 我们从下到上构建二叉树. 注意到节点的深度代表了编码的长度, 因此频次越低的字符所在的节点越深.

算法

从$C$中弹出2个频次最低的字符$\alpha ,\beta$, 并构造新的节点$\alpha \beta$, $f_{\alpha \beta }=f_{\alpha }+f_{\beta }$, 作为$\alpha$和$\beta$的父节点, 再把$\alpha \beta$加入到$C$中. 循环执行上述步骤直到$C$为空(注意: 循环次数为$n?1$次).

Python实现

定义二叉树的节点类Node.

class Node(object):def __init__(self):# dataself.char = None  # characterself.freq = None  # frequency# pointersself.left = None  # left childself.right = None  # right child

HuffmanCodes类实现对字符串的编码与解码. 编码本质上是按照上述贪心算法自下而上构建二叉树(参考HuffmanCodes._build_binary_tree()). 解码时从二叉树的根节点搜索到叶子节点(0-代表left child, 1代表-right child), 从而得到对应的字符(HuffmanCodes._decode).

import queueclass HuffmanCodes(object):def __init__(self, c, f):""":param c: characters, str list:param f: frequencies, int list"""self._c = cself._f = fself._n = len(self._c)self._q = self._init_priority_queue()self._root = None  # encoding treeself._huffman_codes = {
    }  # 编码结果self._build_binary_tree() # 构建二叉树self._format_huffman_codes()  # 保存编码结果def _init_priority_queue(self):""" 初始化优先队列.priority = frequency, value = node使用优先队列可以在O(log n)内返回队列的最小值(代价是插入元素的耗时为O(log n))."""q = queue.PriorityQueue()for item in zip(self._c, self._f):v = Node()v.char, v.freq = item[0], item[1]q.put((v.freq, v))return qdef _build_binary_tree(self):""" 自下而上构建二叉树.Greedy: 每一步从未被连接的节点中, 选择频次(frequency)最小的两个节点合并(作为新的节点)."""for i in range(self._n - 1):z = Node()# 从队列里弹出两个最小权重的节点,合并成新的节点zz.left = self._q.get()[1]z.right = self._q.get()[1]z.freq = z.left.freq + z.right.freq# 把z插入到队列中self._q.put((z.freq, z))# 执行n-1步之后, 队列q剩下一个元素,即二叉树的根节点.self._root = self._q.get()[1]def _format_huffman_codes(self):""" 把每一个字符对应的编码保存在字典中(self._huffman_codes)"""temp = []def traverse(v, res):if v.left is None and v.right is None:self._huffman_codes[v.char] = ''.join(res)returnres.append('0')traverse(v.left, res)res.pop(-1)res.append('1')traverse(v.right, res)res.pop(-1)traverse(self._root, temp)def encode(self, chars):""" 把字符串chars转换成Huffman codes."""return ''.join([self._huffman_codes[c] for c in chars])def decode(self, codes):""" 把0/1编码(字符串格式)转换成字符串."""res = []v = self._rootfor c in codes:if c == '0':v = v.leftelif c == '1':v = v.rightif v.left is None and v.right is None:res.append(v.char)v = self._rootreturn ''.join(res)

完整代码

Remark

为了更好的理解贪心算法, 我们考虑两个问题:

1. 给定一个问题$P$和求解$P$的贪心算法$A$. $A$是否返回$P$的最优解？

基本的思路是采用反证法. 假设$A$得到的解不是最优解, 那么存在$k>0$, 算法$A$在第$k$步决策时没有采用局部最优策略, 按照这个思路如果得出矛盾, 那么最有性得证. 具体的例子可以参考教材算法导论(Introduction to Algorithms)¹（23章-最小生成树, 16章-贪心算法).

2. 贪心算法适用于哪些优化问题?(返回最优解)

独立集

设$S$是一个有限集, $\mathcal{I}\in 2^S$. $(S,\mathcal{I})$称为一个独立集系统当它满足两个条件: i. 非空性: $?\in \mathcal{I}$; ii. 继承性: 如果$I\in \mathcal{I}$, $J?I$, 那么$J\in \mathcal{I}$. 我们把$I\in \mathcal{I}$称为独立集(Independent Set).

独立集上的优化问题

给定权重函数$w:S\to \mathbb{R}$, 我们的目标是找到$I\in \mathcal{I}$使得$I$的总权重$w(I)={\sum }_{x\in I}w(x)$最大.

贪心算法

从$M=?$开始, 每次从$S$中弹出权重最大的元素$e$, 如果 M ∪ { e } ∈ I M\cup \{e\} \in\mathcal{I} M∪{ e}∈I, 则把$e$添加到$M$中, 否则丢弃$e$(直到$S$为空).

结论

考虑独立集上的优化问题. 贪心算法求得最优解当且仅当独立集系统是 拟阵(Matroid)², $(S,\mathcal{I})$满足条件: 如果$I,J\in \mathcal{I},|J|<|I|$, 那么存在$x\in J\backslash I$使得 I ∪ { x } ∈ I I\cup\{x\} \in \mathcal{I} I∪{ x}∈I.

参考文献