算法分析與設(shè)計實驗報告二8頁

1、華中科技大學 算法分析與設(shè)計實驗報告學生姓名：龐 亮 系別：軟件學院 專業(yè)與班號：軟件工程0805學號：U200818042實驗時間：第 三 周，星期三 ，晚上 實驗房間號：軟件學院五樓機房實驗名稱 作業(yè)排程和最長共同子序列算法實驗目的理解動態(tài)規(guī)劃算法設(shè)計思想，利用動態(tài)規(guī)劃算法設(shè)計方法解決作業(yè)排程和最長共同子序列問題。實驗條件硬件：計算機軟件：計算機程序語言開發(fā)平臺，如C、C+、Java、Matlab。學生：至少掌握一門計算機程序設(shè)計語言，如C、C+、Java、Matlab。實驗內(nèi)容及要求 描述并實現(xiàn)動態(tài)規(guī)劃的作業(yè)排程算法，并顯示下圖的排程結(jié)果。 描 述 并 實 現(xiàn) 最 長 共 同 子 序 列

2、 動 態(tài) 規(guī) 劃算法， 并顯示S1=ACCGGTCGAGATGCAG，S2 = GTCGTTCGGAATGCAT 的最長共同子序列。實驗原理1. 作業(yè)排程問題對于生產(chǎn)的每一個環(huán)節(jié)，它不是從一生產(chǎn)線而來，就是從二生產(chǎn)線而來，而且擁有最優(yōu)子問題的結(jié)構(gòu)，因此可以列出這個問題的狀態(tài)轉(zhuǎn)移方程如下圖所示?？梢娒總€狀態(tài)都與前一個狀態(tài)的數(shù)值有關(guān)，于是可以由底至上一步一步求得結(jié)果。2. 最長公共子序列問題LCS問題有最優(yōu)子結(jié)構(gòu)：設(shè)X=和Y=為兩個序列，并設(shè)Z=為XY的任意一個LCS。1） 如果xm=yn，那么zk=xm=yn而且Zk-1是Xm-1和Yn-1的一個LCS；2） 如果xm!=yn,那么zk!=xm蘊

3、含Z是Xm-1和Y的一個LCS；3） 如果xm!=yn,那么zk!=yn蘊含Z是X和Yn-1的一個LCS.由此得出這個問題的狀態(tài)轉(zhuǎn)移方程為：算法具體代碼1. 作業(yè)排程問題/ work_flow.cpp : 定義控制臺應用程序的入口點。/#include stdafx.hint x1,x2;int e1,e2;int a2100;int t2100;int f2100;int path2101;int n;void init()FILE * fin=fopen(in.txt,r);fscanf(fin,%d,&n);fscanf(fin,%d%d,&e1,&e2);fscanf(fin,%d%d

4、,&x1,&x2);for(int i=0;in;i+)fscanf(fin,%d,&a0i);for(int i=0;in;i+)fscanf(fin,%d,&a1i);for(int i=0;in-1;i+)fscanf(fin,%d,&t0i);for(int i=0;in-1;i+)fscanf(fin,%d,&t1i);fclose(fin);int execute()f00=e1+a00;f10=e2+a10;for(int i=1;in;i+)if(f0i-1+a0i)(f1i-1+t1i-1+a0i)f0i=f0i-1+a0i;path0i=1;elsef0i=f1i-1+t1

5、i-1+a0i;path0i=2;if(f1i-1+a1i)(f0i-1+t0i-1+a1i)f1i=f1i-1+a1i;path1i=2;elsef1i=f0i-1+t0i-1+a1i;path1i=1;if(f0n-1+x1f1n-1+x2)pathnn=1;return f0n-1+x1;elsepathnn=2;return f1n-1+x2;int printpath(int a,int b)if(b=0)printf(%d %dn,a+1,b+1);return 0;printpath(pathab-1,b-1);printf(%d %dn,a+1,b+1);int _tmain(

6、int argc, _TCHAR* argv)init();printf(%dn,execute();printpath(pathnn-1,n-1);getchar();return 0;2. 最長共同子序列問題/ LCS.cpp : 定義控制臺應用程序的入口點。/#include stdafx.h#include string.hchar s1100;char s2100;int lcs100100;int path100100;int p,q;void init()FILE * fin=fopen(in.txt,r);fscanf(fin,%s,s1);fscanf(fin,%s,s2);

7、fclose(fin);void findLCS()lcs00=0;for(int i=1;i=strlen(s1);i+)lcsi0=0;for(int i=1;i=strlen(s2);i+)lcs0i=0;for(int i=1;i=strlen(s1);i+)for(int j=1;jlcsij-1)lcsij=lcsi-1j;pathij=0;elselcsij=lcsij-1;pathij=1;int printString(int x,int y)if(x=0 | y=0)return 0;if(pathxy=2)printString(x-1,y-1);printf(%c,s1

8、x-1);else if(pathxy=0)printString(x-1,y);else if(pathxy=1)printString(x,y-1);int _tmain(int argc, _TCHAR* argv)init();findLCS();printString(strlen(s1),strlen(s2);getchar();return 0;思考題 動態(tài)規(guī)劃算法范式是什么？動態(tài)規(guī)劃算法的設(shè)計分為4個步驟：1） 描述最優(yōu)解的結(jié)構(gòu)。2） 遞歸定義最優(yōu)解的值。3） 按自底向上的方式計算最優(yōu)解的值。4） 由計算出的結(jié)果構(gòu)造一個最優(yōu)解。 利用動態(tài)規(guī)劃算法設(shè)計方法解決矩陣鏈相乘問題？矩陣鏈相乘的問題狀態(tài)轉(zhuǎn)移方程如下：實驗體會本次試驗主要研究動態(tài)規(guī)劃問題。了解了動態(tài)規(guī)劃算法設(shè)計的