贪心算法

活动选择问题

设n个活动组成的集合 S={a1,a2,…,an},每个活动 ai 需要使用某资源,且该资源只能独占,每个活动 ai 有开始时间 si 和结束时间 fi
如果[si,fi)和[sj,fj)互不重叠,称活动ai,aj是兼容的
问题就是找出最大兼容子集.

最优子结构

定义如下集合:

  • Sij = { ak in S : fi <= k < fs <= sj }

即Sij是S的一个子集,其中每一个活动ak都在ai后开始,在aj前结束
我们加入虚拟活动a0与an+1,且f0 = 0, sn+1 = MAX_VALUE,于是S = S<0,n+1>( 0 <= i, j <= n+1 ),假设活动结束时间按单调递增排序,即:f0 <= f1 <= f2 <= … <= fn <= fn+1,当 i >= j 时, Sij = NULL .

假设Sij的最优解Aij包含活动ak,则Sik的解Aik和Skj的解Akj也必定时最优的,且 Aij = Aik + Akj + 1(由 Aij = Aij U ak U Akj 得到)
整个问题的一个最优解就是 A<0,n+1>

递归解

设 c[i,j] 为 Sij 中最大兼容子集中的活动数

  1. 当Sij = NULL时,有c[i,j]=0
  2. 当Sij非空时,如果ak在Sij的最大兼容子集中被使用,则有递归式:c[i,j] = c[i,k] + c[k,j] + 1 ( i+1 <= k <= j-1 )
             / 0 ;      Sij = NULL
    c[i,j] = | 
             \ MAX( c[i,k] + c[k,j] + 1; i < k < j, ak in Sij ) ; Sij != NULL

将动态规划转化为贪心算法

对任意非空子问题Sij,设am是Sij中具有最早结束时间的活动.
fm = min{ fk : ak in Sij }
那么:

  • 活动am在Sij的某个最大兼容活动子集中被使用

设Sij最大兼容子集的第一个活动的结束时间是fi+1,又fm <= fi+1
所以,am与Ai+1j兼容
am在Sij某个Aij中使用

  • 子问题Sim为空,所以选择am将使子问题Smj为唯一可能非空子问题

递归贪心算法

    RecursiveActiveSelector( s, f, i, n )
    /*
    s为ai的开始时间数组
    f为ai的结束时间数组
    初始调用 RecursiveActiveSelector( s, f, 1, n )
    活动结束时间按单调递增排序
    */
    m = i + 1 ;

    while m <= n and s[m] < f[i]
        m++ ;

    if m <= n
        print a[m] ;
        RecursiveActiveSelector( s, f, m, n ) ;
    else
        return ;

迭代贪心算法

    GreedyActiveSelector( s, f )
        for i = 1 ; i <= n ;
            for m = i + 1 to n
                if f[i] <= s[m]
                    print a[m] ;
                    break ;
            i = m ;

贪心算法的设计步骤

  1. 先做出选择,在解决剩下的子问题
  2. 证明元问题总有一个最优解是做贪心选择得到的,从而说明贪心选择的安全
  3. 说明在做出贪心选择后,剩余的子问题具有这样一个性质:如果将子问题的最优解和我们所作的贪心选择联合起来,可以得出原问题的一个最优解

赫夫曼编码

假设有一个包含100,000个字符的数据文件要压缩,仅有6种不同字符出现,且出现频率如下:

  a b c d e f
频率(千字) 45 13 12 16 9 5
固定长代码字 000 001 010 011 100 101
变长代码字 0 101 100 111 1101 1100
                100                       100                           
           1 /       \ 0              0/        \1                     
           86         14             a:45       55                        
        0/    \1    0/                      0/      \1                     
        58    28    14                     25        30                 
      0/ \1  0/ \1 0/ \1                 0/   \1  0/    \1                  
      a   b  c  d  e  f                 c:12 b:13 14   d:16                
                                                0/  \1
                                               f:5  e:9

          定长编码树                  变长编码数(前缀编码)
                                  没有一个编码是其他编码的前缀
  • 易知使用前缀编码一个文件所需的位数是
  • B(T) = SUM( f(c) * dt(c); c in C )

C是字母表,c为单个字母, f(c)是c出现的频率, dt(c)为c在书中的深度,也就是c的编码长度

构造赫夫曼编码

    Huffman( C )    //C:字母表
        n = |C| ;   //字母表中字母的数量
        Q = C ;     //Q是以f(c)为关键字的最小优先级队列

        for i = 1 to n-1        //因为集合C有n个元素(叶节点)
            z = NewTreeNode ;   //所以有n-1个内节点(满二叉树的性质)
            left[z] = ExtractMIN( Q ) ;
            right[z] = ExtractMIN( Q ) ;
            f(z) = f(left[z]) + f(right[z]) ;
            InsertQueue( Q, z ) ;

        return ExtractMIN( Q ) ;

    // T(n) = O( nlgn ) 

赫夫曼贪心算法的正确性

设C为一字母表,其中每个字符c in C具有频率f(c),设x和y为C中频率最低的两个字符

  1. 则存在C的一种最优前缀编码,其中x和y的编码长度相同,但最后一位不同.
  2. 并设 C1 = ( C - {x,y} ) U {z}, 其中f(z) = f(x) + f(y). 设T1表示字母表C1上最优前缀编码的任意一个树,那么,将T1中的叶子节点z替换成具有孩子x和y的内部节点所得到的树T,则为字母表C上的一个最优前缀编码树.