《利用動態(tài)規(guī)劃算法求解最長公共子序列問題研究6100字（論文）》

利用動態(tài)規(guī)劃算法求解最長公共子序列問題研究目錄TOC\o"1-3"\u摘要 1引言 21.最長公共子序列 31.1基本概念 31.2蠻力法求解最長公共子序列問題 32.動態(tài)規(guī)劃算法 62.1動態(tài)規(guī)劃算法中的幾個基本概念 62.2動態(tài)規(guī)劃算法的基本思想 62.3動態(tài)規(guī)劃算法的基本要素 72.4動態(tài)規(guī)劃算法的適用條件和一般步驟 72.4.1適用條件 72.4.2一般步驟 73.利用動態(tài)規(guī)劃算法求解最長公共子序列問題 83.1動態(tài)規(guī)劃算法求解最長公共子序列問題 83.1.1最長公共子序列問題的特征分析 83.1.2遞歸定義最優(yōu)值 93.1.3計算最長公共子序列的長度 103.1.4構(gòu)造LCS 123.2蠻力法與動態(tài)規(guī)劃算法比較分析 15結(jié)束語 17參考文獻 18摘要：動態(tài)規(guī)劃算法通常應(yīng)用于研究和解決那些在過程中具有特定的最優(yōu)化和特殊性質(zhì)的問題.它的基本設(shè)計思想是把要解決的問題分成許多的子問題，然后先對分出來的子問題求解，得到了這些子問題的解后就可以根據(jù)他們的解來找到原問題的解.并且這些分出來的子問題相互之間并不是獨立的，通常要采用動態(tài)規(guī)劃算法來求得.本文首先介紹最長公共子序列和動態(tài)規(guī)劃算法的相關(guān)概念，包括最優(yōu)化原理、重疊子問題等.然后結(jié)合具體例子了解如何運用動態(tài)規(guī)劃算法來求解最長公共子序列問題，并從中發(fā)現(xiàn)利用動態(tài)規(guī)劃算法的優(yōu)勢，包括有效地解決冗余、節(jié)省時間等.關(guān)鍵詞：動態(tài)規(guī)劃算法；子問題；最長公共子序列；重疊子問題引言動態(tài)規(guī)劃是一種用于設(shè)計算法的方法，可用于優(yōu)化決策過程.它也是使求解決策過程中實現(xiàn)最優(yōu)化的一種數(shù)學(xué)方法.在20世紀中葉，數(shù)學(xué)家們提出了有名的最優(yōu)化原理，以多方面深入地研究多階段決策問題.最優(yōu)化原理就是將一個多步驟的過程一步一步變成一系列獨特的問題，并一步一步地解決它們，從而創(chuàng)立了針對解決過程優(yōu)化問題的動態(tài)規(guī)劃算法這一新方法.動態(tài)規(guī)劃算法在現(xiàn)代數(shù)學(xué)、經(jīng)濟學(xué)和計算機科學(xué)中已經(jīng)有著廣泛的研究和應(yīng)用，也普遍在最優(yōu)控制、生產(chǎn)調(diào)度、機器學(xué)習(xí)等領(lǐng)域得到了廣泛的應(yīng)用，如最短路線問題、圖像數(shù)據(jù)壓縮、資源分配問題、背包問題、庫存管理問題、信息檢索，以及本文中將要探討的最長公共子序列問題.目前關(guān)于動態(tài)規(guī)劃算法與最長公共子序列的相關(guān)研究成果有很多，文獻[1]-[3]主要介紹了動態(tài)規(guī)劃算法的基本思想和基本概念原理等；文獻[4]主要介紹子序列、公共子序列、最長公共子序列等相關(guān)概念；文獻[5]-[6]主要介紹求解最長公共子序列的具體方法，如蠻力法、動態(tài)規(guī)劃算法等；文獻[7]-[12]主要介紹了運用動態(tài)規(guī)劃算法的求解步驟以及相對于其他算法所具備的優(yōu)勢；文獻[13]-[14]主要介紹了動態(tài)規(guī)劃的算法實現(xiàn).本文闡述了動態(tài)規(guī)劃算法的基本思想、相關(guān)的幾個基本概念和基本要素以及適用條件，了解運用動態(tài)規(guī)劃算法求解問題的一般步驟.接著介紹了與最長公共子序列相關(guān)的一些概念，然后結(jié)合具體的最長公共子序列問題，應(yīng)用動態(tài)規(guī)劃算法巧妙地解決問題.在利用動態(tài)規(guī)劃算法求解最長公共子序列問題的過程中，先對問題進行特征分析，然后根據(jù)遞歸公式創(chuàng)建DP數(shù)組，通過數(shù)組確定最長公共子序列的長度從而獲得最長公共子序列，并給出了C++語言算法的實現(xiàn).1.最長公共子序列1.1基本概念定義1[1]子序列：給定一個序列和一個序列，如果存在序列是的下標(biāo)序列，且嚴格遞增，并且對所有的，都滿足，那么就是的子序列.定義2[1]公共子序列：給定一個序列和一個序列，如果序列既是的子序列，也是的子序列，那么稱是和的公共子序列.定義3[1]最長公共子序列（LCS）：在序列和序列的所有公共子序列中，如果是其中長度最長的，那么序列就是和的最長公共子序列.一組序列的最長公共子序列問題是用來查找所有序列中最長子序列的問題.最長公共子串與最長公共子序列的有以下差異：在原字符串中最長公共子序列不需要是連續(xù)的，但最長公共子串必須是連續(xù)的，只要相對順序保持一致即可.最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)：可以將該問題分解成更簡單的，更小的“子問題”，并且這些子問題細分出幾的子問題，從而簡化了整個問題.在最長公共子序列問題中，子問題的解可以重復(fù)使用，也就是說，高級子問題通常會重復(fù)使用低級子問題的解.然后就可以利用動態(tài)規(guī)劃算法來解決，此時通過儲存子問題的解可以防止其被重復(fù)計算.1.2蠻力法求解最長公共子序列問題蠻力法也可以叫做枚舉法，用蠻力法求最長公共子序列的基本思想是將滿足條件的所有序列都列舉出來，從中找到最長公共子序列.這也是求解問題最容易想到的方法.蠻力法的求解步驟如下：（1）枚舉序列里的每一個子序列；（2）枚舉序列里的每一個子序列；（3）檢查子序列是否也是序列里的子序列；（4）在和的共同子序列里找到最長的子序列.例1給定字符串；字符串.運用蠻力法求解它們的最長公共子序列.解：的子序列有.的子序列有的子序列中也是的子序列有.由上述可得最長公共子序列為.算法實現(xiàn)：#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對應(yīng)的元素取出來{if(i&(1<<j))z+=x[j];}if(judge(z,y))//判斷z是不是y的子序列{intt=z.length();ans=max(ans,t);}}cout<<ans<<endl;}return0;}運行結(jié)果：結(jié)合例題可以知道第1步枚舉中所有的子序列共有個，每個子序列在中檢查是否存在的時間復(fù)雜度為.因此蠻力法的最壞時間復(fù)雜度為，這是指數(shù)級算法，從中可以發(fā)現(xiàn)利用蠻力法可以對較短的序列求LCS，但對較長的序列求LCS需要過多的時間，顯然是不適用的，因此下面我們來了解一下動態(tài)規(guī)劃算法，看看動態(tài)規(guī)劃算法相對于蠻力法是否可以更好地對較長的序列求得最長公共子序列.2.動態(tài)規(guī)劃算法2.1動態(tài)規(guī)劃算法中的幾個基本概念動態(tài)規(guī)劃：是運籌學(xué)的一個分支，可用于優(yōu)化決策過程.在多階段決策問題中，在每個階段中所做出的決策通常會受時間的影響，并且決策不僅取決于當(dāng)前狀態(tài)，還會導(dǎo)致狀態(tài)的轉(zhuǎn)移，由于決策序列就是在變化的狀態(tài)下生成的，因此有“動態(tài)”的含義，則稱這種多階段決策最優(yōu)化的解決過程為動態(tài)規(guī)劃方法.多階段決策問題：將整個活動過程分解為多個階段，然后一個一個做出適當(dāng)且正確的決策，也就是采取有效措施，當(dāng)做好一個階段相應(yīng)的決策后，下一個階段以及后面的階段都會被影響到，從而就確定了整個活動過程，這就是多階段決策問題.決策序列由各個階段的決策構(gòu)成，稱為一個策略.由于策略不同，產(chǎn)生的效果也不同，多階段決策問題，就是在可以選擇的策略中選取其中的最優(yōu)策略，使得其在一定的條件下可以達到最好的效果.最優(yōu)化原理：一個策略如果被稱為最優(yōu)化策略，那么它必須具備如下一些特點：當(dāng)前決策和過去狀態(tài)不論是怎么樣的，其余的決策都必須組合起來構(gòu)成由先前的決策所組合而形成的狀態(tài)最優(yōu)化策略.換句話說就是，最優(yōu)化策略的子策略始終是最佳的.2.2動態(tài)規(guī)劃算法的基本思想動態(tài)規(guī)劃算法通常被廣泛應(yīng)用來解決那些在過程中具有某種最優(yōu)特征和性質(zhì)的問題.這類最優(yōu)問題在過程中很有可能出現(xiàn)多種最優(yōu)可行的方法.每一個解都必須擁有一個相對應(yīng)的值，我們要在過程中找到一個具有最優(yōu)值的解.動態(tài)規(guī)劃算法與分治法也有相似之處，他們的基本理念和思想都是將所需要解決的問題分解為多個子問題，首先來解決子問題，然后在從這些所得子問題在解中獲取了原問題的所得子.動態(tài)規(guī)劃算法與傳統(tǒng)的分治方式存在以下幾點不同：一個問題如用動態(tài)規(guī)劃算法來求解，那么得到的所有子問題中往往是不會有重復(fù)的.但是如果用分治法來求解，會得到許多重復(fù)的子問題，并且子問題的數(shù)目很大，還會被重復(fù)地計算很多次.如果可以用一個表來記錄求得的子問題的解，在需要的時候通過表找到所需要的子問題的答案，則可以避免進行多次重復(fù)計算并節(jié)省時間.像這樣用一個表將所有已解的子問題的答案記錄在里面.將被計算過的子問題的結(jié)果填入表中，無論將來是否要使用到該子問題.這就是動態(tài)規(guī)劃法的基本思路.2.3動態(tài)規(guī)劃算法的基本要素最優(yōu)子結(jié)構(gòu)：一個問題如果具有最優(yōu)子結(jié)構(gòu)的性質(zhì)，那么這個問題的子問題的最優(yōu)解就包含在這個問題的最優(yōu)解中.根據(jù)問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可以發(fā)現(xiàn)該問題可用動態(tài)規(guī)劃算法來解決.在動態(tài)規(guī)劃算法中，根據(jù)問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，問題的最優(yōu)解就由子問題的最優(yōu)解以自底向上的方式逐步構(gòu)造出來了.重疊子問題：動態(tài)規(guī)劃算法可以解決的問題的另一個要素就是子問題還需具有重疊性質(zhì).當(dāng)使用遞歸算法的時候，要一個一個逐步求解，新產(chǎn)生的問題有可能是前面已經(jīng)存在的，此時還要計算就使得前面的問題被多次計算了.如果使用動態(tài)規(guī)劃算法，則是利用子問題具有的重疊性質(zhì)，將子問題的解記錄在表中，如果再次需要子問題，就從表中提取，使得每個子問題只被求解一次，不會浪費時間，提高解決問題的效率.2.4動態(tài)規(guī)劃算法的適用條件和一般步驟2.4.1適用條件要利用動態(tài)規(guī)劃算法來求解的問題的需要具有以下幾個性質(zhì)：（1）滿足最優(yōu)化原理.（2）無后效性：一旦確定一個階段的狀態(tài)，這個狀態(tài)后續(xù)決策就不會使它受到影響.也就是說，以前的狀態(tài)不會被后續(xù)的某種狀態(tài)所影響到，只會影響到當(dāng)前狀態(tài).（3）有重疊子問題：具有該性質(zhì)時，可以發(fā)現(xiàn)動態(tài)規(guī)劃算法相對于其他算法存在的優(yōu)勢.但這個條件并不是必要的2.4.2一般步驟設(shè)計一個問題的動態(tài)規(guī)劃算法主要有以下幾步：（1）找到最優(yōu)解的性質(zhì)并表征其結(jié)構(gòu)特征.（2）遞歸定義最優(yōu)解的值.（3）通過自下而上的方法計算出最優(yōu)值.（4）根據(jù)計算最優(yōu)解時獲得的信息來構(gòu)建最優(yōu)解.如果只需要一個最優(yōu)解的值，而不是這個結(jié)本身，就不需要第（4）步.如果需要得到這個解本身，也就是說需要執(zhí)行第（4）步，這往往需要我們在第（3）步中記錄一些額外的信息，以方便第（4）步的求解.3.利用動態(tài)規(guī)劃算法求解最長公共子序列問題3.1動態(tài)規(guī)劃算法求解最長公共子序列問題3.1.1最長公共子序列問題的特征分析設(shè)和是兩個序列，令為和的最長公共子序列.這里找出就是一個最優(yōu)化問題.那么要找到和的最長公共子序列，首先要考慮的最后一個元素和的最后一個元素.（1）當(dāng)時，則該元素一定位于公共子序列中.所以現(xiàn)在要找的是.此時就是原問題的一個子問題，因此就是和的一個最長公共子序列.（2）當(dāng)時，則兩個序列的最后一個元素不相等，就不可能是最長公共子序列中的元素，此時就產(chǎn)生了兩個子問題：和.表示：最長公共序列可以在和中找.表示：最長公共序列可以在和中找.求解上面兩個子問題，就是所求的的公共子序列中最長的那個.即為了更好地理解上述性質(zhì)，下面結(jié)合例2進行分析.例2給定兩個字符串；字符串.求它們的最長公共子序列.由題可以得到下圖：圖1圖解LCS3.1.2遞歸定義最優(yōu)值上述特征簡而言之就是，如果的最后一個元素和的最后一個元素相等，那么我們需要求解，并且在這個LCS的末尾將和相等的最后一個元素加入其中，這樣得到的一個新的LCS就是接下來要求的.如果的最后一個元素與的最后一個元素不相等，則需要求解兩個子問題，即和.兩個LCS中較長者就是和的一個LCS.上述三個子問題看似是不重疊的，但實際它們是重疊的，因為它們只重疊了一大部分.例如第二個子問題，當(dāng)和的最后一個元素不相同時，我們還需要將繼續(xù)分解成：和，也就是說：繼續(xù)分解子問題時，有些問題是重疊的.根據(jù)上述分析，定義表示：和的最長公共子序列的長度，可以得出下面遞歸公式：3.1.3計算最長公共子序列的長度這里以，為例，首先創(chuàng)建DP數(shù)組如下圖：圖2空DP數(shù)組表圖中的空白格子先根據(jù)兩個序列填上相應(yīng)的數(shù)字，把第一行和第一列的每個格子里都記上零，再根據(jù)上面得出的遞歸公式填寫表格，也就是說：如果橫向第i個元素與豎向第j個元素對應(yīng)相等，該空格的值.如果不相等，則取和中較大者.最后可以得到下圖，根據(jù)性質(zhì)，為和的LCS的長度，也就是5.圖3DP數(shù)組算法實現(xiàn)：#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數(shù)組中的字母有沒有相等的c[i][k]=c[i-1][k-1]+1;//如果相等的話,把左上的數(shù)字加1else//不相等{c[i][k]=max(c[i-1][k],c[i][k-1]);//選取這個位置上面和左邊中最大者}}}cout<<c[n][m]<<endl;return0;}運行結(jié)果：3.1.4構(gòu)造LCS上面計算了最長公共子序列的長度，我們現(xiàn)在從開始倒推出X和Y的LCS.，且，所以倒推回去，的值來源于的值(因為).，且，所以倒推回去，的值來源于.以此類推，如果遇到，且這種存在分支的情況，這里要選擇一個方向，得到第一種結(jié)果，綠色方格為相等元素，即：圖4第一種情況選擇另一個方向，會得到另一個結(jié)果，此時.圖5第二種情況算法實現(xiàn)：#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]里面存儲的是個數(shù)字}char*build_lcs(chars[],char*X,char*Y){inti=strlen(X),k=strlen(Y);intk=lcs_len(X,Y,c);s[k]='\0';//s數(shù)字保存的是最大公共子序列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;}運行結(jié)果：3.2蠻力法與動態(tài)規(guī)劃算法比較分析根據(jù)上面分析可以得到下表：表1蠻力法與動態(tài)規(guī)劃算法的對比蠻力法動態(tài)規(guī)劃算法基本思路對每一種情況都進行列舉從后向前對兩個序列進行判斷時間復(fù)雜度適用情況求較短序列的LCS既可以求較短序列的LCS也可以求較長序列的LCS運用蠻力法求解最長公共子序列的最壞時間復(fù)雜度為，像這樣指數(shù)級算法對較長的序列求LCS需要消耗的時間太長，顯然是不適用的，因此只能用于求解較短的序列的LCS.運用動態(tài)規(guī)劃算法求最長公共子序列問題的時間復(fù)雜度為，空間復(fù)雜度亦為.從中可以看出，動態(tài)規(guī)劃算法相對于蠻力法，可以更有效地解決冗余，使得原本具有指數(shù)級復(fù)雜度算法的時間復(fù)雜度降低，大大節(jié)省了時間.結(jié)束語本文主要是介紹利用動態(tài)規(guī)劃算法求解最長公共子序列問題.文章第一部分簡單介紹了最長公共子序列及其相關(guān)概念；第二部分講述了動態(tài)規(guī)劃算法的基本要素、基本思想、適用條件及一般步驟等；第三部分通過對具體例子求最長公共子序列并運用動態(tài)規(guī)劃算法來求解.動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題.這類問題中可能會有許多可行解.每一個解都有對應(yīng)的一個值，我們想要找的解具有最優(yōu)值.我們在運用動態(tài)規(guī)劃算法求解最長公共子序列的過程中，可以發(fā)現(xiàn)動態(tài)規(guī)劃算法有著其他算法沒有的優(yōu)勢，即對每個子問題它只會求解一次，將其保存在一個表格中，避免了不必要的重復(fù)計算，大大地節(jié)省了時間.通過對本次課題的研究和學(xué)習(xí)，我也收獲了很多，也了解了還有很多其他算法需要程序設(shè)計人員進一步去優(yōu)化完善.參考文獻[1]張瑩.動