最长公共子序列的研究报告.docx

最长公共子序列的研究报告一、 问题描述最长公共子序列，英文缩写为LCS（Longest Common Subsequence）。其定义是：一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。抽象数学描述：令给定的字符序列X=x0,x1,xm-1 ,序列Y=y0,y1,yn-1 ，若序列S=s0,s1,s2,sk-1满足:1) 存在X的一个严格递增下标序列及Y的一个严格递增下标序列，使得对所有的j=0，1，k-1，有xij=sj=yaj。即S为X,Y的公共子序列2) 不存在满足性质1)且元素个数大于S的另一序列S。则称序列S为序列X,序列Y的最长公共子序列。二、 算法设计与分析计算两个序列的最长公共子序列的动态规划方法如下：以两个序列 X(长度为m)、Y(长度为n) 为例子：设有二维数组fi,j (0im,0jn) 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度，则求解的递推式如下:fi,j=0 ,i=0或j=0 ci-1j-1+1 , i,j0且xi=yj maxci,j-1,ci-1,j , i,j0且xiyj此时，二维数组fi,j中最大的数便是 X 和 Y 的最长公共子序列的长度，依据该数组回溯，便可找出最长公共子序列。此算法的时间复杂度为O(mn),若假定X,Y长度一样，则时间复杂度为(n2)。举例说明:图1而蛮力法求解最长公共子序列时，时间效率为(n3),即动态规划方法比蛮力法时间效率提高了一个数量级。三、 伪代码描述LCSstr1,str2Begin/输入两个字符串str1,str2./输出两个字符串的最长公共子序列的长度len1str1.length;len2str2.length;for i0 to len1 dofi0 0;endfor i0 to len2 dof0i 0;endfor i0 to len1 dofor j0 to len2 doflagij0;/flag是标记下标走向的数组，为1表示斜向下，2向右，3向下endendfor i1 to len1 dofor j1 to len2 doif str1i-1=str2j-1 dofij fi-1j-1+1;flagij 1;/标记向斜下方endelse if fij-1fi-1j dofij fij-1;flagij2 /标记向右endelse dofijfi-1jflagij 3/标记向下endendend/返回 flen1len2;End回溯的函数：LOOKBACK（f,str1,str2）Begin/输入：LCS得到的二维数组f及两个公共子序列str1,str2/输出：str1,str2的最长公共子序列len1str1.length;len2str2.length;ilen1;jlen2;k0;while i1 and j1doif flagij=1 do res_strk str1i-1;kk+1;jj-1;ii-1; endelse if flagij=2dojj-1;endelse if flagij=3doii-1;endend/返回结果字符串res_strEnd四、 数据及实验测试数据：实验数据总共40组，按数据长度分为10组（长度分别为1000,2000，10000），再按字符串的平均长度分4组（分别为50,100,150,200），所以是4*10=40组。无论是字符串的长度还是字符串的内容都是使用随机函数产生的，控制随机数产生的范围就可以控制一组数据的平均长度。如：需要产生字符串平均长度为100的一组字符串，则产生75到125范围的随机数，理论上它们满足均匀分布，其均值即数学期望E=i=75125i*1(125-75)=100再以它们为各字符串的长度，则控制了字符串的平均长度。实验测试：经过对数据量从1000增长到10000的若干次实验后，得出下列运行时间随数据量的增长曲线：图2五、 实验探究结论如图2，用此算法运行时间来反映算法时间效率，运用动态规划算法求解最长公共子序列时，随数据量线性增长的过程中，运行时间也