算法分析報告

動態(tài)規(guī)劃法解最長公共子序列問題動態(tài)規(guī)劃法是一種經(jīng)典的算法：動態(tài)規(guī)劃法是一種經(jīng)典的算法：動態(tài)規(guī)劃算法與分治法類似，基本思想是將待求解問題分解成若干個子問題，先求解子問題，然后從子問題的解得到原問題的解。但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的，不同子問題的數(shù)目常常只有多項式量級。在用分治法求解時，有些子問題被重復(fù)計算了許多次。如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復(fù)計算，從而得到多項式時間算法。為了達(dá)到這個目的，可以用一個表來記錄所有已解決的子問題的答案，不管是否該子問題在以后被用到，只要它被計算過，就將結(jié)果填入表中，這就是動態(tài)規(guī)劃法的基本思想。—、問題描述與分析動態(tài)規(guī)劃法解最長公共子序列問題是一個經(jīng)典問題。動態(tài)規(guī)劃法的基本要素：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)。最優(yōu)子結(jié)構(gòu)性質(zhì)：設(shè)計動態(tài)規(guī)劃算法的第一步通常是刻畫最優(yōu)解的結(jié)構(gòu)。當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。它提供了該問題可用動態(tài)規(guī)劃算法求解的重要線索。重疊子問題：在用遞歸算法自頂向下求解問題時，每次產(chǎn)生的子問題并不總是新問題，有的問題被重復(fù)計算多次。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)，對每一個子問題只解一次，而后將其解保存在一個表格中，當(dāng)再次需要解此子問題時，只是簡單的用常數(shù)時間查看一下結(jié)果。通常，不同的子問題個數(shù)隨問題的大小呈多項式增長。因此，用動態(tài)規(guī)劃算法通常只需要多項式時間，從而獲得較高的解題效率。子序列：一個給定序列的子序列是在該序列中刪去若干兀素后得到的序列。確切的說，若給定序列X={x1,x2，??%}，則另一序列Z={z1,z2^*zk}，X的子序列是指存在一個嚴(yán)格遞增下標(biāo)序列{"2??%.},使得對于所有j=1,2,???k有z=x..。12, k Jij公共子序列：給定兩個序列X和Y，當(dāng)另一序列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的一個公共子序列，但它不是X和Y的最長公共子序列。序列{B,C,B,A}也是X和Y的一個公共子序列，它的長度為4,而且它是X和Y的最長公共子序列，因為X和Y沒有長度大于4的公共子序列。最長公共子序列問題描述：給定兩個子序列X={X],x2,??%}和Y={y1,y2…ym},找出X和Y的最長公共子序列。 m ,m問題的分析過程：首先，確定X和Y的公共子序列，再求出X和Y的最長公共子序列;其次，建立最優(yōu)值的遞歸關(guān)系；計算問題的最優(yōu)值；最后，構(gòu)造最長的公共子序列。二、算法設(shè)計（或算法步驟）用動態(tài)規(guī)劃法解解最長公共子序列問題的算法總體思想是：a動態(tài)規(guī)劃法是一種經(jīng)典的算法：基本思想是將待求解問題分解成若干個子問題，先求解子問題，然后從子問題的解得到原問題的解。b適用動態(tài)規(guī)劃方法解決的子問題一般不是獨(dú)立的，子問題中存在大量的公共子問題，保存計算結(jié)果，為后面的計算直接引用，減少重復(fù)計算次數(shù)是該方法的基本思想。c可根據(jù)其遞歸式以自底向上的方式進(jìn)行計算，在計算過程中，保存已解決子問題的答案，每個子問題只計算一次，從而避免大量重復(fù)計算，最終得到多項式時間算法。用動態(tài)規(guī)劃法解解最長公共子序列問題的算法步驟：找出最優(yōu)解的性質(zhì)，并刻畫出結(jié)構(gòu)特征：最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，先找出X和Y的公共子序列，再找出其中最長的公共子序列，它包含了這兩個序列的前綴的最長公共子序列。設(shè)序列X={xx*^x,}和Y={y,y，…y}的最長公共子序列為Z={zz…zj，則廠 1,2, 1 1 2j 1 2，K若xm=yn則zk=xm=yn,且Zk-1是Xm-1和Yn-1的最長公共子序列；{若xm^yn則zk=手xm,，且Z是Xm-1和Y的最長公共子序列；匚若xm^yn則zk=手yn,，且Z是X和Yn-1的最長公共子序列；其中，X={x,x,…偵};Y={y,y,…丫};z{z,z???%}。m-1 1 2 m-1 n-1 1 2 n-1 K-1= 1 2, k-1遞歸地定義最優(yōu)值，子問題的遞歸結(jié)構(gòu)：首先建立子問題最優(yōu)值的遞歸關(guān)系。用c[i][j]記錄序列X1和Y1的最長公共子序列的長度。其中X={xx—x};Y={y,y，…y}.當(dāng)i=0或j=0時，空序列是X和Y1 1, 2, 1j1 2 j i j的最長公共子序列，故此時c[i][j]=0.在其他情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：10 i=0,j=0c[i-1][j-1]+1 i,j>0;xi=yjmax{c[i][j-1],c[i-1][j]} i,j>0;xi^yj以自底向上的方式計算出最優(yōu)值，可以提高算法的效率。問題的最優(yōu)值即為X和Y的最長公共子序列，其中c[i][j]存儲Xi和Yj的最長公共子序列。根據(jù)計算最優(yōu)值時得到的信息'，構(gòu)造最優(yōu)解，即構(gòu)造最長公共子序列。在算法lcs中，每一次遞歸調(diào)用使i或j減1，因此算法的計算時間為O(m+n)。三、算法實現(xiàn)該程序的實現(xiàn)用的是C++程序執(zhí)行完成的#include<iostream.h>#include<string>usingnamespacestd;#defineN100charX[N],Y[N],str[N]; //其中X和Y用來存儲兩個字符串intc[N][N],num=0;intlcs_len(char*X,char*Y,intc[][N]){intm=strlen(X),n=strlen(Y),i,j;for(i=0;i<=m;i++) //c[i][j]用來存儲*和Yj的最長公共子序列的長度c[i][0]=0; //考慮Y.集合里面沒有元素時c[i][j]的情況for(i=0;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++) //考慮當(dāng)Xi和Y.集合里面均有元素時的比較情況{ 1Jfor(j=1;j<=n;j++){if(X[i-1]==Y[j-1])c[i][j]=c[i-1][j-1]+1;elseif(c[i-1][j]>=c[i][j-1])c[i][j]=c[i-1][j];elsec[i][j]=c[i][j-1];}}returnc[m][n]; //完成對2個集合的掃描和匹配，即X和Y的最長公共子序列的長度存儲在c[m][n]中}char*build_lcs(chars[],char*X,char*Y){inti=strlen(X),j=strlen(Y);intk=lcs_len(X,Y,c);s[k]=’\0’while(k>0){if(c[i][j]==c[i-1][j])i--;elseif(c[i][j]==c[i][j-1])j--;else{s[--k]=X[i-1];i--;j--;num++;}}returns;}voidmain(){cout<〈”輸入一個長度小于”<<N<<”的字符串”vvendl; 〃進(jìn)行輸入和輸出操作cin>>X;cout<<”請再輸入一個長度小于”<<N<<”的字符串”<<endlcin>>Y;cout<<”Lsc=”<<build_lcs(str,X,Y)<<endl;cout<<”最大子序列長度為”<<num<<endl}執(zhí)行結(jié)果為：圖3-1四、算法分析（與改進(jìn)）分析部分：（1） 時間復(fù)雜度：在算法lcs中，每一次遞歸調(diào)用使i或者j減1,因此算法的計算時間為O（m+n），但由于數(shù)組c仍需要（mn）的空間，所以所做的改進(jìn)，只是對空間復(fù)雜性的常數(shù)因子的改進(jìn)。（2） 和書中的算法相比較：書中的算法如下：（a）這部分程序中有數(shù)組b的建立，由于每個數(shù)組單元的計算耗費(fèi)O（1）的時間，算法lcsLength耗時O（mn）publicstaticintlcsLength（char[]X,char[]Yint[][]b）{intm=X.length-1;intn=Ylength-1;int[][]c=newint[m+1][n+1];for(inti=1;i<=m;i++)c[i][0]=0；for(i=1;i<=n;i++)c[0][i]=0;for(inti=1;i<=m;i++)for(intj=1;j<=n;j++){if(X[i]==Y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}returnc[m][n];}(b)在算法Ics中，每一次遞歸調(diào)用使i或j減1,此算法的計算時間為O(m+n)publicstaticvoidlcs(intI,intj;char[]X,int[][]b){if(i==0||j=0)return;if(b[i][j]=1){lcs(i-1,j-1,x,b);System.out.print(X[i]);}elseif(b[i][j]==2)lcs(i-1,j,x,b);elselcs(i,j-1,x,b);}比較部分:.本算法在lcs和Lcslength中，成功的把數(shù)組b省去了。因為數(shù)組元素c[i][j]的值僅由c[i-1][j-1],c[i-1][j]和c[i][j-1]這3個數(shù)組元素的值所確定，即對于給定的數(shù)組元素c[i][j]，可以不