南京郵電大學(xué)算法設(shè)計實驗報告-動態(tài)規(guī)劃法

4/4南京郵電大學(xué)算法設(shè)計實驗報告——動態(tài)規(guī)劃法

實驗報告

（2009/2010學(xué)年第一學(xué)期）

課程名稱算法分析與設(shè)計A

實驗名稱動態(tài)規(guī)劃法

實驗時間2009年11月20日指導(dǎo)單位計算機(jī)學(xué)院軟件工程系

指導(dǎo)教師張怡婷

學(xué)生姓名丁力琪班級學(xué)號B07030907學(xué)院(系)計算機(jī)學(xué)院專業(yè)軟件工程

實驗報告

實驗名稱動態(tài)規(guī)劃法指導(dǎo)教師張怡婷實驗類型驗證實驗學(xué)時2×2實驗時間2009-11-20一、實驗?zāi)康暮腿蝿?wù)

目的：加深對動態(tài)規(guī)劃法的算法原理及實現(xiàn)過程的理解，學(xué)習(xí)用動態(tài)規(guī)劃法解決實際應(yīng)用中的最長公共子序列問題。

任務(wù)：用動態(tài)規(guī)劃法實現(xiàn)求兩序列的最長公共子序列，其比較結(jié)果可用于基因比較、文章比較等多個領(lǐng)域。

要求：掌握動態(tài)規(guī)劃法的思想，及動態(tài)規(guī)劃法在實際中的應(yīng)用；分析最長公共子序列的問題特征，選擇算法策略并設(shè)計具體算法，編程實現(xiàn)兩輸入序列的比較，并輸出它們的最長公共子序列。

二、實驗環(huán)境(實驗設(shè)備)

硬件：計算機(jī)

軟件：VisualC++

三、實驗原理及內(nèi)容（包括操作過程、結(jié)果分析等）

1、最長公共子序列（LCS）問題是：給定兩個字符序列X={x1,x2,……,xm}和Y={y1,y2,……,yn}，要求找出X和Y的一個最長公共子序列。

例如：X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a}。它們的最長公共子序列LSC={b,c,d,a}。

通過“窮舉法”列出所有X的所有子序列，檢查其是否為Y的子序列并記錄最長公共子序列并記錄最長公共子序列的長度這種方法，求解時間為指數(shù)級別的，因此不可取。

2、分析LCS問題特征可知，如果Z={z1,z2,……，zk}為它們的最長公共子序列，則它們一定具有以下性質(zhì)：

（1）若xm=yn，則zk=xm=yn，且Zk-1是Xm-1和Yn-1的最長公共子序列；

（2）若xm≠yn且xm≠zk，則Z是Xm-1和Y的最長公共子序列；

（3）若xm≠yn且zk≠yn，則Z是X和Y的最長公共子序列。

這樣就將求X和Y的最長公共子序列問題，分解為求解較小規(guī)模的問題：

若xm=ym，則進(jìn)一步分解為求解兩個（前綴）子字符序列Xm-1和Yn-1的最長公共子序列問題；如果xm≠yn，則原問題轉(zhuǎn)化為求解兩個子問題，即找出Xm-1和Y的最長公共子序列與找出X和Yn-1的最長公共子序列，取兩者中較長者作為X和Y的最長公共子序列。

由此可見，兩個序列的最長公共子序列包含了這兩個序列的前綴的最長公共子序列，具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

3、令c[i][j]保存字符序列Xi={x1,x2,……,xi}和Yj={y1,y2,……,yj}的最長公共子序列的長度，由上述分析可得如下遞推式：

0i=0或j=0

c[i][j]=c[i-1][j-1]+1i,j>0且xi=yj

max{c[i][j-1],c[i-1][j]}i,j>0且xi≠yj

由此可見，最長公共子序列的求解具有重疊子問題性質(zhì)，如果采用遞歸算法實現(xiàn)，會得到一個指數(shù)時間算法，因此需要采用動態(tài)規(guī)劃法自底向上求解，并保存子問題的解，這樣可以避免重復(fù)計算子問題，在多項式時間內(nèi)完成計算。

