动态规划

算法设计步骤

  1. 描述最优解的结构
  2. 递归定义最优解的值
  3. 按自底向上的方式计算最优解的值
  4. 计算出的结果构造一个最优解

装配线调度

通过工厂最快路线的结构

一个问题(通过装配站S<i,j>的最快路线)的最优解包含子问题(通过S<1,j-1>或者S<2,j-1>的最快路线)的一个最优解.—-最优子结构

一个递归解

令fi[j]表示一个底盘从起点到装配站S<i,j>的最快可能时间,设出厂的最快时间为f,则:
f
= min( f1[n]+x1, f2[n]+x2 ); xi为从S<i,n>离开装配线的时间
又易知 f1[1] = a<1,1> + e1, f2[1] = a<2,1> + e2; ei为进入S<i,1>的时间

计算fi[j]

             /  e1 + a<1,1>   ; j = 1
    f1[j] = |
             \  min( f1[j-1] + a<1,j>, f2[j-1] + t<2,j-1> + a<1,j>) ; j > 1
             #t<i,j>为装配线互换的调度时间

             /  e2 + a<2,1>   ; j = 1
    f2[j] = |
             \  min( f2[j-1] + a<2,j>, f1[j-1] + t<1,j-1> + a<2,j>) ; j > 1
             #t<i,j>为装配线互换的调度时间   

跟踪最优解的构造过程
定义Li[j]为通过装配站S<i,j>时,第j-1个装配站所选的装配线(1或2)

计算最快时间

    FastWay( a, t, e, x, n )
    /*
    a为a<i,j>,每个装配站装配用的时间; t为t<i,j>,装配站之间调度用的时间;
    e为ei,进入每条装配线第一个装配站所用的时间; x为xi,从最后一个装配站离开的时间
    n是装配站的数量
    */
        f1[1] = e1 + a<1,1> ;
        f2[1] = e2 + a<1,2> ;

        for j = 2 to n
            if f1[j-1] <= f2[j-1] + t<2,j-1>
                f1[j] = f1[j] + a<1,j> ;
                L1[j] = 1 ;
            else
                f1[j] = f2[j-1] + t<2,j-1> + a<1,j> ;   
                L1[j] = 2 ;                             

            if f2[j-1] <= f1[j-1] + t<1,j-1>            //每进入一个新的站点
                f2[j] = f2[j] + a<2,j> ;                //我们都不知道是f1[j-1]快,还是f2[j-1]快,所以f1[j-1]和f2[j-1]都要保存
                L2[j] = 2 ;
            else
                f2[j] = f1[j-1] + t<1,j-1> + a<2,j> ;   
                L2[j] = 1 ;

        if f1[n] + x1 <= f2[n] + x2
            f* = f1[n] + x1 ;
            L* = 1 ;
        else
            f* = f2[n] + x2 ;
            L* = 2 ;

构造通过工厂的最快路线

    PrintStation( L, L*, n )
        i = L* ;
        print line "i" station "n" ;

        for j = n down to 2
            i = Li[j] ;
            print line "i" station "j-1" ;

矩阵乘法

给定一个要相乘的矩阵构成的序列( A1, A2, …, An),要计算乘积A1A2…*An

  • 矩阵乘法满足结合律,即:((A1 * A2) * A3) = (A1 * (A2 * A3))
    //两个矩阵相乘
    MatrixMultiply( A, B )  //A,B分别是矩阵
        if col[A] != row[B] //A[i][j],B[j][k]
            return ERROR ;  //如果A的列数不等于B的行数,则不满足矩阵相乘的定义

        for i = 1 to row[A]
            for k = 1 to col[B]
                C[i][k] = 0 ;
                for j = 1 to row[B]
                    C[i][k] = A[i][k] * B[k][j] //标量乘法

        return C
    /*
    如果A是一个 p*q 矩阵, B是一个 q*r 的矩阵, 则C是 p*r 矩阵.
    而标量乘法的计算次数为 p*q*r
    */

设有三个矩阵( A1, A2, A3 ). A1:10x100; A2:100x5; A3:5x50
如果按 ((A1 * A2) * A3) 的顺序计算:
( A1 * A2 : 10 * 100 * 5 = ) 5000 + (* A3 : 10 * 5 * 50 = ) 2500 = 7500
如果按 (A1 * (A2 * A3)) 的顺序计算:
( A2 * A3 : 100 * 5 * 50 = ) 25000 + ( *A1 : 10 * 100 * 50 = )50000 = 75000

  • 所以妥善安排矩阵相乘的顺序,可以有效降低运行时间

