南京郵電大學(xué)算法設(shè)計(jì)實(shí)驗(yàn)報(bào)告-動(dòng)態(tài)規(guī)劃法

4/4南京郵電大學(xué)算法設(shè)計(jì)實(shí)驗(yàn)報(bào)告——?jiǎng)討B(tài)規(guī)劃法

實(shí)驗(yàn)報(bào)告

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

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

實(shí)驗(yàn)名稱動(dòng)態(tài)規(guī)劃法

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

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

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

實(shí)驗(yàn)報(bào)告

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

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

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

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

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

硬件：計(jì)算機(jī)

軟件：VisualC++

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

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

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

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

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)一步分解為求解兩個(gè)（前綴）子字符序列Xm-1和Yn-1的最長公共子序列問題；如果xm≠yn，則原問題轉(zhuǎn)化為求解兩個(gè)子問題，即找出Xm-1和Y的最長公共子序列與找出X和Yn-1的最長公共子序列，取兩者中較長者作為X和Y的最長公共子序列。

由此可見，兩個(gè)序列的最長公共子序列包含了這兩個(gè)序列的前綴的最長公共子序列，具有最優(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ì)，如果采用遞歸算法實(shí)現(xiàn)，會(huì)得到一個(gè)指數(shù)時(shí)間算法，因此需要采用動(dòng)態(tài)規(guī)劃法自底向上求解，并保存子問題的解，這樣可以避免重復(fù)計(jì)算子問題，在多項(xiàng)式時(shí)間內(nèi)完成計(jì)算。

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

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

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

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

#include

#include

usingnamespacestd;

#definemaxlength11

classLCS

{

public:

LCS(intnx,intny,char*x,char*y)//對(duì)數(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)解？請(qǐng)編寫一個(gè)類似的CLCS算法實(shí)現(xiàn)：不借助二維數(shù)組s在O(m+n)的時(shí)間內(nèi)構(gòu)造最長公共子序列的功能。（提示：此時(shí)可在當(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、如果只需計(jì)算最長公共子序列的長度，而無須構(gòu)造最優(yōu)解，則如何改進(jìn)原有程序可以使得算法的空間需求大大減少？請(qǐng)改寫原程序，使算法的空間復(fù)雜度減少為O(min{m,n})。（提示：計(jì)算c[i][j]僅用到第i行和第i-1行元素，因此，只需兩行元素空間就可以計(jì)算最長公共子序列的長度，并且選用序列長度較短的一個(gè)作為y序列，可以縮短每行元素的個(gè)數(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]的時(shí)候，分別沿著c[i-1][j]