[关闭]
@zqbinggong 2018-03-18T13:49:12.000000Z 字数 2015 阅读 451

chap16 贪心算法

贪心算法 算法导论

内容


贪心算法的原理

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

活动选择问题

  1. 最优子结构:
  2. 贪心选择,最大兼容活动集必然包含中最早结束的活动,反证法可以证明
  3. 假设输入活动已经按照结束时间单调递增顺序排好序

递归贪心算法
k表示要解决的子问题,n是问题规模,其中表示原问题(加上一个起始时间都是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

赫夫曼编码

基本概念:

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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注