最长公共子序列(LCS)算法

《算法设计与分析》上机报告姓名：张先荣学号：SA16225439日期：2016/11/29上机题目：实验5：最长公共子序列算法实验环境：CPU：CoreI3;内存:2G;操作系统：window7;软件平台：VS2013;一、算法设计与分析：题目一:一个给定序列的子序列就是该给定序列中去掉零个或者多个元素的序列。形式化来讲就是：给定一个序列X={x1，x2，……，xm}，另外一个序列Z={z1、z2、……，zk}，如果存在X的一个严格递增小标序列<i1，i2……，ik>，使得对所有j=1,2，……k，有xij=zj，那么Z是X的子序列。例如：Z={B,C,D,B}是X={A,B,C,B,D,A,B}的一个子序列，相应的小标为<2,3,5,7>。从定义可以看出子序列直接的元素不一定是相邻的。公共子序列：给定两个序列X和Y，如果Z既是X的一个子序列又是Y的一个子序列，那么称序列Z是X和Y的公共子序列。例如：X={A,B,C,B,D,A,B}，Y={B,D,C,A,B,A}，那么序列{B,C,A}是X和Y的一个公共子序列，但不不是最长公共子序列。最长公共子序列〔LCS〕问题描述：给定两个序列X={x1，x2，……，xm}和Y={y1，y2，……，yn}，找出X和Y的最长公共子序列。2、动态规划解决过程1〕描述一个最长公共子序列如果序列比拟短，可以采用蛮力法枚举出X的所有子序列，然后检查是否是Y的子序列，并记录所发现的最长子序列。如果序列比拟长，这种方法需要指数级时间，不切实际。LCS的最优子结构定理：设X={x1，x2，……，xm}和Y={y1，y2，……，yn}为两个序列，并设Z={z1、z2、……，zk}为X和Y的任意一个LCS，那么：〔1〕如果xm=yn，那么zk=xm=yn，而且Zk-1是Xm-1和Yn-1的一个LCS。〔2〕如果xm≠yn，那么zk≠xm蕴含Z是是Xm-1和Yn的一个LCS。〔3〕如果xm≠yn，那么zk≠yn蕴含Z是是Xm和Yn-1的一个LCS。定理说明两个序列的一个LCS也包含两个序列的前缀的一个LCS，即LCS问题具有最优子结构性质。2〕一个递归解根据LCS的子结构可知，要找序列X和Y的LCS，根据xm与yn是否相等进行判断的，如果xm=yn那么产生一个子问题，否那么产生两个子问题。设C[i,j]为序列Xi和Yj的一个LCS的长度。如果i=0或者j=0，即一个序列的长度为0，那么LCS的长度为0。LCS问题的最优子结构的递归式如下所示：回朔过程如下：由于每次调用至少向上或向左〔或向上向左同时〕移动一步，故最多调用(m+n)次就会遇到i=0或j=0的情况，此时开始返回。返回时与递归调用时方向相反，步数相同，故算法时间复杂度为Θ(m+n)。二、核心代码：用随机数生成N个随机数，每个随机数都是对应1，2，3，4，范围是4，再根据随机数对应A，T，C，G。生成两个DNA串。DNA串的长度由用户自定义：用动态规划算法，生成一个2维表，记录代价，此时还要记录时间：根据动态规划的回朔图，输出公共序列，并结束计时：三、结果与分析：1.用户输入10，运行时间955ms: 2.生成长度为1000的序列，运行时间为1316ms.随机生成长度为10000的序列，时间为4188ms:分析：动态规划比普通算法确实节省了很多时间。总结：蛮力法是解决最长公共子序列问题最容易想到的方法，即对S的每一个子序列，检查是否为T的子序列，从而确定它是否为S和T的公共子序列，并且选出最长的公共子序列。S和T的所有子序列都检查过后即可求出S和T的最长公共子序列。S的一个子序列相应于下标序列1,2，...，n的一个子序列。因此，S共有2^n个子序列。当然，T也有2^m个子序列。因此，蛮力法的时间复杂度为O(2^n*2^m)，这可是指数级别的啊附录〔源代码〕算法源代码〔C/C++/JAVA描述〕C#代码：namespaceAlgorithm_experiment_5{classProgram{staticvoidMain(string[]args){Console.ForegroundColor=ConsoleColor.Yellow;Console.WriteLine("中国科大算法实验5——最长公共子序列LCS算法");Console.WriteLine("-----------------------------------------------------------");Console.WriteLine("SA16225439张先荣软设6班");Console.WriteLine();Console.WriteLine("-----------------------------------------------------------");Console.WriteLine("输出了两行DNA序列：");Console.WriteLine("请输入生成DNA序列长度：");intaii=Int32.Parse(Console.ReadLine());Randomrandom=newRandom();int[]integer1=newint[aii];int[]integer2=newint[aii];for(intiii=0;iii<aii;iii++){integer1[iii]=random.Next(1,4);integer2[iii]=random.Next(1,4);}stringstr1="",str2="";for(intiii=0;iii<aii;iii++){switch(integer1[iii]){case1:str1=str1+"A";break;case2:str1=str1+"T";break;case3:str1=str1+"C";break;case4:str1=str1+"G";break;}switch(integer2[iii]){case1:str2=str2+"A";break;case2:str2=str2+"T";break;case3:str2=str2+"C";break;case4:str2=str2+"G";break;}}Console.ReadKey();Console.WriteLine("第一个DNA序列：");Console.WriteLine(str1);Console.ReadKey();Console.WriteLine("-----------------------------------------------------------");Console.WriteLine("第二个DNA序列：");Console.WriteLine(str2);Console.WriteLine("-----------------------------------------------------------");Console.ReadKey();Stopwatchsw=newStopwatch();sw.Start();intm=str1.Length;intn=str2.Length;int[,]arr=newint[m+1,n+1];for(intii=1;ii<=m;ii++){arr[ii,0]=0;}for(intjj=1;jj<=n;jj++){arr[0,jj]=0;}inti=0;intj=0;for(i=1;i<=m;i++){for(j=1;j<=n;j++){if(str1[i-1]==str2[j-1]){arr[i,j]=arr[i-1,j-1]+1;}elseif(arr[i,j-1]>=arr[i-1,j]){arr[i,j]=arr[i,j-1];}else{arr[i,j]=arr[i-1,j];}}}Console.ReadKey();Console.WriteLine("倒序输出最长公共子序列：");strings="";for(i=m,j=n;i>=1&&j>=1;){if(str1[i-1]==str2[j-1]){Console.Write(str1[i-1]);s=s+str1[i-1];i--;j--;}elseif(arr[i,j-1]>arr[i-1,j]){j--;}else{i--;}}sw.Stop();Console.WriteLine();Console.WriteLine("-----------------------------------------------------------");Console.ReadKey();Console.WriteLine("正序输出最长公共子序列：");for(i=s.Length-1;i>=0;i--){Console.Write(s[i]);}Console.WriteLin