動態(tài)規(guī)劃解最長公共子序列問題

動態(tài)規(guī)劃解最長公共子序列問題動態(tài)規(guī)劃主要針對最優(yōu)化問題，它的決策是全面考慮不同的情況分別進行決策，，最后通過多階段決策逐步找出問題的最終解.當各個階段采取決策后，會不斷決策出新的數(shù)據(jù)，直到找到最優(yōu)解.每次決策依賴于當前狀態(tài)，又隨機引起狀態(tài)的轉(zhuǎn)移.一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，故有”動態(tài)”的含義.所以，這種多階段最優(yōu)化決策解決問題的過程稱為動態(tài)規(guī)劃.一問題的描述與分析字符序列的子序列是指從給定字符序列中隨意地（不一定連續(xù)）去掉若干字符（可能一個也不去掉）后形成的字符序列..令給定的字符序列X="x0，x1，x2，?xm-1”，序列Y="y0，y1，…yk-廣是X的子序列，存在X的一個嚴格遞增下標序列i=i0，i1，i2，?ik-1，使得對所有的j=0，1，2，?k-1，有xi=yi。例如X="ABCBDAB”，Y=“BCDB^是X的一個子序列。給定兩個序列A和B，稱序列Z是A和B公共子序列，是指Z同是A和B的子序列。求最長公共子序列。若A的長度為m，B的長度為n，則A的子序列有2*m-1個，B的子序列有2*n-1個。采用枚舉法分別對A和B的所以子序列一一檢查，最終求出最長公共子序列。如此比較次數(shù)（2*2n）接近指數(shù)階，當n較大時，算法太耗時，不可取。所以要全面考慮不同的情況分別進行決策,，最后通過多階段決策逐步找出問題的最終解.當各個階段采取決策后，會不斷決策出新的數(shù)據(jù)，直到找到最優(yōu)解。二、算法設計（或算法步驟）A=''a0，a1，a2,……am-1''，B=''b0，b1，b2,……bn-1”，且Z=''z0，z1，z2……zk-1''，為她們的最長公共子序列。不難證明有一下結(jié)論：（1） 如果am-1=bn-1，則zk-1=am-1=bn-1,且“z0,z1,z2, zk-2”是“a0,a1,a2, am-2”和“b0,b1,b2,……bn-2”的一個最長公共子序列；（2） 如果am-1!=bn-1,則若zk-1!=am-1,則“z0,z1,z2, zk-1”是“a0,a1,a2, am-2”和”b0,b1,b2,……bn-1”的一個最長公共子序列。（3） 如果am-1!=bn-1,則若zk-1!=bn-1,則“z0,z1,z2, zk-1”是“a0,a1,a2, am-1”和“b0,b1,b2,……bn-2”的一個最長公共子序列。如此找到了原問題與其子問題的遞歸關系?；敬鎯Y(jié)構(gòu)是存儲兩個字符串及其最長公共子序列的3個一位數(shù)組。當然要找出最長公共子序列，要存儲當前最長公共子序列的長度和當前公共子序列的長度，而若只存儲當前信息，最后只能求解最長公共子序列的長度，卻不能找到最長公共子序列本身。因此需建立一個（n+1）*（m+1）的二維數(shù)組c,c[i][j]存儲序列“a0,a1,a2……ai-2”和“b0,b1,……bj-1”的最長公共子序列長度，由上遞推關系分析，計算c[i][j]可遞歸的表述如下：(1)c[i][j]=0如果i=0或j=0;(1)c[i][j]=0c[i][j]=c[i-1][j-1]+1 如果i,j>0,且a[i-1]=b[j-1]c[i][j]=max(c[i][j-1],c[i-1][j]) 如果i,j>0,且a[i-1]!=b[j-1]以此可寫出計算兩個序列的最長公共子序列的長度函數(shù)，最終求解出c[m][n].三、算法實現(xiàn)由二維數(shù)組c的遞歸定義，c[i][j]的結(jié)果僅依賴于c[i-1][j-1],c[i-1][j]和c[i][j-1].可以從c[m][n]開始，跟蹤c[i][j]結(jié)果的產(chǎn)生過程，從而逆向構(gòu)造最長公共子序列。include<stdio.h>include<string.h>#defineN100/*字符串的最大長度限制*/chara[N],/*第一個字符串*/b[N],/*第二個字符串*/str[N];/*用于存放a與b的公共子序列*//*計算兩個序列的最長公共子序列的長度*/intlcs_len(char*a,char*b,intc[][N])(intm=strlen(a),/*計算兩個序列的長度*/n=strlen(b),i,/*行指針*/j;/*列指針*/for(i=0;i<=m;i++)c[i][0]=0;/*j==0表示b串長度為0，無論a串多長，兩者的公共子序列長度為0*/for(j=1;j<=n;j++)c[0][j]=0;/*根據(jù)上一個類推*/for(i=1;i<=m;i++)/*開始遞推*/for(j=1;j<=n;j++)/*若兩序列的最后一個字符相同，那么公共子序列長度為去掉這最后一個字符后新生成的兩個串的公共子序列長度+1*/if(a[i-1]==b[j-1]){c[i][j]=c[i-1][j-1]+1;printf("\nc[%d][%d]=c[%d-1][%d-1]+1\n",i,j,i,j);}/**/elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];printf("\nc[%d][%d]=c[%d-1][%d]\n",i,j,i,j);}/*若兩序列最后一個字符不同，那么他們最大子序列的長度為c[i-1][j]和c[i][j-1]中較大的一個*/else{c[i][j]=c[i][j-1];printf("\nc[%d][%d]=c[%d][%d-1]\n",i,j,i,j);}/*調(diào)試：將生成的數(shù)組方陣顯示出來,m行，n列*/printf("\n");printf("");for(j=0;j<=n;j++)printf("%d,",j);/*顯示列標號*/printf("\n");for(i=0;i<=m;i++){printf("%d:",i);/*顯示行標號*/for(j=0;j<=n;j++)printf("%d,",c[i][j]);printf("\n");/*一行顯示完，換下一行*/}returnc[m][n];/*結(jié)果：a與b的最大子序列長度存在c[m][n]中*/}/*構(gòu)造最長子序列函數(shù)*/char*build_lcs(chars[],char*a,char*b){/*根據(jù)lcs_len()函數(shù)計算的結(jié)果，倒推出最長子序列，結(jié)果放在、[]中*/intk,/*a與b最長子序列的長度*/i=strlen(a),/*a串長度*/j=strlen(b),/*b*/c[N][N];/*存放全部的計算過程，動態(tài)規(guī)劃，體現(xiàn)在這個地方，中間計算結(jié)果都在這里*/k=lcs_len(a,b,c);/*將c□□傳給lcs_len()計算并求出長度，將中間結(jié)果放在c[][]中*/s[k]='\0';/*s串的結(jié)束標記*/while(k>0)/*開始倒推*/if(c[i][j]==c[i-1][j])i--;elseif(c[i][j]==c[i][j-1])j--;else{s[--k]=a[i-1];/*將一個公共字符存入s中*/i--;j--;}returns;}/*測試程序*/voidmain(){printf("Entertwostring(<%d)!\n",N);scanf("%s%s",a,b);printf("LCS=%s\n",build_lcs(str,a,b));以X=”ABCBDAB”與Y=”BDCABA”為例，兩字符串算法實現(xiàn)求解最長公共子序列的長度和最長公共子序列的求解過程。0I23456yjBDCABA0000000..QJJJ\<10\*~1T\0TTJiT..0\tr:\—3QTt?r0Tr&ntfend0\44CDABEntertwostring(<100)!a,b,ca,b,c,dc[1][1]=c[1-1][1-1]+1c[1][2]=c[1][2-1]c[1][3]=c[1][3-1]c[1][4]=c[1][4-1]c[1][5]=c[1][5-1]c[1][6]=c[1][6-1]c[2][2]=c[2-1][2-1]+1c[2][3]=c[2][3-1]c[2][4]=c[2-1][4-1]+1c[2][5]=c[2][5-1]c[2][6]=c[2-1][6-1]+1c[2][7]=c[2][7-1]c[3][1]=c[3-1][1]c[3][2]=c[3-1][2]c[3][3]=c[3-1][3-1]+1c[3][4]=c[3][4-1]c[3][5]=c[3][5-1]c[3][6]=c[3][6-1]c[3][7]=c[3][7-1]c[4][1]=c[ 4 - 1 ][1]c[4][2]=c[ 4 - 1 ][2-1]+ 1c[4][3]=c[ 4 - 1 ][3]c[4][4]=c[ 4 - 1 ][4-1]+ 1c[4][5]=c[4][5-1]c[4][6]=c[4-1][6-1]+1c[4][7]=c[4][7-1]

