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

实 验 报 告（2009/2010学年 第一学期）课程名称算法分析与设计A实验名称动 态 规 划 法实验时间2009年11月20日指导单位计算机学院软件工程系指导教师张怡婷学生姓名丁力琪班级学号院(系)计算机学院专 业软件工程实 验 报 告实验名称动 态 规 划 法指导教师张怡婷实验类型验证实验学时2×2实验时间2009-11-20实验目的和任务目的：加深对动态规划法的算法原理及实现过程的理解，学习用动态规划法解决实际应用中的最长公共子序列问题。 任务：用动态规划法实现求两序列的最长公共子序列，其比较结果可用于基因比较、文章比较等多个领域。要求：掌握动态规划法的思想，及动态规划法在实际中的应用；分析最长公共子序列的问题特征，选择算法策略并设计具体算法，编程实现两输入序列的比较，并输出它们的最长公共子序列。 实验环境(实验设备)硬件：计算机软件：Visual C++实验原理及内容（包括操作过程、结果分析等）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的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法，求解时间为指数级别的，因此不可取。分析LCS问题特征可知，如果Z={z1,z2,……，zk}为它们的最长公共子序列，则它们一定具有以下性质：若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列；若xm≠yn且xm≠zk，则Z是Xm-1和Y的最长公共子序列；若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}的最长公共子序列的长度，由上述分析可得如下递推式： 0 i=0或j=0c[i][j]= c[i-1][j-1]+1 i,j0且xi=yj max{c[i][j-1],c[i-1][j]} i,j0且xi≠yj 由此可见，最长公共子序列的求解具有重叠子问题性质，如果采用递归算法实现，会得到一个指数时间算法，因此需要采用动态规划法自底向上求解，并保存子问题的解，这样可以避免重复计算子问题，在多项式时间内完成计算。为了能由最优解值进一步得到最优解（即最长公共子序列），还需要一个二维数组s[][]，数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。编程定义LCS类，计算最长公共子序列的长度，并给出最长公共子序列：（注意：C语言中数组下标由0开始，而实际数据在一维数组a、b和二维数组是c、s中存放却是从小标为1处开始。） 类中数据成员主要有二维数组c和s用于动态规划法求解过程中保存子问题的求解结果，一维数组a和b用于存放来两个字符序列，m和n为两个字符序列中实际字符的个数。这些数据成员均应在LCS类的构造函数中进行初始化：#includeiostream#includestringusing namespace std;#define maxlength 11class LCS{public:LCS(int nx,int ny,char *x,char *y) //对数据成员m、n、a、b、c、s初始化{m=nx;n=ny;a=new char[m+2];b=new char[n+2];memset(a,0,m+2);memset(b,0,n+2); //将x和y中的字符写入一维数组a和b中for(int i=0;inx+2;i++){a[i+1]=x[i];}for(int i=0;iny+2;i++){b[i+1]=y[i]