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

实验报告（2009/2010学年第一学期）课程名称算法分析与设计A实验名称动态规划法实验时间2009年11月20日指导单位计算机学院软件工程系指导教师张怡婷学生姓名丁力琪班级学号B07030907学院(系)计算机学院专业软件工程2实验报告实验名称动态规划法指导教师张怡婷实验类型验证实验学时2×2实验时间2009-11-20一、实验目的和任务目的：加深对动态规划法的算法原理及实现过程的理解，学习用动态规划法解决实际应用中的最长公共子序列问题。任务：用动态规划法实现求两序列的最长公共子序列，其比较结果可用于基因比较、文章比较等多个领域。要求：掌握动态规划法的思想，及动态规划法在实际中的应用；分析最长公共子序列的问题特征，选择算法策略并设计具体算法，编程实现两输入序列的比较，并输出它们的最长公共子序列。二、实验环境(实验设备)硬件：计算机软件：VisualC++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的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法，求解时间为指数级别的，因此不可取。2、分析LCS问题特征可知，如果Z={z1,z2,……，zk}为它们的最长公共子序列，则它们一定具有以下性质：（1）若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列；（2）若xm≠yn且xm≠zk，则Z是Xm-1和Y的最长公共子序列；（3）若xm≠yn且zk≠yn，则Z是X和Y的最长公共子序列。这样就将求X和Y的最长公共子序列问题，分解为求解较小规模的问题：若xm=ym，则进一步分解为求解两个（前缀）子字符序列Xm-1和Yn-1的最长公共子序列问题；如果xm≠yn，则原问题转化为求解两个子问题，即找出Xm-1和Y的最长公共子序列与找出X和Yn-1的最长公共子序列，取两者中较长者作为X和Y的最长公共子序列。由此可见，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，具有最优子结构性质。3、令c[i][j]保存字符序列Xi={x1,x2,……,xi}和Yj={y1,y2,……,yj}的最长公共子序列的长度，由上述分析可得如下递推式：0i=0或j=0c[i][j]=c[i-1][j-1]+1i,j0且xi=yjmax{c[i][j-1],c[i-1][j]}i,j0且xi≠yj由此可见，最长公共子序列的求解具有重叠子问题性质，如果采用递归算法实现，会得到一个指数时间算法，因此需要采用动态规划法自底向上求解，并保存子问题的解，这样可以避免重复计算子问题，在多项式时间内完成计算。4、为了能由最优解值进一步得到最优解（即最长公共子序列），还需要一个二维数组s[][]，数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。45、编程定义LCS类，计算最长公共子序列的长度，并给出最长公共子序列：（注意：C语言中数组下标由0开始，而实际数据在一维数组a、b和二维数组是c、s中存放却是从小标为1处开始。）类中数据成员主要有二维数组c和s用于动态规划法求解过程中保存子问题的求解结果，一维数组a和b用于存放来两个字符序列，m和n为两个字符序列中实际字符的个数。这些数据成员均应在LCS类的构造函数中进行初始化：#includeiostream#includestringusingnamespacestd;#definemaxlength11classLCS{public:LCS(intnx,intny,char*x,char*y)//对数据成员m、n、a、b、c、s初始化{m=nx;n=ny;a=newchar[m+2];b=newchar[n+2];memset(a,0,m+2);memset(b,0,n+2);//将x和y中的字符写入一维数组a和b中for(inti=0;inx+2;i++){a[i+1]=x[i];}for(inti=0;iny+2;i++){b[i+1]=y[i];}a[0]=b[0]=0;c=newint[maxlength][maxlength];s=newint[maxlength][maxlength];//对二维数组c和s进行初始化for(inti=0;imaxlength;i++){for(intj=0;jmaxlength;j++){s[i][j]=0;c[i][j]=0;}5}}intLCSLength();voidCLCS(){CLCS(m,n);}private:voidCLCS(inti,intj)const;int(*c)[maxlength],(*s)[maxlength];intm,n;char*a,*b;};//6、类中成员函数主要有LCSLength()和CLCS()两个公有成员函数，CLCS()通过调用私有递归//成员函数CLCS(intt,intj)实现。intLCS::LCSLength(){for(inti=0;i=m;i++)c[i][0]=0;for(intj=0;j=n;j++)c[0][j]=0;for(inti=1;i=m;i++){for(intj=1;j=n;j++){if(a[i]==b[j]){c[i][j]=c[i-1][j-1]+1;s[i][j]=1;}elseif(c[i-1][j]=c[i][j-1]){c[i][j]=c[i-1][j];s[i][j]=2;}else{c[i][j]=c[i][j-1];s[i][j]=3;}}}returnc[m][n];//返回最优解值}voidLCS::CLCS(inti,intj)const6{if(i==0||j==0||s[i][j]==0)return;if(s[i][j]==1){CLCS(i-1,j-1);couta[i];}elseif(s[i][j]==2)CLCS(i-1,j);elseCLCS(i,j-1);}//7、主函数中负责输入两个待比较的字符串x和y（长度不超过maxlength-1），求得他们的实际//字符长度nx和ny，并调用LCS类的成员函数LCSLength()和CLCS()求最优解值和最优解：intmain(){intnx,ny;char*x,*y;x=newchar[maxlength];y=newchar[maxlength];cout请输入Xendl;gets(x);nx=strlen(x);cout请输入Yendl;gets(y);ny=strlen(y);LCSlcs(nx,ny,x,y);coutX和Y最长公共子序列的长度为：lcs.LCSLength()endl;cout该序列为endl;lcs.CLCS();delete[]x;delete[]y;return0;}78、输入序列X={x1,x2,……,xm}={a,b,c,b,d,a,b}和Y={y1,y2,……,yn}={b,d,c,a,b,a}作为测试数据，测试程序是否能够正确运行？输出结果是什么？运行正确，实验结果显示：4bcba9、分析该动态规划算法的两个主要成员函数intLCSLength()和voidCLCS()的时间复杂性。intLCSLength()的平均时间复杂度为O(2n)；voidCLCS()的平均时间复杂度为O(nlogn)。思考1、备忘录方法是动态规划法的一个变种，它采用分治法思想，自顶向下直接递归求最优解。但与分治法不同的是，备忘录方法为每个已经计算的子问题建立备忘录，即保存子问题的计算结果以备需要时应用，从而避免子问题的重复求解。试改写当前的intLCSLength()函数，用备忘录方法来求解最长公共子序列。（提示：备忘录方法采用的事递归求解方式，因此需要用一个公有成员函数intLCSLength();来调用私有递归成员函数intLCSLength(inti,intj);共同实现）intLCS::LCSLength(inti,intj)8{if(i==0||j==0)return0;if(c[i][j]!=0)returnc[i][j];else{if(a[i]==b[j]){c[i][j]+LCSLength(i-1,j-1)+1;s[i][j]=1;}elseif(LCSLength(i-1,j)=LCSLength(i,j-1)){c[i][j]=LCSLength(i-1,j);s[i][j]=2;}else{c[i][j]=LCSLength(i,j-1);s[i][j]=3;}}returnc[i][j];}2、若省去原程序中的二维数组s，是否还能求的最长公共子序列问题的最优解？请编写一个类似的CLCS算法实现：不借助二维数组s在O(m+n)的时间内构造最长公共子序列的功能。（提示：此时可在当前c[i][j]处比较a[i]和b[j]。如果相等，则调用CLCS(i-1,j-1)，输出a[i]（或b[j]）。如果不相等，则比较c[i-1][j]和c[i][j-1]。若c[i-1][j]≥c[i][j-1],则递归调用CLCS（i-1，j）；否则，递归调用CLCS(i,j-1)。）voidLCS::CLCS(inti,intj)const{if(i==0||j==0)return;if(a[i]==b[j]){CLCS(i-1,fj-1);couta[i];}else{if(c[i-1][j]=c[i][j-1])CLCS(i-1,j);elseCLCS(i,j-1);}}93、如果只需计算最长公共子序列的长度，而无须构造最优解，则如何改进原有程序可以使得算法的空间需求大大减少？请改写原程序，使算法的空间复杂度减少为O(min{m,n})。（提示：计算c[i][j]仅用到第i行和第i-1行元素，因此，只需两行元素空间就可以计算最长公共子序列的长度，并且选用序列长度较短的一个作为y序列，可以缩短每行元素的个数，从而进一步减少空间复杂度。）#includeiostream#includestringusingnamespacestd;#definemaxlength11classLCS{public:LCS(intnx,intny,char*x,char*y){m=nx;n=ny;a=newchar[m+1];b=newchar[n+1];memset(a,0,m+2);memset(b,0,n+2);for(inti=0;inx;i++)a[i+1]=x[i];for(inti=0;iny;i++)b[i+1]=y[i];if(mn){l=m;s=n;}else{char*t;t=x;x=y;y=t;s=m;l=n;}c1=newint[s+1];c2=newint[s+1];for(inti=0;is;i++)c1[i]=c2[i]=0;}intLCSLength();private:10intm,n;int*c1,*c2;intl,s;char*a,*b;};intLCS::LCSLength(){int*temp;for(inti=0;is;i++)c1[i]=0;for(inti=1;i=l;i++){for(intj=1;j=s;j++){if(a[i]==b[j])c2[j]=c1[j-1]+1;elseif(c1[j]=c2[j-1])c2[j]=c1[j];elsec2[j]=c2[j-1];}for(