【算法分析与设计】动态规划（下）（一）

一、最长公共子序列

  若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的 子序列 是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。

  给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。

  给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的 最长公共子序列。

1.1 最长公共子序列的结构

  设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ，则

  (1)若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。

  (2)若xm≠yn且zk≠xm，则 Z是xm-1和Y的最长公共子序列。

  (3)若xm≠yn且zk≠yn，则 Z是X和yn-1的最长公共子序列。

  由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。

1.2 子问题的递归结构

  由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列和的最长公共子序列的长度。其中， Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。其它情况下，由最优子结构性质可建立递归关系如下：

1.3 计算最优值

  由于在所考虑的子问题空间中，总共有θ(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。

void LCSLength(int m，int n，char *x，char *y，int **c，int **b)
{  
       int i，j;
       for (i = 1; i <= m; i++) c[i][0] = 0;
       for (i = 1; i <= n; i++) c[0][i] = 0;
       for (i = 1; i <= m; i++)
          for (j = 1; j <= n; j++) {
             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]=2;}
             else { c[i][j]=c[i][j-1]; b[i][j]=3; }
             }
}

//构造最长公共子序列
void LCS(int i，int j，char *x，int **b)
{
      if (i ==0 || j==0) return;
      if (b[i][j]== 1){ LCS(i-1，j-1，x，b); cout<<x[i]; }
      else if (b[i][j]== 2) LCS(i-1，j，x，b);
      else LCS(i，j-1，x，b);
}

1.4 举例说明

1.5 算法的改进

  在算法lcsLength和lcs中，可进一步将数组b省去。事实上，数组元素c[i][j]的值仅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]这3个数组元素的值所确定。对于给定的数组元素c[i][j]，可以不借助于数组b而仅借助于c本身在时间内确定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一个值所确定的。

   如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。

  事实上，在计算c[i][j]时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n))。

二、最大子段和

  子段：数列中的连续若干子数列的集合

  问题：给定由n个整数（可能为负整数）组成的序列a1,a2,…an，求该序列的子段和的最大值

  当所有整数均为负整数时，定义其最大子段和为零

  例如，当（a1,a2,a3,a4,a5,a6）=（-2,11,-4,13,-5,-2）时，最大子段和为20。

2.1 代码

int MaxSum(int n,int *a){
  int besti,bestj;
  int i,j,k,thissum;
  int sum=0;
  for(i=1;i<=n;i++){
    for(j=i;j<=n;j++){
      thissum=0;
      for(k=i;k<=j;k++)
        thissum+=a[k];
      if (thissum>sum){
        sum=thissum;
        besti=i;
        bestj=j;
      }
    }
  }
return sum;
} 

2.2 最大子段和问题的分治算法

  将所给的序列a[1:n]，分成长度相等的两端a[1:n/2]和 a[n/2+1:n]，分别求出这两端的最大子段和，则 a[1:n]的最大子段和有三种情况：

  a[1:n]的最大子段和与a[1:n/2]的最大子段和相同；

  a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同；

  a[1:n]的最大子段和跨越a[1:n/2]和a[n/2+1:n]两个区域。

  对于3，容易看出，a[n/2]与a[n/2+1]必在最优子序列中！

  在a[1:n/2]中计算出s1为含有a[n/2]的最大子段和。

  在a[n/2+1:n]中计算出s2为含有a[n/2+1]的最大子段和。

  则s1+s2即为出现情形3时的最优值。

int MaxSubSum(int *a,int left,int right){
  int sum=0;
  int center;
  int leftsum,rightsum;
  int i,s1,s2,lefts,rights;
  if(left==right)
    sum=a[left]>0?a[left]:0;
  else{
    center=(left+right)/2;
    leftsum=MaxSubSum(a,left,center);
  rightsum=MaxSubSum(a,center+1,right);
                        s1=0;
    lefts=0;
    for(i=center;i>=left;i--){
      lefts+=a[i];
      if(lefts>s1)
        s1=lefts;
    }
    s2=0;
    rights=0;
    for(i=center+1;i<=right;i++){
      rights+=a[i];
      if(rights>s2)
        s2=rights;
    }

2.3 代码

sum=s1+s2;
    if(sum<leftsum)
      sum=leftsum;
    if(sum<rightsum)
      sum=rightsum;
  }
  return sum;
}

2.4 分治算法的时间复杂度

  该算法所需的计算时间T(n)满足典型的分治算法递归式。

  解此递归方程可知，T(n)= O(nlogn)。

