算法设计与分析课程设计

成绩评定表学生姓名班级学号专业信息与计算科学课程设计题目矩阵连乘；批作业处理调度评语组长签字：成绩日期20年月日课程设计任务书学院理学院专业信息与计算科学学生姓名班级学号课程设计题目矩阵连乘；批作业处理调度实践教学要求与任务:要求：1．巩固和加深对基本算法的理解和运用，提高综合运用课程知识进行算法设计与分析的能力。2．培养学生自学参考书籍，查阅手册、和文献资料的能力。3．通过实际课程设计，掌握利用分治法或动态规划算法，回溯法或分支限界法等方法的算法的基本思想，并能运用这些方法设计算法并编写程序解决实际问题。4．了解与课程有关的知识，能正确解释和分析实验结果。任务：1.动态规划解决矩阵连乘问题；2.回溯法解决批作业处理调度问题；3.总结解决问题的方法与收获。工作计划与进度安排:第12周：查阅资料。掌握算法设计思想，进行算法设计。第13周：算法实现，调试程序并进行结果分析。撰写课程设计报告，验收与答辩。指导教师：201年月日专业负责人：201年月日学院教学副院长：201年月日沈阳理工大学算法设计与分析课程设计I摘要算法设计与分析，其实可以解释为一类优化问题，一般针对可以利用计算机解决的离散型问题的优化。主要目的就是为了解决某一问题而提出的各种不同的解决方案。本文通过计算机算法分析设计出解矩阵连乘的动态规划算法和设计出解批处理作业调度的回溯法算法，利用C++语言编写程序实现算法。动态规划算法是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。首先找出最优解的性质，并刻其结构特征，然后递归的定义最优值（写出动态规划方程）并且以自底向上的方式计算出最优值，最后根据计算最优值时得到的信息，构造一个最优解。回溯法算法是确定了解空间的组织结构后，回溯法就是从开始节点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始节点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的或节点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。换句话说，这个节点，这个结点不再是一个活结点。此时，应往回（回溯）移动至最近一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归的在解空间中搜索，直到找到所要求的解或解空间中以无活结点为止。即通过确定初始解和剪枝函数原则画出状态图进行搜索产生全部可行解。关键词：动态规划；矩阵连乘；回溯法；批处理作业调度；剪枝原则；C++沈阳理工大学算法设计与分析课程设计II目录一、课程设计目的..............................................................................................................1二、课程设计内容..............................................................................................................1三、概要设计.......................................................................................................................13.1动态规划—矩阵连乘...........................................................................................13.2回溯法—批处理作业调度.................................................................................2四、详细设计与实现..........................................................................................................34.1动态规划—矩阵连乘............................................................................................34.11问题描述.............................................................................................................34.12分析最优解的结构............................................................................................34.13建立递归关系.....................................................................................................34.14计算最优值..........................................................................................................44.15代码实现..............................................................................................................44.16运行结果.............................................................................................................74.2回溯法—批处理作业调度...................................................................................84.21问题描述.............................................................................................................84.22算法分析.............................................................................................................84.23代码实现.............................................................................................................94.24运行结果...........................................................................................................12总结.......................................................................................................................................14参考文献..............................................................................................................................15沈阳理工大学算法设计与分析课程设计1一、课程设计目的《计算机算法设计与分析》这门课程是一门实践性非常强的课程，要求我们能够将所学的算法应用到实际中，灵活解决实际问题。通过这次课程设计，能够培养我们独立思考、综合分析与动手的能力，并能加深对课堂所学理论和概念的理解，可以训练我们算法设计的思维和培养算法的分析能力。二、课程设计内容1、动态规划：设计出解矩阵连乘问题的动态规划算法2、回溯法：设计出解批处理作业调度的回溯法算法三、概要设计3.1动态规划—矩阵连乘动态规划的基本思想是将问题分解为若干个小问题，解子问题，然后从子问题得到原问题的解。设计动态规划法的步骤：（1）找出最优解的性质，并刻画其结构特征；（2）递归地定义最优值（写出动态规划方程）；（3）以自底向上的方式计算出最优值；（4）根据计算最优值时得到的信息，构造一个最优解。沈阳理工大学算法设计与分析课程设计23.2回溯法—批处理作业调度回溯法的基本思想是确定了解空间的组织结构后，回溯法就是从开始节点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始节点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的或节点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。换句话说，这个节点，这个结点不再是一个活结点。此时，应往回（回溯）移动至最近一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归的在解空间中搜索，直到找到所要求的解或解空间中以无活结点为止。用回溯法解决批处理作业调度的步骤：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数原则避免无效搜索。沈阳理工大学算法设计与分析课程设计3四、详细设计与实现4.1动态规划—矩阵连乘4.11问题描述给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。例如求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，则其相应的完全加括号形式为((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],1=i=j=n，所需的最少数乘次数为m[i][j]，则原问题的最优值为m[1][n]。当i=j时，A[i;j]=Ai，为单一矩阵，无需计算，因此m[i][i]=0。沈阳理工大学算法设计与分析课程设计4当ij时，可以利用最优子结构的性质来计算