您好,欢迎访问三七文档
实验三最长公共子序列问题1.实验环境本实验采用java语言编写实现,环境:JDK1.8,编译器:eclipse2.实验目的通过最长公共子序列问题,巩固并详细分析动态规划思想和解题步骤。3.设计思路最长公共子序列的定义为:设有两个序列S1[1..m]和S2[1..n],需要寻找它们之间的一个最长公共子序列。例如,假定有两个序列:S1:INTHEBEGINNINGS2:ALLTHINGSARELOST则S1和S2的一个最长公共子序列为THING。又比如:S1:ABCBDABS2:BDCABA则它们的一个最长公共子序列为BCBA。这里需要注意的是,一个子序列不一定必须是连续的,即中间可被其他字符分开,单它们的顺序必须是正确的。另外,最长公共子序列不一定只有一个,而我们需要寻找的是其中一个。当然,如果要求子序列里面的元素必须连成一片也是可以的。实际上,连成一片的版本比这里实现的更容易。4.过程我们可以通过蛮力策略解决这个问题,步骤如下:1.检查S1[1..m]里面每一个子序列。2.看看其是否也是S2[1..n]里的子序列。3.在每一步记录当前找到的子序列里面最长的子序列。这种方法的效率十分低下。因此本实验采用动态规划的方法实现该算法。利用动态规划寻找最长公共子序列步骤如下:1.寻找最长公共子序列的长度。2.扩展寻找长度的算法来获取最长公共子序列。策略:考虑序列S1和S2的前缀序列。设c[i,j]=|LCS(S1[1..i],S2[1..j])|,则有c[m,n]=|LCS(S1,S2)|所以有c[i–1,j–1]+1,如要S1[i]=S2[j]c[i,j]=max{c[i-1,j],c[i,j-1]},如果S1[i]≠S2[j]然后回溯输出最长公共子序列过程:5.实现源代码packagelcsimple;publicclassLCSImplem{//返回一个决定搜索方向的数组privatestaticint[][]getLength(char[]stringArr1,char[]stringArr12){int[][]b=newint[stringArr1.length][stringArr12.length];int[][]c=newint[stringArr1.length][stringArr12.length];for(inti=1;istringArr1.length;i++){for(intj=1;jstringArr12.length;j++){//S1[i]=S2[j]的情况if(stringArr1[i]==stringArr12[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}//S1[i]≠S2[j]的情况elseif(c[i-1][j]=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=0;}//S1[i]≠S2[j]的情况else{c[i][j]=c[i][j-1];b[i][j]=-1;}}}returnb;}//回溯的实现,采用递归法privatestaticvoidDisplay(int[][]b,char[]stringArr1,inti,intj){if(i==0||j==0)return;if(b[i][j]==1){Display(b,stringArr1,i-1,j-1);System.out.print(stringArr1[i]+);}elseif(b[i][j]==0){Display(b,stringArr1,i-1,j);}elseif(b[i][j]==-1){Display(b,stringArr1,i,j-1);}}publicstaticvoidmain(String[]args){Stringstr1=ABCBDAB;Stringstr2=BDCABA;str1=+str1;str2=+str2;char[]stringArr1=str1.toCharArray();char[]stringArr2=str2.toCharArray();int[][]b=getLength(stringArr1,stringArr2);Display(b,stringArr1,stringArr1.length-1,stringArr2.length-1);}}6.断点调试及代码分析首先在main方法里定义两个字符串,如:对这两个字符串,使它们的第一个字符为空,即初始化之后的c[][]的第一行第一列,之所以要空出,是因为c[][]代表的是两个字符串数组多少个,0的意思就是某个字符串的长度为0。然后将这两个字符串分割为char型数组:接下来就调用getLength方法计算出决定搜索方向的数组,传到该方法的两个数组参数stringArr1和stringArr2的值可以看到然后定义两个二维数组b[][],c[][],大小为stringArr1.length*stringArr12.length,用于接受结果矩阵。接着遍历每一个stringArr1的值,与stringArr2的每一个值做比较:循环内的第一层判断,就是当当前字符匹配的时候,c[i][j]最为前缀序列为后面的匹配计算使用,将当前值赋值为1,b[i][j]用于保存匹配结果记为1:把下面的两个判断作为第二层判断,即当当前字符不匹配的时候对c[i][j]做计算,c[i][j]就是该值在矩阵中上面一个数和左边一个数中较大的值:这些判断就是对该矩阵值的计算,c矩阵:但是这个方法返回的是b矩阵,b矩阵在当前位置在字符匹配时的值为1,不匹配时,就对c矩阵做出比较,该值在矩阵中左边的数值大于上边的数值时,b矩阵在当前位置在字符匹配时的值为0,反之记为-1。因此,计算返回b矩阵,输出b矩阵得到:最后就是对结果的输出,对b矩阵调用Display方法:当当前值为1时,说明字符匹配成功,再对左上方的值进行比较;当当前值为0时,说明左边的值大于上边的值,采用递归法,再对上边的值进行比较;当当前值为-1时,对左边的值进行比较。下面是对b的迭代:这个方法,就是对下面矩阵方向的计算:最后输出判断中匹配上的结果。7.算法分析由于每次调用至少向上或向左(或向上向左同时)移动一步,故最多调用(m*n)次就会遇到i=0或j=0的情况,此时开始返回。返回时与递归调用时方向相反,步数相同,故算法时间复杂度为Θ(m*n)。8.实验结果在main方法中输入的字符串为:所以得到结果:改变输入的字符串测试:结果准确,实验结束。9.实验总结对最长公共子序列的求解,实际上是对动态规划思想的学习,这个实验实现的算法比前两个实验实现的算法难度又有所提升,对字符串进行反复递归时容易出错,所以只能先对简单的字符串计算进行测试。个人认为,动态规划思想中难的部分就是突出在反复的循环/递归,对循环参数的取值往往让人伤神,需要十分谨慎小心,并反复的测验才能确保算法的正确性。
本文标题:最长公共子序列问题
链接地址:https://www.777doc.com/doc-1801276 .html