chap16 贪心算法

贪心算法 算法导论

内容

贪心算法的原理

1. 注意，动态规划在划分子问题时的依据是由最优子结构得到的一个特定关系，这个特定关系给出了不同规模子问题之间的依赖关系。在这里，我们可以给这个关系加上限制条件，从而得到了贪心算法。具体地说，动归中，大规模的问题依赖较小规模问题集中某个问题的解，但我们无法提前确定这个被依赖的小问题，只能通过一个循环来确定（寻找max或者min）；在贪心算法中，通过额外的限制信息，我们知道大问题依赖的小问题是哪一个，从而不需要循环过程去寻找。并且划分后，只剩下一个子问题，而不是两个或更多
2. 简单来说，贪心是动归的特例，是当问题满足更多的特性时使用的做法。因而能用贪心解，就能用动归，反之不成立，因而后者对问题的限制更多
3. 这个附加的限制因素就是贪心选择性质。通俗地说，我们贪心做出的划分点和动归通过循环得到的划分点是一致的，即问题有可以知道选择划分点的信息。
4. 必要因素： 最优子结构和贪心选择性质。后者表示能够通过做出局部最优选择来构造全局最优解，即直接在当前问题中做出看来最优的选择，而不需考虑子问题的解
5. 这句话也很明显，无论分治还是动归，都是将问题变成小问题集，解决小问题集中的问题，通过依赖关系得到大问题的解。因而实际要求解的就是这些小问题，因而他们的规模越小越好。
6. 详细可参考chap15 动态规划
7. 0-1背包问题和分数背包问题，后者可以贪心求解。本质上来看，前者不具备3中所说的可以确定划分点的额外信息。

活动选择问题

1. 最优子结构： $c[i,j] = \begin{cases} & 0 \text{ if } S_{ij} = \varnothing \\ & max_{ a_{k}\in S_{ij}} (c[i,k]+c[k+1,j]+1) \text{ if } i < j \end{cases}$
2. 贪心选择，最大兼容活动集必然包含$S_{ij}$中最早结束的活动，反证法可以证明
3. 假设输入活动已经按照结束时间单调递增顺序排好序
4. $\Theta(n)$

递归贪心算法
k表示要解决的子问题$S_{k}$,n是问题规模，其中$S_{0}$表示原问题（加上一个起始时间都是0的虚拟问题）
recursive-activity-selector(s,f,k,n)

m = k + 1
while m <= n and s[m] < f[k]        #寻找k之后与k都兼容的活动，而k之
                    前的活动的时间区间都包含于k的活动时间区间
    m = m + 1
if m <= n
    return {a_m} U recursive-activity-selector(s,f,m,n)
else 
    return 空集

迭代贪心算法
greedy-activity-selector(s,f)

n = s.length
A = {a1}            #a1是最早结束的
k = 1
for m = 2 to n
    if s[m] >= f[k]
        A = A U {am}
        k = m
return A

赫夫曼编码

基本概念：

• 变长编码（variable-length code）,赋予高频字符短编码，低频字符长编码
• 前缀码（prefix code）,即没有任何码字是其他码字的前缀。与其他任何码字相比，前缀码可以保证达到最优数据压缩。另外，前缀码的作用是简化解码过程，由于没有码字其他码字的前缀，编码文件的开始码字是无歧义的
• 解码过程需要前缀码的一种方便的表示形式以便我们可以容易地截取开始码字，一种二叉树可以满足这种要求——叶结点为给定的字符，该字符的二进制码字用从根结点到该叶结点的简单路径表示
• 最优编码方案总对应一棵满二叉树，即每个非叶结点都有两个孩子（反证法）。因为接下来我们只关注于满二叉树
• 对于字符集C，那么对应的满二叉树有|C|个叶结点，|C|-1 个内部结点
• 伪代码，从|C|个叶结点开始，执行|C|-1 个“合并”操作创建出最终的二叉树。其中使用了以结点属性freq为关键字的最小优先队列，以识别两个频率最低的对象将其合并

huffman(C)

n = |C|
Q = C
for i = 1 to n-1
    allocate a new nde z
    z.left = x = extract-min(Q)
    z.right = y = extract-min(Q)
    z.freq = x.freq + y.freq
    insert(Q,z)
return extract-min(Q)           #return the root of the tree

习题

16.1-4 区间图着色问题

1. 问题描述，将一组活动安排在不同的教室里进行，任意活动都可以在任意教室里进行，目标是寻找所需的最少的教室数量
2. 区间着色问题，使用最少的颜色对顶点进行着色，要求相邻的顶点颜色各不相同。这里将顶点看成活动，边链接不兼容的活动
3. 贪心算法，将s和f合并成t，再对t进行排序，将教室分成两类，一种是busy，一一种是free，对t进行遍历，若遇到的元素是s的元素，就将free的队头教室取出用来进行该元素对应的活动，并将该教室放进busy中；若遇到的是f中的元素，将它所占用的教室从busy中取出并放在free的队头（或者用栈，后进先出）

to be continued

代码实现

java