搜索
实验二最长公共子序列问题一、实验目的：1、理解动态规划算法的概念；2、掌握动态规划算法的基本要素；3、掌握设计动态规划算法的步骤；4、通过应用范例学习动态规划算法的设计技巧与策略；二、实验内容及要求：1、使用动态规划算法解决最长公共子序列问题：给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。。2、通过上机实验进行算法实现。3、保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。三、实验原理：动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程（decisionprocess)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistepdecisionprocess)的优化问题时，提出了著名的最优化原理(principleofoptimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著DynamicProgramming，这是该领域的第一本著作。算法总体思想：1)动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题,先求解子问题，然后从这些子问题的解得到原问题的解。2)与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。子问题中存在大量的公共子问题，在分治求解过程中被多次重复计算，保存计算结果，为后面的计算直接引用，减少重复计算次数这就是动态规划的基本思想。3)用动态规划算法求解问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题的答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量重复计算，最终得到多项式时间算法。动态规划基本步骤：1）找出最优解的性质，并刻划其结构特征。2）递归地定义最优值。3）以自底向上的方式计算出最优值。4）根据计算最优值时得到的信息，构造最优解。前三个步骤是动态规划算法的基本步骤。在只需求出最优值的情况，步骤四可以省去。若需要求最优解，则必须执行步骤四，根据所记录的信息，快速构造出最优解。四、程序代码：#includeiostream#includestring#defineN20usingnamespacestd;intd[N][N];intLCSlength(char*a,char*b,intc[][N]){inti,j;intalen=strlen(a);intblen=strlen(b);for(i=0;i=alen;i++)c[i][0]=0;for(j=0;j=blen;j++)c[0][j]=0;for(i=1;i=alen;i++)for(j=1;j=blen;j++)if(a[i-1]==b[j-1])c[i][j]=c[i-1][j-1]+1;elsec[i][j]=c[i][j-1]c[i-1][j]?c[i][j-1]:c[i-1][j];returnc[alen][blen];}char*LCS(char*s,char*a,char*b){intc[N][N];inti=strlen(a);intj=strlen(b);intk=LCSlength(a,b,c);s[k]='\0';while(k0){if(c[i][j]==c[i-1][j])i--;elseif(c[i][j]==c[i][j-1])j--;else{s[--k]=a[i-1];i--;j--;}}returns;}main(){char*s=newchar[N];chars1[N];chars2[N];cout请输入第一个字符串:;cins1;cout请输入第二个字符串:;cins2;cout最长的公共子序列为:LCS(s,s1,s2)长度为:LCSlength(s1,s2,d)endl;deletes;}五、结果运行与分析：六、心得与体会：本次实验通过动态算法解决最长公共子序列问题，对于求两个序列的一个最长公共子序列,LCSlength算法时间复杂性为0(alen*blen),能够得到较满意的结果。但另一个方面,这种算法在对c[i-l][j]与c[i][j-l]值的比较中忽略了相等的情况,即在两个序列的最长公共子序列不唯一时不可能求出所有的最长公共子序列。