设计性实验报告 课程名称： 《算法分析与设计》 实验题目： 矩阵连乘问题 组 长： 成 员 一： 成 员 二： 成 员 三： 系 别： 数学与计算机科学系 专业班级： 指导教师： 实验日期： - 1 - 一、实验目的和要求 实验目的 熟悉动态规划算法设计思想和设计步骤，掌握基本的程序设计方法，培养学生用计算机解决实际问题的能力。 实验要求 1、根据实验内容，认真编写源程序代码、上机调试程序，书写实验报告。 2、本实验项目考察学生对教材中核心知识的掌握程度和解决实际问题的能力。 3、实验项目可以采用集中与分散实验相结合的方式进行，学生利用平时实验课时间和课外时间进行实验，要求在学期末形成完整的项目程序设计报告。 二、实验内容提要 矩阵连乘问题 给定n 个矩阵{A1,A2,… ,An}， 其中，Ai 与Ai+1 是可乘的，i=1,2，…，n-1。考查这 n个矩阵的连乘积 A1,A2,… ,An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2 个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积 A 是完全加括号的，则 A 可表示为 2 个完全加括号的矩阵连乘积B 和C 的乘积并加括号，即 A=（BC）。 三、实验步骤 下面考虑矩阵连乘积的最优计算次序问题的动态规划方法。 （1）分析最优解的结构（最优子结构性质） 设计求解具体问题的动态规划算法的第一步是刻画该问题的最优解结构特征。对于矩阵乘积的最优计算次序问题也不例外。首先，为方便起见，降矩阵乘积 Ai Ai+1…Aj 简记为 A[i:j]。考查计算A[1：n]的最优计算次序。设这个计算次序在矩阵Ak 和Ak+1 之间将矩阵链断开，1<=k
