南京邮电大学算法设计实验报告——动态规划法

1、实 验 报 告（2009/2010学年 第一学期）课程名称算法分析与设计A实验名称动 态 规 划 法实验时间2009年11月20日指导单位计算机学院软件工程系指导教师张怡婷学生姓名丁力琪班级学号B学院(系)计算机学院专 业软件工程实 验 报 告实验名称动 态 规 划 法指导教师张怡婷实验类型验证实验学时22实验时间2009-11-20一、 实验目的和任务目的：加深对动态规划法的算法原理及实现过程的理解，学习用动态规划法解决实际应用中的最长公共子序列问题。 任务：用动态规划法实现求两序列的最长公共子序列，其比较结果可用于基因比较、文章比较等多个领域。要求：掌握动态规划法的思想，及动态规划法在实际

2、中的应用；分析最长公共子序列的问题特征，选择算法策略并设计具体算法，编程实现两输入序列的比较，并输出它们的最长公共子序列。 二、 实验环境(实验设备)硬件：计算机软件：Visual C+3、 实验原理及内容（包括操作过程、结果分析等）1、最长公共子序列（LCS）问题是：给定两个字符序列X=x1,x2,xm和Y=y1,y2,yn，要求找出X和Y的一个最长公共子序列。 例如：X=a,b,c,b,d,a,b,Y=b,d,c,a,b,a。它们的最长公共子序列LSC=b,c,d,a。通过“穷举法”列出所有X的所有子序列，检查其是否为Y的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法，求解时

3、间为指数级别的，因此不可取。2、 分析LCS问题特征可知，如果Z=z1,z2,，zk为它们的最长公共子序列，则它们一定具有以下性质：（1） 若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列；（2） 若xmyn且xmzk，则Z是Xm-1和Y的最长公共子序列；（3） 若xmyn且zkyn，则Z是X和Y的最长公共子序列。 这样就将求X和Y的最长公共子序列问题，分解为求解较小规模的问题： 若xm=ym，则进一步分解为求解两个（前缀）子字符序列Xm-1和Yn-1的最长公共子序列问题； 如果xmyn，则原问题转化为求解两个子问题，即找出Xm-1和Y的最长公共子序列与找出X和

4、Yn-1的最长公共子序列，取两者中较长者作为X和Y的最长公共子序列。 由此可见，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，具有最优子结构性质。3、令cij保存字符序列Xi=x1,x2,xi和Yj=y1,y2,yj的最长公共子序列的长度，由上述分析可得如下递推式： 0 i=0或j=0cij= ci-1j-1+1 i,j0且xi=yj maxcij-1,ci-1j i,j0且xiyj 由此可见，最长公共子序列的求解具有重叠子问题性质，如果采用递归算法实现，会得到一个指数时间算法，因此需要采用动态规划法自底向上求解，并保存子问题的解，这样可以避免重复计算子问题，在多项式时间内完

5、成计算。4、 为了能由最优解值进一步得到最优解（即最长公共子序列），还需要一个二维数组s，数组中的元素sij记录cij的值是由三个子问题ci-1j-1+1,cij-1和ci-1j中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。5、 编程定义LCS类，计算最长公共子序列的长度，并给出最长公共子序列：（注意：C语言中数组下标由0开始，而实际数据在一维数组a、b和二维数组是c、s中存放却是从小标为1处开始。） 类中数据成员主要有二维数组c和s用于动态规划法求解过程中保存子问题的求解结果，一维数组a和b用于存放来两个字符序列，m和n为两

6、个字符序列中实际字符的个数。这些数据成员均应在LCS类的构造函数中进行初始化：#include#includeusing namespace std;#define maxlength 11class LCSpublic:LCS(int nx,int ny,char *x,char *y) /对数据成员m、n、a、b、c、s初始化m=nx;n=ny;a=new charm+2;b=new charn+2;memset(a,0,m+2);memset(b,0,n+2); /将x和y中的字符写入一维数组a和b中for(int i=0;inx+2;i+)ai+1=xi;for(int i=0;iny