矩阵链乘法:
给定n个矩阵构成一个链( A1, A2,…,Ai),其中 i = 1, 2,…,n. 切矩阵Ai的维数是 Pi-1 * Pi , 对乘积 A1 * A2 * … * An 以一种最小化标量乘法次数的方法进行家括号.

最优加全括号的结构

假设 Ai * Ai+1 * … * Aj 的一个最优加全部括号把乘积在 Ak 和 Ak+1 之间分开,则对 Ai * Ai+1 * … * Aj 最优加全部括号的”前缀” Ai,Ai+1,…,Ak 和”后缀” Ak+1,Ak+2…Aj 也是最优加全部括号

递归解

设m[i,j]为计算矩阵 Ai…Aj 所需标量乘法运算次数的最小值.对于整个问题,计算A1…An的最小代价就是m[1,n],下面来递归定义m[i,j]
如果 i=j, 矩阵链只包含一个矩阵 Ai, 故无需做标量乘法 ===> m[i,i] = 0
假设最优加权括号将乘积 Ai,Ai+1,…,Aj从Ak和Ak+1之间分开( i <= k < j ),又Ai是Pi-1 * Pi 的矩阵,所以

             / 0 ; i=j
    m[i,j] = |
             \ min( m[i,k] + m[k+1,j] + Pi-1 * Pk * Pj ) ; i<j

计算最优代价

可使用动态规划的标志:

  1. 有最优子结构
  2. 子问题重叠
  • 定义s[i,j]为记录 Ai,Ai+1,…,Aj 最优加全括号的k值
    MatrixChainOrder( P )   //P记录A1,A2,...,An的维数,p[0][n]
        for i = 1 to n
            m[i,i] = 0 ;

        for l = 2 to n      //矩阵子链的长度
            for i = 1 to n-l+1 //矩阵子链的起始位置
                j = i + l - 1 ;//矩阵子链的结束位置
                m[i,j] = MAX_VALUE ;
                for k = i to j-1
                    t = m[i,k] + m[k+1,j] + Pi-1*Pk*pj
                        if m[i,j] > t
                            m[i,j] = t ;
                            s[i,j] = k ;
        return m,s ;

构造最优解

    PrintOptimalPairs( s, i, j )        //s记录k值
        if( i == j )
            print "A"i ;
        else
            print "(" ;
            PrintOptimalPairs( s, i, s[i,j] ) ;
            PrintOptimalPairs( s, s[i,j]+1, j ) ;
            print ")" ;

动态规划基础

最优子结构
如果一个问题的最优解中包含了子问题的最优解,则该问题具有最优子结构
重叠自问题
每个子问题只解一次,把解保存在一个需要时就可以查看的表中,而每次查看的时间为常数

    //基于递归算法的矩阵链相乘(可以看出子问题被重复计算多次)
    RecursiveMatrixChain( P, i, j )
        if i == j
            return 0 ;
        M[i,j] = MAX_VALUE ;
        for k = i to j-1
            t = RecursiveMatrixChain( P, i, k ) + RecursiveMatrixChain( P, k+1, j ) + Pi-1*Pk*Pj ;
            if m[i,j] > t
                m[i,j] = t ;
        return m[i,j] ;
  • 要妥善选择要被记录下来的信息,从而保障构造最优解的效率.(如:矩阵链中的s[i,j]表)
    //做备忘录(优化递归算法的性能)
    MemoiredMatrixChain( P )
        for i = 1 to n
            for j = i to n 
                m[i,j] = MAX_VALUE ;

        return LookupChain( P, i, j ) ;

    //==============
    LookupChain( P, i, j )
        if m[i,j] < MAX_VALUE  //这一步就是在查备忘录
            return m[i,j] ;

        if i == j
            m[i,j] = 0 ;
        else
            for k = i to j-1 
                t = LookupChain( P, i, k ) + LookupChain( P, k+1, j ) + Pi-1*Pk*Pj ;
                if m[i,j] > t
                    m[i,j] = t ;

        return m[i,j] ;

最长公共子序列

