最长公共子序列问题.doc

该【最长公共子序列问题 】是由【知识改变命运】上传分享，文档一共【9】页，该文档可以免费在线阅读，需要了解更多关于【最长公共子序列问题 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。实验三最长公共子序列问题
实验环境
本实验采纳java语言编写实现,环境:,编译器:eclipse
实验目的
经过最长公共子序列问题,稳固并详尽剖析动向规划思想和解题
步骤。
设计思路
最长公共子序列的定义为:设有两个序列S1[1..m]和S2[1..n],需要
找寻它们之间的一个最长公共子序列。
比如,假设有两个序列:
S1:INTHEBEGINNING
S2:ALLTHINGSARELOST
则S1和S2的一个最长公共子序列为THING。又比方:
S1:ABCBDAB
S2:BDCABA
则它们的一个最长公共子序列为BCBA。
这里需要注意的是,一个子序列不必定一定是连续的,即中间可
被其余字符分开,单它们的次序一定是正确的。此外,最长公共子序
列不必定只有一个,而我们需要找寻的是此中一个。
自然,假如要求子序列里面的元素一定连成一片也是能够的。实
际上,连成一片的版本比这里实现的更简单。
过程
我们能够经过蛮力策略解决这个问题,步骤以下:
检查S1[1..m]里面每一个子序列。
看看其能否也是S2[1..n]里的子序列。
在每一步记录目前找到的子序列里面最长的子序列。
这类方法的效率十分低下。所以本实验采纳动向规划的方法实现该算法。
利用动向规划找寻最长公共子序列步骤以下:
找寻最长公共子序列的长度。
扩展找寻长度的算法来获得最长公共子序列。
策略:考虑序列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]
而后回溯输出最长公共子序列过程:
实现源代码
packagelcsimple;
publicclassLCSImplem{
断点调试及代码剖析
第一在main方法里定义两个字符串,如:
对这两个字符串,使它们的第一个字符为空,即初始化以后的c[][]的第一行第一列,之所以要空出,是因为c[][]代表的是两个字符串数组多少个,0的意思就是某个字符串的长度为0。而后将这两个字符串切割为char型数组:
接下来就调用getLength方法计算出决定搜寻方向的数组,传到该方法的两个数组参数stringArr1和stringArr2的值能够看到
而后定义两个二维数组b[][],c[][],大小为*,用于接受结果矩阵。
接着遍历每一个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时,对左侧的值进行比较。下边是对
的迭代:
这个方法,就是对下边矩阵方向的计算:
最后输出判断中般配上的结果。
算法剖析
因为每次调用起码向上或向左(或向上向左同时)挪动一步,故
最多调用(m*n)次就会碰到i=0或j=0的状况,此时开始返回。返回时与递归调用时方向相反,步数同样,故算法时间复杂度为Θ(m*n)。
实验结果
在main方法中输入的字符串为:
所以获得结果:
改变输入的字符串测试:
结果正确,实验结束。
实验总结
对最长公共子序列的求解,其实是对动向规划思想的学****这
个实验实现的算法比前两个实验实现的算法难度又有所提高,对字符
串进行频频递归时简单犯错,所以只好先对简单的字符串计算进行测
试。个人以为,动向规划思想中难的部分就是突出在频频的循环/递
归,对循环参数的取值常常让人伤神,需要十分慎重当心,并频频的
测试才能保证算法的正确性。