算法设计与分析课程设计

1、 成 绩 评 定 表学生姓名班级学号专 业信息与计算科学课程设计题目矩阵连乘；批作业处理调度评语组长签字：成绩日期 20 年 月 日课程设计任务书学 院理学院专 业信息与计算科学学生姓名班级学号课程设计题目矩阵连乘；批作业处理调度实践教学要求与任务:要求：1巩固和加深对基本算法的理解和运用，提高综合运用课程知识进行算法设计与分析的能力。2培养学生自学参考书籍，查阅手册、和文献资料的能力。3通过实际课程设计，掌握利用分治法或动态规划算法，回溯法或分支限界法等方法的算法的基本思想，并能运用这些方法设计算法并编写程序解决实际问题。4了解与课程有关的知识，能正确解释和分析实验结果。任务：1. 动态规划

2、解决矩阵连乘问题；2. 回溯法解决批作业处理调度问题；3. 总结解决问题的方法与收获。工作计划与进度安排:第12周：查阅资料。掌握算法设计思想，进行算法设计。第13周：算法实现，调试程序并进行结果分析。撰写课程设计报告，验收与答辩。指导教师： 201 年 月 日专业负责人：201 年 月 日学院教学副院长：201 年 月 日摘 要算法设计与分析，其实可以解释为一类优化问题，一般针对可以利用计算机解决的离散型问题的优化。主要目的就是为了解决某一问题而提出的各种不同的解决方案。本文通过计算机算法分析设计出解矩阵连乘的动态规划算法和设计出解批处理作业调度的回溯法算法，利用C+语言编写程序实现算法。

3、动态规划算法是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。首先找出最优解的性质，并刻其结构特征，然后递归的定义最优值（写出动态规划方程）并且以自底向上的方式计算出最优值，最后根据计算最优值时得到的信息，构造一个最优解。 回溯法算法是确定了解空间的组织结构后，回溯法就是从开始节点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始节点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的或节点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。换

4、句话说，这个节点，这个结点不再是一个活结点。此时，应往回（回溯）移动至最近一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归的在解空间中搜索，直到找到所要求的解或解空间中以无活结点为止。即通过确定初始解和剪枝函数原则画出状态图进行搜索产生全部可行解。关键词：动态规划；矩阵连乘；回溯法；批处理作业调度；剪枝原则； C+目录一、课程设计目的1二、课程设计内容1三、概要设计13.1 动态规划矩阵连乘13.2 回溯法批处理作业调度2四、详细设计与实现34.1动态规划矩阵连乘34.11 问题描述34.12分析最优解的结构34.13建立递归关系34.14计算最优值44.15代码实现

5、44.16 运行结果74.2回溯法批处理作业调度84.21 问题描述84.22 算法分析84.23 代码实现94.24 运行结果12总结14参考文献15一、课程设计目的计算机算法设计与分析这门课程是一门实践性非常强的课程，要求我们能够将所学的算法应用到实际中，灵活解决实际问题。通过这次课程设计，能够培养我们独立思考、综合分析与动手的能力，并能加深对课堂所学理论和概念的理解，可以训练我们算法设计的思维和培养算法的分析能力。二、课程设计内容1、动态规划：设计出解矩阵连乘问题的动态规划算法2、回溯法：设计出解批处理作业调度的回溯法算法三、概要设计3.1 动态规划矩阵连乘动态规划的基本思想是将问题分解

6、为若干个小问题，解子问题，然后从子问题得到原问题的解。设计动态规划法的步骤：（1）找出最优解的性质，并刻画其结构特征；（2）递归地定义最优值（写出动态规划方程）；（3）以自底向上的方式计算出最优值；（4）根据计算最优值时得到的信息，构造一个最优解。3.2 回溯法批处理作业调度回溯法的基本思想是确定了解空间的组织结构后，回溯法就是从开始节点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始节点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的或节点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩

7、展结点就成为死结点。换句话说，这个节点，这个结点不再是一个活结点。此时，应往回（回溯）移动至最近一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归的在解空间中搜索，直到找到所要求的解或解空间中以无活结点为止。 用回溯法解决批处理作业调度的步骤： （1）针对所给问题，定义问题的解空间； （2）确定易于搜索的解空间结构； （3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数原则避免无效搜索。四、详细设计与实现4.1动态规划矩阵连乘4.11 问题描述给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1,2 ,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次

8、序计算矩阵连乘积需要的数乘次数最少。例如求n个矩阵A1,A2，A3，A4.An相乘的最小数乘次数，当A1为10*100的矩阵，A2为100*5的矩阵，A3为5*50的矩阵，则方法（A1A2）A3）的数乘次数为10*100*5+10*5*50=7500，而方法（A1（A2A3）则为100*5*50+10*100*50=75000，两者相差10倍。4.12分析最优解的结构 设计求解具体问题的动态规划算法的第一步是刻画该问题的最优解的结构特征。我们将矩阵连乘积AiAi+1.Aj简记为A i : j 。考察计算A 1: n的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，1=kn，则

9、其相应的完全加括号形式为(A1.Ak)(Ak+1.An)。以此次序，总的计算量为A 1 : k 的计算量加上A k+1 : n 的计算量， 再加上A 1 : k 和A k+1 : n 相称的计算量。 这个问题的关键特征是：计算A 1 :n 的最优次序所包含的计算矩阵子链a 1 : k 和A k+1 : n 的次序也是最优的。因此，矩阵连乘积计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可以用动态规划算法求解的显著特征。 4.13建立递归关系 设计动态规划算法的第二步就是递归地定义最优值。对于矩阵连乘积的最有计算次序问题，设计算A i : j

