最长公共子序列问题

实验三最长公共子序列问题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.实验总结对最长公共子序列的求解，实际上是对动态规划思想的学习，这个实验实现的算法比前两个实验实现的算法难度又有所提升，对字符串进行反复递归时容易出错，所以只能先对简单的字符串计算进行测试。个人认为，动态规划思想中难的部分就是突出在反复的循环/递归，对循环参数的取值往往让人伤神，需要十分谨慎小心，并反复的测验才能确保算法的正确性。