《利用动态规划算法求解最长公共子序列问题研究6100字（论文）》

利用动态规划算法求解最长公共子序列问题研究目录TOC\o"1-3"\u摘要 1引言 21.最长公共子序列 31.1基本概念 31.2蛮力法求解最长公共子序列问题 32.动态规划算法 62.1动态规划算法中的几个基本概念 62.2动态规划算法的基本思想 62.3动态规划算法的基本要素 72.4动态规划算法的适用条件和一般步骤 72.4.1适用条件 72.4.2一般步骤 73.利用动态规划算法求解最长公共子序列问题 83.1动态规划算法求解最长公共子序列问题 83.1.1最长公共子序列问题的特征分析 83.1.2递归定义最优值 93.1.3计算最长公共子序列的长度 103.1.4构造LCS 123.2蛮力法与动态规划算法比较分析 15结束语 17参考文献 18摘要：动态规划算法通常应用于研究和解决那些在过程中具有特定的最优化和特殊性质的问题.它的基本设计思想是把要解决的问题分成许多的子问题，然后先对分出来的子问题求解，得到了这些子问题的解后就可以根据他们的解来找到原问题的解.并且这些分出来的子问题相互之间并不是独立的，通常要采用动态规划算法来求得.本文首先介绍最长公共子序列和动态规划算法的相关概念，包括最优化原理、重叠子问题等.然后结合具体例子了解如何运用动态规划算法来求解最长公共子序列问题，并从中发现利用动态规划算法的优势，包括有效地解决冗余、节省时间等.关键词：动态规划算法；子问题；最长公共子序列；重叠子问题引言动态规划是一种用于设计算法的方法，可用于优化决策过程.它也是使求解决策过程中实现最优化的一种数学方法.在20世纪中叶，数学家们提出了有名的最优化原理，以多方面深入地研究多阶段决策问题.最优化原理就是将一个多步骤的过程一步一步变成一系列独特的问题，并一步一步地解决它们，从而创立了针对解决过程优化问题的动态规划算法这一新方法.动态规划算法在现代数学、经济学和计算机科学中已经有着广泛的研究和应用，也普遍在最优控制、生产调度、机器学习等领域得到了广泛的应用，如最短路线问题、图像数据压缩、资源分配问题、背包问题、库存管理问题、信息检索，以及本文中将要探讨的最长公共子序列问题.目前关于动态规划算法与最长公共子序列的相关研究成果有很多，文献[1]-[3]主要介绍了动态规划算法的基本思想和基本概念原理等；文献[4]主要介绍子序列、公共子序列、最长公共子序列等相关概念；文献[5]-[6]主要介绍求解最长公共子序列的具体方法，如蛮力法、动态规划算法等；文献[7]-[12]主要介绍了运用动态规划算法的求解步骤以及相对于其他算法所具备的优势；文献[13]-[14]主要介绍了动态规划的算法实现.本文阐述了动态规划算法的基本思想、相关的几个基本概念和基本要素以及适用条件，了解运用动态规划算法求解问题的一般步骤.接着介绍了与最长公共子序列相关的一些概念，然后结合具体的最长公共子序列问题，应用动态规划算法巧妙地解决问题.在利用动态规划算法求解最长公共子序列问题的过程中，先对问题进行特征分析，然后根据递归公式创建DP数组，通过数组确定最长公共子序列的长度从而获得最长公共子序列，并给出了C++语言算法的实现.1.最长公共子序列1.1基本概念定义1[1]子序列：给定一个序列和一个序列，如果存在序列是的下标序列，且严格递增，并且对所有的，都满足，那么就是的子序列.定义2[1]公共子序列：给定一个序列和一个序列，如果序列既是的子序列，也是的子序列，那么称是和的公共子序列.定义3[1]最长公共子序列（LCS）：在序列和序列的所有公共子序列中，如果是其中长度最长的，那么序列就是和的最长公共子序列.一组序列的最长公共子序列问题是用来查找所有序列中最长子序列的问题.最长公共子串与最长公共子序列的有以下差异：在原字符串中最长公共子序列不需要是连续的，但最长公共子串必须是连续的，只要相对顺序保持一致即可.最长公共子序列问题具有最优子结构：可以将该问题分解成更简单的，更小的“子问题”，并且这些子问题细分出几的子问题，从而简化了整个问题.在最长公共子序列问题中，子问题的解可以重复使用，也就是说，高级子问题通常会重复使用低级子问题的解.然后就可以利用动态规划算法来解决，此时通过储存子问题的解可以防止其被重复计算.1.2蛮力法求解最长公共子序列问题蛮力法也可以叫做枚举法，用蛮力法求最长公共子序列的基本思想是将满足条件的所有序列都列举出来，从中找到最长公共子序列.这也是求解问题最容易想到的方法.蛮力法的求解步骤如下：（1）枚举序列里的每一个子序列；（2）枚举序列里的每一个子序列；（3）检查子序列是否也是序列里的子序列；（4）在和的共同子序列里找到最长的子序列.例1给定字符串；字符串.运用蛮力法求解它们的最长公共子序列.解：的子序列有.的子序列有的子序列中也是的子序列有.由上述可得最长公共子序列为.算法实现：#include<bits/stdc++.h>usingnamespacestd;booljudge(stringz,stringy)//遍历字符串y{for(inti=0,j=0;i<y.length();i++){if(y[i]==z[j])j++;if(j==z.length())returntrue;}returnfalse;}intmain(){stringx,y;while(cin>>x>>y){intans=0; //最长公共子序列长度为0if(y.length()<x.length())swap(x,y);//枚举x的所有子序列intn=x.length();for(inti=0;i<(1<<n);i++)//通过枚举方案i得到子序列z{stringz;for(intj=0;j<n;j++)//i的二进制的1对应的元素取出来{if(i&(1<<j))z+=x[j];}if(judge(z,y))//判断z是不是y的子序列{intt=z.length();ans=max(ans,t);}}cout<<ans<<endl;}return0;}运行结果：结合例题可以知道第1步枚举中所有的子序列共有个，每个子序列在中检查是否存在的时间复杂度为.因此蛮力法的最坏时间复杂度为，这是指数级算法，从中可以发现利用蛮力法可以对较短的序列求LCS，但对较长的序列求LCS需要过多的时间，显然是不适用的，因此下面我们来了解一下动态规划算法，看看动态规划算法相对于蛮力法是否可以更好地对较长的序列求得最长公共子序列.2.动态规划算法2.1动态规划算法中的几个基本概念动态规划：是运筹学的一个分支，可用于优化决策过程.在多阶段决策问题中，在每个阶段中所做出的决策通常会受时间的影响，并且决策不仅取决于当前状态，还会导致状态的转移，由于决策序列就是在变化的状态下生成的，因此有“动态”的含义，则称这种多阶段决策最优化的解决过程为动态规划方法.多阶段决策问题：将整个活动过程分解为多个阶段，然后一个一个做出适当且正确的决策，也就是采取有效措施，当做好一个阶段相应的决策后，下一个阶段以及后面的阶段都会被影响到，从而就确定了整个活动过程，这就是多阶段决策问题.决策序列由各个阶段的决策构成，称为一个策略.由于策略不同，产生的效果也不同，多阶段决策问题，就是在可以选择的策略中选取其中的最优策略，使得其在一定的条件下可以达到最好的效果.最优化原理：一个策略如果被称为最优化策略，那么它必须具备如下一些特点：当前决策和过去状态不论是怎么样的，其余的决策都必须组合起来构成由先前的决策所组合而形成的状态最优化策略.换句话说就是，最优化策略的子策略始终是最佳的.2.2动态规划算法的基本思想动态规划算法通常被广泛应用来解决那些在过程中具有某种最优特征和性质的问题.这类最优问题在过程中很有可能出现多种最优可行的方法.每一个解都必须拥有一个相对应的值，我们要在过程中找到一个具有最优值的解.动态规划算法与分治法也有相似之处，他们的基本理念和思想都是将所需要解决的问题分解为多个子问题，首先来解决子问题，然后在从这些所得子问题在解中获取了原问题的所得子.动态规划算法与传统的分治方式存在以下几点不同：一个问题如用动态规划算法来求解，那么得到的所有子问题中往往是不会有重复的.但是如果用分治法来求解，会得到许多重复的子问题，并且子问题的数目很大，还会被重复地计算很多次.如果可以用一个表来记录求得的子问题的解，在需要的时候通过表找到所需要的子问题的答案，则可以避免进行多次重复计算并节省时间.像这样用一个表将所有已解的子问题的答案记录在里面.将被计算过的子问题的结果填入表中，无论将来是否要使用到该子问题.这就是动态规划法的基本思路.2.3动态规划算法的基本要素最优子结构：一个问题如果具有最优子结构的性质，那么这个问题的子问题的最优解就包含在这个问题的最优解中.根据问题的最优子结构性质可以发现该问题可用动态规划算法来解决.在动态规划算法中，根据问题的最优子结构性质，问题的最优解就由子问题的最优解以自底向上的方式逐步构造出来了.重叠子问题：动态规划算法可以解决的问题的另一个要素就是子问题还需具有重叠性质.当使用递归算法的时候，要一个一个逐步求解，新产生的问题有可能是前面已经存在的，此时还要计算就使得前面的问题被多次计算了.如果使用动态规划算法，则是利用子问题具有的重叠性质，将子问题的解记录在表中，如果再次需要子问题，就从表中提取，使得每个子问题只被求解一次，不会浪费时间，提高解决问题的效率.2.4动态规划算法的适用条件和一般步骤2.4.1适用条件要利用动态规划算法来求解的问题的需要具有以下几个性质：（1）满足最优化原理.（2）无后效性：一旦确定一个阶段的状态，这个状态后续决策就不会使它受到影响.也就是说，以前的状态不会被后续的某种状态所影响到，只会影响到当前状态.（3）有重叠子问题：具有该性质时，可以发现动态规划算法相对于其他算法存在的优势.但这个条件并不是必要的2.4.2一般步骤设计一个问题的动态规划算法主要有以下几步：（1）找到最优解的性质并表征其结构特征.（2）递归定义最优解的值.（3）通过自下而上的方法计算出最优值.（4）根据计算最优解时获得的信息来构建最优解.如果只需要一个最优解的值，而不是这个结本身，就不需要第（4）步.如果需要得到这个解本身，也就是说需要执行第（4）步，这往往需要我们在第（3）步中记录一些额外的信息，以方便第（4）步的求解.3.利用动态规划算法求解最长公共子序列问题3.1动态规划算法求解最长公共子序列问题3.1.1最长公共子序列问题的特征分析设和是两个序列，令为和的最长公共子序列.这里找出就是一个最优化问题.那么要找到和的最长公共子序列，首先要考虑的最后一个元素和的最后一个元素.（1）当时，则该元素一定位于公共子序列中.所以现在要找的是.此时就是原问题的一个子问题，因此就是和的一个最长公共子序列.（2）当时，则两个序列的最后一个元素不相等，就不可能是最长公共子序列中的元素，此时就产生了两个子问题：和.表示：最长公共序列可以在和中找.表示：最长公共序列可以在和中找.求解上面两个子问题，就是所求的的公共子序列中最长的那个.即为了更好地理解上述性质，下面结合例2进行分析.例2给定两个字符串；字符串.求它们的最长公共子序列.由题可以得到下图：图1图解LCS3.1.2递归定义最优值上述特征简而言之就是，如果的最后一个元素和的最后一个元素相等，那么我们需要求解，并且在这个LCS的末尾将和相等的最后一个元素加入其中，这样得到的一个新的LCS就是接下来要求的.如果的最后一个元素与的最后一个元素不相等，则需要求解两个子问题，即和.两个LCS中较长者就是和的一个LCS.上述三个子问题看似是不重叠的，但实际它们是重叠的，因为它们只重叠了一大部分.例如第二个子问题，当和的最后一个元素不相同时，我们还需要将继续分解成：和，也就是说：继续分解子问题时，有些问题是重叠的.根据上述分析，定义表示：和的最长公共子序列的长度，可以得出下面递归公式：3.1.3计算最长公共子序列的长度这里以，为例，首先创建DP数组如下图：图2空DP数组表图中的空白格子先根据两个序列填上相应的数字，把第一行和第一列的每个格子里都记上零，再根据上面得出的递归公式填写表格，也就是说：如果横向第i个元素与竖向第j个元素对应相等，该空格的值.如果不相等，则取和中较大者.最后可以得到下图，根据性质，为和的LCS的长度，也就是5.图3DP数组算法实现：#include<bits/stdc++.h>usingnamespacestd;constintN=1000+10;intc[N][N];//定义了一个N*N的矩阵intmain(){stringx,y;cin>>x>>y;intn=x.length();intm=y.length();//两个字符串的长度x.insert(0,"#");y.insert(0,"#");memset(c,0,sizeof(c));//依次填表for(inti=1;i<=n;i++){for(intk=1;j<=m;k++){if(x[i]==y[k])//判断第i行和Y数组中的字母有没有相等的c[i][k]=c[i-1][k-1]+1;//如果相等的话,把左上的数字加1else//不相等{c[i][k]=max(c[i-1][k],c[i][k-1]);//选取这个位置上面和左边中最大者}}}cout<<c[n][m]<<endl;return0;}运行结果：3.1.4构造LCS上面计算了最长公共子序列的长度，我们现在从开始倒推出X和Y的LCS.，且，所以倒推回去，的值来源于的值(因为).，且，所以倒推回去，的值来源于.以此类推，如果遇到，且这种存在分支的情况，这里要选择一个方向，得到第一种结果，绿色方格为相等元素，即：图4第一种情况选择另一个方向，会得到另一个结果，此时.图5第二种情况算法实现：#include<stdio.h>#include<string.h>#defineN100charX[N],Y[N],str[N];intc[N][N],num=0;intlcs_len(char*X,char*Y,intC[][N]){intn=strlen(X),m=strlen(Y),i,k;for(i=0;i<=n;i++)//给第一列赋初值c[i][0]=0;for(i=0;i<=m;i++)//给第一行赋初值c[0][i]=0;for(i=1;i<=n;i++){for(k=1;k<=m;k++){if(X[i-1]==Y[k-1])c[i][k]=c[i-1][k-1]+1;elseif(c[i-1][k]>=c[i][k-1])c[i][k]=c[i-1][k];elsec[i][k]=c[i][k-1];}}returnc[n][m];//这个c[n][m]里面存储的是个数字}char*build_lcs(chars[],char*X,char*Y){inti=strlen(X),k=strlen(Y);intk=lcs_len(X,Y,c);s[k]='\0';//s数字保存的是最大公共子序列while(k>0){if(c[i][k]==c[i-1][k])i--;elseif(c[i][k]==c[i][k-1])k--;else{s[--k]=X[i-1];i--;k--;num++;}}returns;}intmain(){printf("请输入字符串X：");scanf("%s",&X);printf("请输入字符串Y：");scanf("%s",&Y);printf("Lsc=%s\n",build_lcs(str,X,Y));printf("最长公共子序列的长度为：%d",num);getchar();return0;}运行结果：3.2蛮力法与动态规划算法比较分析根据上面分析可以得到下表：表1蛮力法与动态规划算法的对比蛮力法动态规划算法基本思路对每一种情况都进行列举从后向前对两个序列进行判断时间复杂度适用情况求较短序列的LCS既可以求较短序列的LCS也可以求较长序列的LCS运用蛮力法求解最长公共子序列的最坏时间复杂度为，像这样指数级算法对较长的序列求LCS需要消耗的时间太长，显然是不适用的，因此只能用于求解较短的序列的LCS.运用动态规划算法求最长公共子序列问题的时间复杂度为，空间复杂度亦为.从中可以看出，动态规划算法相对于蛮力法，可以更有效地解决冗余，使得原本具有指数级复杂度算法的时间复杂度降低，大大节省了时间.结束语本文主要是介绍利用动态规划算法求解最长公共子序列问题.文章第一部分简单介绍了最长公共子序列及其相关概念；第二部分讲述了动态规划算法的基本要素、基本思想、适用条件及一般步骤等；第三部分通过对具体例子求最长公共子序列并运用动态规划算法来求解.动态规划算法通常用于求解具有某种最优性质的问题.这类问题中可能会有许多可行解.每一个解都有对应的一个值，我们想要找的解具有最优值.我们在运用动态规划算法求解最长公共子序列的过程中，可以发现动态规划算法有着其他算法没有的优势，即对每个子问题它只会求解一次，将其保存在一个表格中，避免了不必要的重复计算，大大地节省了时间.通过对本次课题的研究和学习，我也收获了很多，也了解了还有很多其他算法需要程序设计人员进一步去优化完善.参考文献[1]张莹.动