7、+2;i+)bi+1=yi;a0=b0=0;c=new intmaxlengthmaxlength;s=new intmaxlengthmaxlength; /对二维数组c和s进行初始化for(int i=0;imaxlength;i+)for(int j=0;jmaxlength;j+)sij=0;cij=0;int LCSLength();void CLCS()CLCS(m,n);private:void CLCS(int i,int j)const;int (*c)maxlength,(*s)maxlength;int m,n;char *a,*b;/6、类中成员函数主要有LCSLeng

8、th()和CLCS()两个公有成员函数，CLCS()通过调用私有递归 /成员函数CLCS(int t,int j)实现。int LCS:LCSLength()for(int i=0;i=m;i+) ci0=0;for(int j=0;j=n;j+) c0j=0;for(int i=1;i=m;i+)for(int j=1;j=cij-1)cij=ci-1j;sij=2;elsecij=cij-1;sij=3;return cmn; /返回最优解值void LCS:CLCS(int i,int j)const if(i=0|j=0|sij=0) return;if(sij=1)CLCS(i-1,

9、j-1); coutai;else if(sij=2) CLCS(i-1,j);else CLCS(i,j-1);/7、主函数中负责输入两个待比较的字符串x和y（长度不超过maxlength-1），求得他们的实际/字符长度nx和ny，并调用LCS类的成员函数LCSLength()和CLCS()求最优解值和最优解：int main()int nx,ny;char *x,*y;x=new charmaxlength;y=new charmaxlength;cout请输入Xendl;gets(x);nx=strlen(x);cout请输入Yendl;gets(y);ny=strlen(y);LCS

10、lcs(nx,ny,x,y);cout X和Y最长公共子序列的长度为：lcs.LCSLength()endl;cout该序列为=LCSLength(i,j-1)cij=LCSLength(i-1,j);sij=2;else cij=LCSLength(i,j-1); sij=3;return cij;2、 若省去原程序中的二维数组s，是否还能求的最长公共子序列问题的最优解？请编写一个类似的CLCS算法实现：不借助二维数组s在O(m+n)的时间内构造最长公共子序列的功能。（提示：此时可在当前cij处比较ai和bj。 如果相等，则调用CLCS(i-1,j-1)，输出ai（或bj）。 如果不相等，则

11、比较ci-1j和cij-1。若ci-1jcij-1,则递归调用CLCS（i-1，j）；否则，递归调用CLCS(i,j-1)。） void LCS:CLCS(int i, int j) constif(i=0|j=0) return;if(ai=bj)CLCS(i-1,fj-1);cout=cij-1) CLCS(i-1,j);else CLCS(i,j-1); 3、 如果只需计算最长公共子序列的长度，而无须构造最优解，则如何改进原有程序可以使得算法的空间需求大大减少？请改写原程序，使算法的空间复杂度减少为O(minm,n)。（提示：计算cij仅用到第i行和第i-1行元素，因此，只需两行元素空间

12、就可以计算最长公共子序列的长度，并且选用序列长度较短的一个作为y序列，可以缩短每行元素的个数，从而进一步减少空间复杂度。）#include#includeusing namespace std;#define maxlength 11class LCSpublic:LCS(int nx,int ny,char *x,char *y)m=nx;n=ny;a=new charm+1;b=new charn+1;memset(a,0,m+2);memset(b,0,n+2);for(int i=0;inx;i+)ai+1=xi;for(int i=0;in)l=m;s=n;elsechar *t;t

13、=x;x=y;y=t;s=m;l=n;c1=new ints+1;c2=new ints+1;for(int i=0;is;i+)c1i=c2i=0;int LCSLength();private:int m,n;int *c1,*c2;int l,s;char *a,*b;int LCS:LCSLength()int *temp;for(int i=0;is;i+) c1i=0;for(int i=1;i=l;i+)for(int j=1;j=c2j-1)c2j=c1j;elsec2j=c2j-1;for(int z=0;zs;z+) c1z=c2z;return c2s;int main()int nx,ny;char *x;char *y;x=new charmaxlength;y=new charmaxlength; coutInput string x:x;nx=strlen(x);coutInput string y:y;ny=strlen(y);LCS lcs(nx,ny,x,y); cout最长公共子序列的长度值（最优解值）：lcs.LCSLength()=cij-1)语句中没有区分ci-1jcij-1和ci-1j