10、 , 1=i=j=n，所需的最少数乘次数为m i j ，则原问题的最优值为m 1 n。 当i=j时，A i ; j =Ai，为单一矩阵，无需计算，因此m i i =0。 当i j时，可以利用最优子结构的性质来计算m i j 。事实上，若计算A i : j 的最优次序在Ak和Ak+1之间断开，i=kj，则m i j =m i k +mk+1 j +Pi-1*Pk*Pj。其中Pi表示第i个矩阵的列数，也是第i-1个矩阵的行数，P0表示第一个矩阵的行数。由于在计算时并不知道断开点k的位置，所以k还未定。不过k的位置只有j-i个可能。从而m i j 可以递归地定义为 当i=j m i j = 0 当i

11、j m i j =min m i k +m k+1 j +Pi-1*Pk*Pj m i j 给出了最优值，即计算A i : j 所需的最少数乘次数。同时还确定了计算A i : j 的最优次序中的断开位置k，也就是说，对于这个k有 m i j =m i k +m k+1 j + Pi-1*Pk*Pj 若将对应于m i j 的断开位置k记为s i j ， 在计算最优值m i j 后，可以递归地有s i j 构造出相应的最优解。4.14计算最优值 根据计算m i j 的递归式，容易写一个递归算法计算m 1 n 。但是简单地递归将好费指数计算时间。在递归计算时，许多子问题被重复计算多次。这也是该问题可

12、以用动态规划算法求解的又一显著特征。4.15代码实现/矩阵连乘#include #define N 100int pN; /用以记录矩阵的行和列int sNN; /用以记录断开位置int mNN; /用以记录最少数乘次数int n; /矩阵数目int kuohao2N; /记录加括号的位置void init() int i; for(i=0;iN;+i) sii=0; kuohao0i=0; kuohao1i=0; void input() int i; printf(please putin the num of matrix:n); scanf(%d,&n); printf(please

13、putin the matrixs:n); for(i=0;i=n;+i) scanf(%d,&pi);void matrix() int i,j,k,t; int d; for(d=1;dn;+d) for(i=1;i=n-d;+i) j=i+d; mij=mi+1j+pi-1*pi*pj; sij=i; for(k=i+1;kj;+k) t=mik+mk+1j+pi-1*pk*pj; if(tmij) mij=t; sij=k; void output() printf(the least times of matrix is: ); printf(%dn,m1n); printf(the

14、 way of it is:n);void tranceback(int i,int j) if(i=j) return; tranceback(i,sij); tranceback(sij+1,j); kuohao0i+; kuohao1j+; kuohao1sij+; kuohao0sij+1+;void trance() int i,j; for(i=1;i=n;+i) for(j=1;jkuohao0i;+j) /j的循环比kuohao（括号）的个数少一，这是因为为了把每个单独矩阵外必然有的一个括号过滤掉即（An） printf(); printf(A%d,i); for(j=1;jn

15、时，算法搜索至叶子结点，得到一个新的作业调度方案。此时算法适时更新当前最优值和相应的当前最佳调度。当in时，当前扩展结点在i-1层，以深度优先方式，递归的对相应子树进行搜索，对不满足上界约束的结点，则剪去相应的子树。4.23 代码实现#include using namespace std;#define MAX 200int* x1;/作业Ji在机器1上的工作时间；int* x2;/作业Ji在机器2上的工作时间；int number=0;/作业的数目；int* xOrder;/作业顺序；int* bestOrder;/最优的作业顺序；int bestValue=MAX;/最优的时间；int

16、xValue=0;/当前完成用的时间；int f1=0;/机器1完成的处理时间；int* f2;/第i阶段机器2完成的时间；void BackTrace(int k) if (knumber) for (int i=1;i=number;i+) bestOrderi=xOrderi; bestValue=xValue; else for (int i=k;if1?f2k-1:f1)+x2xOrderi; xValue+=f2k; swap(xOrderi,xOrderk); if (xValuebestValue) BackTrace(k+1); swap(xOrderi,xOrderk);

17、xValue-=f2k; f1-=x1xOrderi; int main() coutnumber; x1=new intnumber+1; x2=new intnumber+1; xOrder=new intnumber+1; bestOrder=new intnumber+1; f2=new intnumber+1; x10=0; x20=0; xOrder0=0; bestOrder0=0; f20=0; cout请输入每个作业在机器1上所用的时间：endl; for (int i=1;i=number;i+) cout第ix1i; cout请输入每个作业在机器2上所用的时间：endl;

18、 for (i=1;i=number;i+) cout第ix2i; for (i=1;i=number;i+) xOrderi=i; BackTrace(1); cout最节省的时间为：bestValue; coutendl; cout对应的方案为：; for (i=1;i=number;i+) coutbestOrderi ; return 0;4.24 运行结果总结通过本次课程设计，使我对矩阵连乘、批处理作业调度设计的基本过程的设计方法、步骤、思路、有了一定的了解与认识。在这次课程设计过程中，我认识到只是知道课本上的理论知识是远远不够的，我们还必须要深切的理解每个算法的思想，并且能够利用C+语言去编写相关的代码，经过不断的修改、调试，使之能解决相应的问题，最终能运用到实际案例中去。 对我们来说，实际能力的培养至关重要，而这种实际能力的培养单靠课堂教学是远远不够的