算法分析与设计实验报告二

学生姓名：庞 亮 系别：软件学院 专业与班号：软件工程0805 学号：U200818042

实验时间：第 三 周，星期三 ，晚上 实验房间号：软件学院五楼机房

[实验名称] 作业排程和最长共同子序列算法 [实验目的]

理解动态规划算法设计思想，利用动态规划算法设计方法解决作业排程和最 长共同子序列问题。

[实验条件]

硬件：计算机

软件：计算机程序语言开发平台，如C、C++、Java、Matlab。

学生：至少掌握一门计算机程序设计语言，如C、C++、Java、Matlab。

[实验内容及要求]

描述并实现动态规划的作业排程算法，并显示下图的排程结果。

描 述 并 实 现 最 长 共 同 子 序 列 动 态 规 划算法， 并显示S1= ACCGGTCGAGATGCAG，S2 = GTCGTTCGGAATGCAT 的最长共同子序列。

[实验原理]

1.

作业排程问题

对于生产的每一个环节，它不是从一生产线而来，就是从二生产线而来，而且拥有最优子问题的结构，因此可以列出这个问题的状态转移方程如下图所示。可见每个状态都与前一个状态的数值有关，于是可以由底至上一步一步求得结果。

2. 最长公共子序列问题

LCS问题有最优子结构：

设X=和Y=为两个序列，并设Z=

为XY的任意一个LCS。

1） 如果xm=yn，那么zk=xm=yn而且Zk-1是Xm-1和Yn-1的一个LCS； 2） 如果xm!=yn,那么zk!=xm蕴含Z是Xm-1和Y的一个LCS； 3） 如果xm!=yn,那么zk!=yn蕴含Z是X和Yn-1的一个LCS. 由此得出这个问题的状态转移方程为：

[算法具体代码] 1. 作业排程问题

// work_flow.cpp : 定义控制台应用程序的入口点。 //

#include \"stdafx.h\"

int x1,x2; int e1,e2; int a[2][100]; int t[2][100]; int f[2][100]; int path[2][101]; int n;

void init() { }

int execute() {

f[0][0]=e1+a[0][0]; f[1][0]=e2+a[1][0]; for(int i=1;iif((f[0][i-1]+a[0][i])<(f[1][i-1]+t[1][i-1]+a[0][i])) { } else { }

if((f[1][i-1]+a[1][i])<(f[0][i-1]+t[0][i-1]+a[1][i])) {

f[0][i]=f[1][i-1]+t[1][i-1]+a[0][i]; path[0][i]=2;

f[0][i]=f[0][i-1]+a[0][i]; path[0][i]=1;

FILE * fin=fopen(\"in.txt\",\"r\"); fscanf(fin,\"%d\",&n); fscanf(fin,\"%d%d\",&e1,&e2); fscanf(fin,\"%d%d\",&x1,&x2); for(int i=0;ifor(int i=0;ifor(int i=0;ifor(int i=0;ifclose(fin);

fscanf(fin,\"%d\",&t[1][i]); fscanf(fin,\"%d\",&t[0][i]); fscanf(fin,\"%d\",&a[1][i]); fscanf(fin,\"%d\",&a[0][i]);

}

}

}

f[1][i]=f[1][i-1]+a[1][i]; path[1][i]=2;

else { }

f[1][i]=f[0][i-1]+t[0][i-1]+a[1][i]; path[1][i]=1;

if(f[0][n-1]+x1path[n][n]=2; return f[1][n-1]+x2; path[n][n]=1; return f[0][n-1]+x1;

int printpath(int a,int b) { }

int _tmain(int argc, _TCHAR* argv[]) { }

init();

printf(\"%d\\n\",execute()); printpath(path[n][n]-1,n-1); getchar(); return 0; if(b==0) { }

printpath(path[a][b]-1,b-1); printf(\"%d %d\\n\",a+1,b+1);

printf(\"%d %d\\n\",a+1,b+1); return 0;

2. 最长共同子序列问题

// LCS.cpp : 定义控制台应用程序的入口点。 //

#include \"stdafx.h\" #include \"string.h\"

char s1[100]; char s2[100]; int lcs[100][100]; int path[100][100]; int p,q;

void init() { }

void findLCS() {

lcs[0][0]=0;

for(int i=1;i<=strlen(s1);i++) { }

for(int i=1;i<=strlen(s2);i++) { }

for(int i=1;i<=strlen(s1);i++) {

for(int j=1;j<=strlen(s2);j++) {

if(s1[i-1]==s2[j-1]) { } else {

if(lcs[i-1][j]>lcs[i][j-1]) {

lcs[i][j]=lcs[i-1][j-1]+1; path[i][j]=2;

lcs[0][i]=0; lcs[i][0]=0;

FILE * fin=fopen(\"in.txt\",\"r\"); fscanf(fin,\"%s\",s1); fscanf(fin,\"%s\",s2); fclose(fin);

}

}

}

}

}

lcs[i][j]=lcs[i-1][j]; path[i][j]=0;

else { }

lcs[i][j]=lcs[i][j-1]; path[i][j]=1;

int printString(int x,int y) { }

int _tmain(int argc, _TCHAR* argv[]) { }

init(); findLCS();

printString(strlen(s1),strlen(s2)); getchar(); return 0; if(x==0 || y==0) { }

if(path[x][y]==2) { }

else if(path[x][y]==0) { }

else if(path[x][y]==1) { }

printString(x,y-1); printString(x-1,y); printString(x-1,y-1); printf(\"%c\",s1[x-1]); return 0;

[思考题]

动态规划算法范式是什么？

动态规划算法的设计分为4个步骤： 1）描述最优解的结构。 2）递归定义最优解的值。

3）按自底向上的方式计算最优解的值。 4）由计算出的结果构造一个最优解。 利用动态规划算法设计方法解决矩阵链相乘问题？ 矩阵链相乘的问题状态转移方程如下：

[实验体会]

本次试验主要研究动态规划问题。了解了动态规划算法设计的基本方法，并利用这些方法，解决了若干最优解问题。可以发现动态规划就是自底向上的思想解决问题，以后的每个问题都是由若干子问题构成的。所以运用动态规划解决问题的关键就是找到最优子问题之间的关系，然后就是写出状态转移方程，通过一维或者二维数组实现动态规划的算法。