Z=(B,C,D,B) 是 X=(A,B,C,B,D,A,B) 的一个子序列,相应x的下标序列为(2,3,5,7)
定义:给定一个 X=(x1,x2,…,xm),另一个序列 Z=(z1,z2,…,zk),如果x的一个严格递增下标序列(i1,i2,…,ik),使得对所有的 j=1,2,…,k, 有 x<ij> = zj,则z是x的子序列

描述一个最长公共子序列(LCS)

最优子结构:
设 X=(x1,x2,…,xm) 和 Y=(y1,y2,…yn)为两个序列,并设 Z=(z1,z2,…,zk) 为 X 和 Y 的任意LCS

  1. 如果 xm = yn, 且 zk = xm = yn, 则 Zk-1 是 Xm-1 和 Yn-1的一个LCS
  2. 如果 xm != yn, 且 zk != xm, 则 Z 是 Xm-1 和 Yn 的一个LCS
  3. 如果 xm = yn, 且 zk != yn, 则 Z 是 Xm 和 Yn-1 的一个LCS

递归解:

    #定义c[i,j]为序列 Xi 和 Yj 的一个LCS的长度
             / 0 ;  i = 0 or j = 0 即 Xi 或 Yj 中有一个长度为0 
    c[i.j] = | c[i-1,j-1] + 1 ; i,j > 0 and xi == yi
             \ max( c[i,j-1], c[i-1,j]) ;   i,j > 0 and xi != yj

计算LCS的长度:

    //c[0..m,0..m]记录LCS长度,b[1..m,1..n]辅助最优解的构造
    //注意:LCS的解不是唯一的
    LCSlength( X, Y )
        m = length[X] ;
        n = length[Y] ;
        c[0][0..n] = 0 ;
        c[0..m][0] = 0 ;

        for i = 1 to m
            for j = 1 to n
                if x[i] == y[j]
                    c[i][j] = c[i-1][j-1] + 1 ;
                    b[i][j] = 1 ;
                else if c[i-1][j] >= c[i][j-1]
                    c[i][j] = c[i-1][j] ;
                    b[i][j] = 0 ;
                else
                    c[i][j] = c[i][j-1] ;
                    b[i][j] = -1 ;
        return b, c ;

构造LCS:

    //使用表b构造LCS
    PrintLCS( b, X, m, n )
        if m == 0 or n == 0
            return ;
        if b[m][n] == 1 
            PrintLCS( b, X, m-1, n-1 ) ;
            print "x[m]" ;
        else if b[m][n] == 0
            PrintLCS( b, X, m-1, n ) ;
        else 
            PrintLCS( b, X, m, n-1 ) ;

    //=============
    //使用表c构造LCS
    PrintLCS( c, X, m, n )
        if m == 0 or n == 0
            return ;
        if c[m][n] == c[m-1][n-1] + 1
            PrintLCS( c, X, m-1, n-1 ) ;
            print "X[m]" ;
        else if c[m][n] = c[m-1][n]
            PrintLCS( c, X, m-1, n-1 ) ;
        else
            PrintLCS( c, X, m, n-1 ) ;

LCSlength( X, Y )备忘录版:

    LCSlength( X, Y )
        m = length[X] ;
        n = length[Y] ;
        c[1..m][1..n] = MIN_VALUE ;
        return Lookup( c, m, n ) ;

    //=========
    LookupLCS( c, m, n )
        if m == 0 or n == 0 
            return 0 ;
        else if c[m][n] > MIN_VALUE //这一步就是在才备忘录
            return c[m][n] ;
        else if xm == yn 
            c[m][n] = LookupLCS( c, m-1, n-1 ) + 1 ;
        else
            c[m][n] = max( LookupLCS(c, m-1, n), LookupLCS(c, m, n-1) ) ;

        return c[m][n] ;

最优二叉查找树

给定一个有n个互异的关键字组成的序列 K=(k1,k2,…,kn),且关键字有序(即:k1 < k2 < … < kn).对每个关键字ki,一次搜索为ki的概率是pi.但某些搜索的值可能不在 K 内,因此还有 n+1 个虚拟键”d0,d1,…,dn”代表不在 K 内的值.具体的,d0代表所有小于k1的值,dn代表所有大于kn的值,其他di位于ki和ki+1之间.一次搜索对于di的概率是qi.且每次搜索要么成功(找到ki),要么失败(找到di)

  • SUM(pi, i=1 to n) + SUM(qi, i=0 to n) = 1
    #搜索代价
    E[T] = SUM( (h(ki) + 1)*pi, i=1 to n ) + SUM( (h(di) + 1)*qi, i=0 to n )
         = 1 + SUM( h(ki)*pi,i=1 to n ) + SUM( h(di)*qi, i=0 to n )
    #h(ki) 和 h(di)为ki和di在树中的深度

