最长公共子序列问题.doc

实验三 最长公共子序列问题1. 实验环境本实验采用java语言编写实现，环境：JDK1.8，编译器：eclipse2. 实验目的通过最长公共子序列问题，巩固并详细分析动态规划思想和解题步骤。3. 设计思路最长公共子序列的定义为：设有两个序列S11.m和S21.n，需要寻找它们之间的一个最长公共子序列。例如，假定有两个序列：S1：I N T H E B E G I N N I N GS2：A L L T H I N G S A R E L O S T则S1 和S2的一个最长公共子序列为THING。又比如：S1：A B C B D A BS2：B D C A B A则它们的一个最长公共子序列为BCBA。这里需要注意的是，一个子序列不一定必须是连续的，即中间可被其他字符分开，单它们的顺序必须是正确的。另外，最长公共子序列不一定只有一个，而我们需要寻找的是其中一个。当然，如果要求子序列里面的元素必须连成一片也是可以的。实际上，连成一片的版本比这里实现的更容易。4. 过程我们可以通过蛮力策略解决这个问题，步骤如下：1. 检查S11.m里面每一个子序列。2. 看看其是否也是S21.n里的子序列。3. 在每一步记录当前找到的子序列里面最长的子序列。这种方法的效率十分低下。因此本实验采用动态规划的方法实现该算法。利用动态规划寻找最长公共子序列步骤如下：1. 寻找最长公共子序列的长度。2. 扩展寻找长度的算法来获取最长公共子序列。策略：考虑序列S1和S2的前缀序列。设ci，j = |LCS (S11.i,S21.j)|，则有cm，n = |LCS(S1，S2)|所以有c i 1 ， j 1 + 1，如要S1i = S2jci，j = max c i - 1，j ，c i ，j -1 ，如果S1iS2j然后回溯输出最长公共子序列过程：5. 实现源代码package lcsimple;public class LCSImplem /返回一个决定搜索方向的数组private static int getLength(char stringArr1, char stringArr12) int b = new intstringArr1.lengthstringArr12.length;int c = new intstringArr1.lengthstringArr12.length;for(int i=1; istringArr1.length; i+)for(int j=1; j= cij-1)cij = ci-1j;bij = 0;/S1iS2j的情况elsecij = cij-1;bij = -1;return b;/回溯的实现，采用递归法private static void Display(int b, char stringArr1, int i, int j)if(i = 0 | j = 0)return;if(bij = 1)Display(b, stringArr1, i-1, j-1);System.out.print(stringArr1i + );else if(bij = 0)Display(b, stringArr1, i-1,j);else if(bij = -1)Display(b, stringArr1, i, j-1);public static void main(String args) String str1 = ABCBDAB;String str2 = 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的每一个值做比较：循环内的第一层判断，就是当当前字符匹配的时候，cij最为前缀序列为后面的匹配计算使用，将当前值赋值为1，bij用于保存匹配结果记为1：把下面的两个判断作为第二层判断，即当当前字符不匹配的时候对cij做计算，cij就是该值在矩阵中上面一个数和左边一个数中较大的值：这些判断就是对该矩阵值的计算，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. 实验总结对最长公共子序列的求解，实际上是对动态规划思想的学