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

利用動態(tài)規(guī)劃算法解決最長公共子序列問題摘要：算法可以理解為有基本運算及規(guī)定的運算順序所構(gòu)成的完整的解題步驟。或者看成按照要求設(shè)計好的有限的確切的計算序列，并且這樣的步驟和序列可以解決一類問題。其中動態(tài)規(guī)劃是一種有效的解決問題的算法。此論文將圍繞如何利用動態(tài)規(guī)劃算法解決最長公共子序列問題展開。關(guān)鍵詞：算法，動態(tài)規(guī)劃，最長公共子序列。Abstract:Algorithmcanbeunderstoodasabasiccomputingandtheprovisionsoftheorderofoperationsthatformacompletesolvingsteps.Orasaccordingtotherequestanddesignoftheexactcalculationofgoodlimitedsequence,andthestepsandcansolveproblemofsequence.Amongthemthedynamicplanningisakindofeffectiveproblemsolvingalgorithm.Thispaperwillfocusonhowtousedynamicprogrammingalgorithmispresentedtosolvethelongestpublicsononsequence.Keywords:algorithm,thedynamicprogramming,thelongestpublicsonsequence.1引言動態(tài)規(guī)劃算法是一種有效的解決問題的算法。通常將待求解問題分解成若干個子問題，利用這一特性，可以解決很多能夠以大化小的問題，如：矩陣連成問題、求最長公共子序列、求凸多邊形最優(yōu)三角剖分、圖像壓縮、電路布線、流水作業(yè)調(diào)度等。此論文將聯(lián)系如何求解最長公共子序列來描述動態(tài)規(guī)劃算法。2動態(tài)規(guī)劃的思想2、1動態(tài)規(guī)劃的概念動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題。但是經(jīng)分解得到的子問題往往不是互相獨立的。不同子問題的數(shù)目常常只有多項式量級。在用分治法求解時，有些子問題被重復(fù)計算了許多次。如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復(fù)計算，從而得到多項式時間算法。

找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計算出最優(yōu)值。根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。2、3動態(tài)規(guī)劃算法的基本要素最優(yōu)子結(jié)構(gòu)矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。在分析問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時，所用的方法具有普遍性：首先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的，然后再設(shè)法說明在這個假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個問題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問題能用動態(tài)規(guī)劃算法求解的前提。重疊子問題遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次。這種性質(zhì)稱為子問題的重疊性質(zhì)。動態(tài)規(guī)劃算法，對每一個子問題只解一次，而后將其解保存在一個表格中，當(dāng)再次需要解此子問題時，只是簡單地用常數(shù)時間查看一下結(jié)果。通常不同的子問題個數(shù)隨問題的大小呈多項式增長。因此用動態(tài)規(guī)劃算法只需要多項式時間，從而獲得較高的解題效率。備忘錄方法備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需要時查看，避免了相同子問題的重復(fù)求解。3、利用動態(tài)規(guī)劃算法解決求最長公共子序列問題

3、1問題描述?若給定序列X={x1,x2,…,xm},則另一序列Z={z1,z2,…,zk},是X的子序列是指存在一個嚴(yán)格遞增下標(biāo)序列{ii,i2,...,ik}使得對于所有j=1,2,…,k有：zj=xij。例如，序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列，相應(yīng)的遞增下標(biāo)序列為{2,3,5,7}。?給定2個序列X和Y,當(dāng)另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。3、2最長公共子序列的結(jié)構(gòu)設(shè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長公共子序列為Z={z1,z2,…，zk},則⑴若xm=yn,^0zk=xm=yn，且zk-1是xm-1和yn-1的最長公共子序列。⑵若xm尹yn且zk尹xm，則Z是xm-1和Y的最長公共子序列。⑶若xm尹yn且zk尹yn，則Z是X和yn-1的最長公共子序列。由此可見，2個序列的最長公共子序列包含了這2個序列的前綴的最長公共子序列。因此，最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。3、3子問題的遞歸結(jié)構(gòu)由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用c[i][j]記錄序列和的最長公共子序列的長度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…，yj}。當(dāng)i=0或j=0時，空序列是Xi和Yj的最長公共子序列。故此時C[i][j]=0。其他情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下:0,j=0由于在所考慮的子問題空間中，總共有e(mn)個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。c[I-1][j-1]+1l,jmax{c[I][j-1],c[l-1][j]}l,jyj0;x。yjc[I-1][j-1]+1l,jmax{c[I][j-1],c[l-1][j]}l,jyj0;x。yj?如果只需要計算最長公共子序列的長度，則算法的空間需求可大大減少。事實上，在計算c[i][j]時，只用到數(shù)組c的第i行和第i-1行。因此，用2行的數(shù)組空間就可以計算出最長公共子序列的長度。進(jìn)一步的分析還可將空間需求減至O(min(m,n))。4、結(jié)束語通過對動態(tài)規(guī)劃算