分析

对于一棵二叉查找树的任意一棵子树必定包含在连续范围内的关键字 ki,…,kj(1 <= i <= j <= n)且必定包含虚拟关键字 di-1,…,dj 作为叶子
如果一棵最优二叉查找树T有一棵包含关键字 ki,…,kj 和虚拟键 di-1,…,dj 的子树Ti,那么Ti也是最优的.

    给定关键字ki,...,kj;设kr(i <= r <= j)为这棵子树根<br>
    
    ki,...,kr-1 + di-1,...,dr-1 和 kr+1,...,kj + dr,...,dj 
             子树最优                       子树最优

    则: 以kr为根的子树最优.
    检查每一个r(i <= r <= j)以确定ki,...,kj的最优二叉查找树

递归解

定义e[i,j]为搜索一棵包含关键字 ki,…,kj 的最优二叉查找树的期望代价,最终我们要计算e[1,n]
当 j = i-1 时,出现简单情况.此时只有虚拟键 di-1, 期望搜索代价是 e[i,i-1] = qi-1
当 j >= i 时,需要从 ki,…,kj 中选择一个子树根r,然后用 ki,…,kr-1 + di-1,…,dr-1 和 kr+1,…,kj + dr,…,dj 分别构建左右子树,使其最优.
定义概率总和为:

  • w[i,j] = SUM( pl, l = i to j ) + SUM( ql, l = i-1 to j )
    如果kr是一棵包含关键字 ki,...,kj 的最优子树的根
    ===> e[i,j] = pr + ( e[i,r-1] + w[i,r-1] ) + ( e[r+1,j] + w[r+1,j] )
    注意: w[i,j] = pr + w[i,r-1] + w[r+1,j]
    ===> e[i,j] = w[i,j] + e[i,r-1] + e[r+1,j]

    所以:
             / qi-1 ;   j=i-1
    e[i,j] = |
             \ MIN( e[i,r-1]+e[r+1,j]+w[i,j], i <= r <= j ) ; i <= j
  • 定义root[i,j]为kr的下标r,kr是包含关键字ki,…,kj的一棵最优二叉查找树的树根

计算最优二叉查找树的期望代价

    /*
    把 e[i,j] 保存在表 e[1..n+1,0..n] 中,
    第一维的下标需要达到 n+1,原因是为了有一个只包含虚拟键dn
    的子树;
    第二维的下标从0开始,是为了保存e[1,0],即只有d0的子树

    令w[1..n+1,0..n]保存w[i,j]值
    w[i,i-1] = qi-1 ;
    w[i,j] = w[i,j-1] + pj + qj ; 1 <= i <= n+1 且 j >= i
    */

    OptimalBST( p, q, n )
    //p为ki的概率
    //q为di的概率
    //n为ki的数量
    for i = 1 to n+1
        e[i,i-1] = qi-1 ;
        w[i,i-1] = qi-1 ;

    for l = 1 to n      //关键字链的长度
        for i = 1 to n-l+1
            j = l+i-1 ;
            e[i,j] = MAX_VALUE ;
            w[i,j] = w[i,j-1] + pj + qj ;

            for r = i to j
                t = w[i,j] + e[i,r-1] + e[r+1,j] ;
                if e[i,j] > t 
                    e[i,j] = t ;
                    root[i,j] = r ;
    return root, e ;

    /*
    由于对所有 1 <= i < j <= n,总存在root[i,j-1] <= root[i,j] <= root[i+1,j]
    所以可以将 for r = i to j 这段改为:
    */
    if i == j 
        root[i,j] = i ;
        e[i,j] = w[i][j] + e[i][j-1] + e[i+1][j] ;
    else
        for r = root[i,j-1] to root[i+1,j]
            t = e[i,r-1] + e[r+1][j] + w[i,j] ;
            if e[i,j] > t
                e[i,j] = t ;
                root[i,j] = r ;