4、為了能由最優(yōu)解值進(jìn)一步得到最優(yōu)解（即最長公共子序列），還需要一個二維數(shù)組s[][]，數(shù)組中的元素s[i][j]記錄c[i][j]的值是由三個子問題c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一個計算得到，從而可以得到最優(yōu)解的當(dāng)前解分量（即最長公共子序列中的當(dāng)前字符），最終構(gòu)造出最長公共子序列自身。

5、編程定義LCS類，計算最長公共子序列的長度，并給出最長公共子序列：

（注意：C語言中數(shù)組下標(biāo)由0開始，而實際數(shù)據(jù)在一維數(shù)組a、b和二維數(shù)組是c、s中存放卻是從小標(biāo)為1處開始。）

類中數(shù)據(jù)成員主要有二維數(shù)組c和s用于動態(tài)規(guī)劃法求解過程中保存子問題的求解結(jié)果，一維數(shù)組a和b用于存放來兩個字符序列，m和n為兩個字符序列中實際字符的個數(shù)。這些數(shù)據(jù)成員均應(yīng)在LCS類的構(gòu)造函數(shù)中進(jìn)行初始化：

#include

#include

usingnamespacestd;

#definemaxlength11

classLCS

{

public:

LCS(intnx,intny,char*x,char*y)//對數(shù)據(jù)成員m、n、a、b、c、s初始化

{

m=nx;

n=ny;

a=newchar[m+2];

b=newchar[n+2];

memset(a,0,m+2);

memset(b,0,n+2);

//將x和y中的字符寫入一維數(shù)組a和b中

for(inti=0;i=LCSLength(i,j-1))

{

c[i][j]=LCSLength(i-1,j);

s[i][j]=2;

}

else

{

c[i][j]=LCSLength(i,j-1);

s[i][j]=3;

}

}

returnc[i][j];

}

2、若省去原程序中的二維數(shù)組s，是否還能求的最長公共子序列問題的最優(yōu)解？請編寫一個類似的CLCS算法實現(xiàn)：不借助二維數(shù)組s在O(m+n)的時間內(nèi)構(gòu)造最長公共子序列的功能。（提示：此時可在當(dāng)前c[i][j]處比較a[i]和b[j]。

如果相等，則調(diào)用CLCS(i-1,j-1)，輸出a[i]（或b[j]）。

如果不相等，則比較c[i-1][j]和c[i][j-1]。若c[i-1][j]≥c[i][j-1],則遞歸調(diào)用CLCS（i-1，j）；

否則，遞歸調(diào)用CLCS(i,j-1)。）

voidLCS::CLCS(inti,intj)const

{

if(i==0||j==0)return;

if(a[i]==b[j])

{

CLCS(i-1,fj-1);

cout=c[i][j-1])CLCS(i-1,j);

elseCLCS(i,j-1);

}

}

3、如果只需計算最長公共子序列的長度，而無須構(gòu)造最優(yōu)解，則如何改進(jìn)原有程序可以使得算法的空間需求大大減少？請改寫原程序，使算法的空間復(fù)雜度減少為O(min{m,n})。（提示：計算c[i][j]僅用到第i行和第i-1行元素，因此，只需兩行元素空間就可以計算最長公共子序列的長度，并且選用序列長度較短的一個作為y序列，可以縮短每行元素的個數(shù)，從而進(jìn)一步減少空間復(fù)雜度。）

#includen)

{

l=m;

s=n;

}

else{

char*t;

t=x;

x=y;

y=t;

s=m;

l=n;

}

c1=newint[s+1];

c2=newint[s+1];

for(inti=0;i>x;

nx=strlen(x);

cout>y;

ny=strlen(y);

LCSlcs(nx,ny,x,y);

cout=c[i][j-1])……語句中沒有區(qū)分c[i-1][j]>c[i][j-1]和c[i-1][j]=c[i][j-1]這兩種不同的情況。因此要找出所有LCS，就必須在a[i]!=b[j]且c[i-1][j]==c[i][j-1]的時候，分別沿著c[i-1][j]