2.5 最大子段和问题的动态规划算法

  若记b[j]为必须包含a[j]的左侧连续数据的最大子段和，则所求的最大子段和为max(1到n) b[j]，再用变量sum存储当前b[j]的最大值即可。

  由于程序只用了一个for循环，所以此算法的时间复杂度为O(n)。

  由b[j]的定义易知：

  当b[j-1]>0 时，b[j]= b[j-1]+a[j]，否则b[j]= a[j]。由此可得b[j]的动态规划递归式b[j]= max{b[j-1]+a[j],a[j]}，1<=j<=n。

  据此，可以设计出求最大字段和的动态规划算法。

  代码如下：

int MaxSum(int n,int *a){
    int i,sum=0,b=0;
    for(i=1;i<=n;i++){
        if(b>0)
      b+=a[i];
        else
      b=a[i];
        if(b>sum)
      sum=b;
    }
    return sum;
}

三、凸多边形最优三角剖分

  用多边形顶点的逆时针序列表示凸多边形，即P={v0,v1,…,vn-1}表示具有n条边的凸多边形。

  若vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成2个多边形{vi,vi+1,…,vj}和{vj,vj+1,…vi}。

  多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。

  给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。

3.1 三角剖分的结构及其相关问题

  一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积((A1(A2A3))(A4(A5A6)))所相应的语法树如图 (a)所示。

  凸多边形{v0,v1,…vn-1}的三角剖分也可以用语法树表示。例如，图 (b)中凸多边形的三角剖分可用图 (a)所示的语法树表示。

  矩阵连乘积中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vi。三角剖分中的一条弦vivj，i<j，对应于矩阵连乘积A[i+1:j]。

3.2 最优子结构性质

  凸多边形的最优三角剖分问题有最优子结构性质。

  事实上，若凸(n+1)边形P={v0,v1,…,vn-1}的最优三角剖分T包含三角形v0vkvn，1≤k≤n-1，则T的权为3个部分权的和：三角形v0vkvn的权，子多边形{v0,v1,…,vk}和{vk,vk+1,…,vn}的权之和。

  可以断言，由T所确定的这2个子多边形的三角剖分也是最优的。因为若有{v0,v1,…,vk}或{vk,vk+1,…,vn}的更小权的三角剖分将导致T不是最优三角剖分的矛盾。

3.3 最优三角剖分的递归结构

  定义t[i][j]，1≤i<j≤n为凸子多边形{vi-1,vi,…,vj}的最优三角剖分所对应的权函数值，即其最优值。为方便起见，设退化的多边形{vi-1,vi}具有权值0。据此定义，要计算的凸(n+1)边形P的最优权值为t[1][n]。

  t[i][j]的值可以利用最优子结构性质递归地计算。当j-i≥1时，凸子多边形至少有3个顶点。由最优子结构性质，t[i][j]的值应为t[i][k]的值加上t[k+1][j]的值，再加上三角形vi-1vkvj的权值，其中i≤k≤j-1。由于在计算时还不知道k的确切位置，而k的所有可能位置只有j-i个，因此可以在这j-i个位置中选出使t[i][j]值达到最小的位置。由此，t[i][j]可递归地定义为：

四、图像压缩

  图象的变位压缩存储格式将所给的象素点序列{p1,p2,…,pn},0≤pi≤255分割成m个连续段S1,S2,…,Sm。第i个象素段Si中(1≤i≤m)，有l[i]个象素,且该段中每个象素都只用b[i]位表示。

  设

  则第i个象素段Si为

  设 ，则hib[i]8。因此需要用3位表示b[i],如果限制1l[i]255，则需要用8位表示l[i]。因此，第i个象素段所需的存储空间为l[i]*b[i]+11位。按此格式存储象素序列{p1,p2,…,pn}，需要 位的存储空间。

  图象压缩问题要求确定象素序列{p1,p2,…,pn}的最优分段，使得依此分段所需的存储空间最少。每个分段的长度不超过256位。

  设l[i]，b[i]，是{p1,p2,…,pn}的最优分段。显而易见，l[1]，b[1]是{p1,…,pl[1]}的最优分段，且l[i]，b[i]，是{pl[1]+1,…,pn}的最优分段。即图象压缩问题满足最优子结构性质。

设s[i]，1≤i≤n，是象素序列{p1,…,pn}的最优分段所需的存储位数。由最优子结构性质易知：

  其中，

  算法复杂度分析：

  由于算法compress中对k的循环次数不超这256，故对每一个确定的i，可在时间O(1)内完成的计算。因此 整个算法所需的计算时间为O(n)。