c[5][3]=c[5-1][3]c[5][4]=c[5-1][4]c[5][5]=c[5-1][5-1]+1c[5][6]=c[5][6-1]c[5][7]=c[5][7-1]0123450,1,2,3,4,5,6,7,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,012345LCS=a,b,cPressanykeytocontinueEntertwostring(<100)!w，e,r,t,yw,r,t,ec[1][1]=c[1-1][1-1]+1TOC\o"1-5"\h\zc[1][2] = c[ 1][ 2 -1]c[1][3] = c[ 1][ 3 -1]c[1][4] = c[ 1][ 4 -1]c[1][5] = c[ 1][ 5 -1]c[1][6] = c[ 1][ 6 -1]c[1][7] = c[ 1][ 7 -1]c[2][3 ] =c[2][3- 1]c[2][4 ] =c[2-1][ 4- 1 ]+ 1c[2][5 ] =c[2][5- 1]c[2][6 ] =c[2-1][6- 1 ]+ 1c[2][7 ] =c[2][7- 1]c[3][1 ] =c[3-1 ][ 1 ]c[3][2 ] =c[3-1 ][ 2 ]c[3][3 ] =c[3-1 ][ 3 ]c[3][4 ] =c[3-1 ][ 4 ]c[3][5 ] =c[3-1 ][ 5 ]c[3][6 ] =c[3-1 ][ 6 ]c[3][7 ] =c[3-1 ][ 7 - 1 ]+ 1c[4][1 ] =c[4-1 ][ 1 ]c[4][2 ] =c[4-1 ][ 2 - 1 ]+ 1c[4][3 ] =c[4-1 ][ 3 ]c[4][4 ] =c[4-1 ][ 4 - 1 ]+ 1c[4][5]=c[4][5-1]c[4][6 ] =c[4-1 ][ 6 - 1 ]+ 1c[4][7 ] =c[4-1 ][ 7 ]c[5][1 ] =c[5-1 ][ 1 ]c[5][4 ] =c[5-1][ 4]c[5][5 ] =c[5-1][ 5]c[5][6]=c[5-1][6]c[5][7 ] =c[5-1][ 7]c[6][1 ] =c[6-1][ 1]c[6][2 ] =c[6-1][ 2- 1 ]+ 1c[6][3 ] =c[6-1][ 3]c[6][4 ] =c[6-1][ 4- 1 ]+ 1c[6][5 ] =c[6][5- 1]c[6][6 ] =c[6-1][ 6- 1 ]+ 1c[6][7 ] =c[6][7- 1]c[7][1 ] =c[7-1][ 1]c[7][2 ] =c[7-1][ 2]c[7][3 ] =c[7-1][ 3]c[7][4 ] =c[