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

华中科技大学算法分析与设计实验报告学生姓名：庞亮系别：软件学院专业与班号：软件工程0805学号：U200818042实验时间：第三周，星期三，晚上实验房间号：软件学院五楼机房[实验名称]作业排程和最长共同子序列算法[实验目的]理解动态规划算法设计思想，利用动态规划算法设计方法解决作业排程和最长共同子序列问题。[实验条件]硬件：计算机软件：计算机程序语言开发平台，如C、C++、Java、Matlab。学生：至少掌握一门计算机程序设计语言，如C、C++、Java、Matlab。[实验内容及要求]�描述并实现动态规划的作业排程算法，并显示下图的排程结果。�描述并实现最长共同子序列动态规划算法，并显示S1=ACCGGTCGAGATGCAG，S2=GTCGTTCGGAATGCAT的最长共同子序列。[实验原理]1.作业排程问题对于生产的每一个环节，它不是从一生产线而来，就是从二生产线而来，而且拥有最优子问题的结构，因此可以列出这个问题的状态转移方程如下图所示。可见每个状态都与前一个状态的数值有关，于是可以由底至上一步一步求得结果。2.最长公共子序列问题LCS问题有最优子结构：设X=x1,x2,x3……,xm和Y=y1,y2,y3……,yn为两个序列，并设Z=z1,z2,z3……,zk为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:定义控制台应用程序的入口点。//#includestdafx.hintx1,x2;inte1,e2;inta[2][100];intt[2][100];intf[2][100];intpath[2][101];intn;voidinit(){FILE*fin=fopen(in.txt,r);fscanf(fin,%d,&n);fscanf(fin,%d%d,&e1,&e2);fscanf(fin,%d%d,&x1,&x2);for(inti=0;in;i++){fscanf(fin,%d,&a[0][i]);}for(inti=0;in;i++){fscanf(fin,%d,&a[1][i]);}for(inti=0;in-1;i++){fscanf(fin,%d,&t[0][i]);}for(inti=0;in-1;i++){fscanf(fin,%d,&t[1][i]);}fclose(fin);}intexecute(){f[0][0]=e1+a[0][0];f[1][0]=e2+a[1][0];for(inti=1;in;i++){if((f[0][i-1]+a[0][i])(f[1][i-1]+t[1][i-1]+a[0][i])){f[0][i]=f[0][i-1]+a[0][i];path[0][i]=1;}else{f[0][i]=f[1][i-1]+t[1][i-1]+a[0][i];path[0][i]=2;}if((f[1][i-1]+a[1][i])(f[0][i-1]+t[0][i-1]+a[1][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]+x1f[1][n-1]+x2){path[n][n]=1;returnf[0][n-1]+x1;}else{path[n][n]=2;returnf[1][n-1]+x2;}}intprintpath(inta,intb){if(b==0){printf(%d%d\n,a+1,b+1);return0;}printpath(path[a][b]-1,b-1);printf(%d%d\n,a+1,b+1);}int_tmain(intargc,_TCHAR*argv[]){init();printf(%d\n,execute());printpath(path[n][n]-1,n-1);getchar();return0;}2.最长共同子序列问题//LCS.cpp:定义控制台应用程序的入口点。//#includestdafx.h#includestring.hchars1[100];chars2[100];intlcs[100][100];intpath[100][100];intp,q;voidinit(){FILE*fin=fopen(in.txt,r);fscanf(fin,%s,s1);fscanf(fin,%s,s2);fclose(fin);}voidfindLCS(){lcs[0][0]=0;for(inti=1;i=strlen(s1);i++){lcs[i][0]=0;}for(inti=1;i=strlen(s2);i++){lcs[0][i]=0;}for(inti=1;i=strlen(s1);i++){for(intj=1;j=strlen(s2);j++){if(s1[i-1]==s2[j-1]){lcs[i][j]=lcs[i-1][j-1]+1;path[i][j]=2;}else{if(lcs[i-1][j]lcs[i][j-1]){lcs[i][j]=lcs[i-1][j];path[i][j]=0;}else{lcs[i][j]=lcs[i][j-1];path[i][j]=1;}}}}}intprintString(intx,inty){if(x==0||y==0){return0;}if(path[x][y]==2){printString(x-1,y-1);printf(%c,s1[x-1]);}elseif(path[x][y]==0){printString(x-1,y);}elseif(path[x][y]==1){printString(x,y-1);}}int_tmain(intargc,_TCHAR*argv[]){init();findLCS();printString(strlen(s1),strlen(s2));getchar();return0;}[思考题]�动态规划算法范式是什么？动态规划算法的设计分为4个步骤：1）描述最优解的结构。2）递归定义最优解的值。3）按自底向上的方式计算最优解的值。4）由计算出的结果构造一个最优解。�利用动态规划算法设计方法解决矩阵链相乘问题？矩阵链相乘的问题状态转移方程如下：[实验体会]本次试验主要研究动态规划问题。了解了动态规划算法设计的基本方法，并利用这些方法，解决了若干最优解问题。可以发现动态规划就是自底向上的思想解决问题，以后的每个问题都是由若干子问题构成的。所以运用动态规划解决问题的关键就是找到最优子问题之间的关系，然后就是写出状态转移方程，通过一维或者二维数组实现动态规划的算法。