资源描述：
《华北电力大学 算法实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、......华北电力大学实验报告
2、实验名称：算法设计与分析实验课程名称：算法设计与程序分析
3、专业班级：学生：学号：2011成绩：指导教师：军实验日期：2013.11...专业........实验一矩阵连乘（动态规划）一、实验目的：掌握基本的动态规划思想，学习解决格路问题的基本思想。二、实验容：给定n个矩阵{A1,A2,…,An}，其中Ai与Ai+1是可乘的，i=1,2,…,n-1。要算出这n个矩阵的连乘积A1A2…An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号
4、的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。例如，矩阵连乘积A1A2A3A4有5种不同的完全加括号的方式：（A1（A2（A3A4））），（A1（（A2A3）A4）），（（A1A2）（A3A4）），（（A1（A2A3））A4），（（（A1A2
5、）A3）A4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A是一个p×q矩阵，B是一个q×r矩阵，则计算其乘积C=AB的标准算法中，需要进行pqr次数乘。为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵{A1,A2,A3}连乘的情况。设这三个矩阵的维数分别为10×100，100×5，5×50。加括号的方式只有两种：（（A1A2）A3），（A1（A2A...专业........3）），第一种方式需要的数乘次数为10×100×5＋10×5×50＝7
6、500，第二种方式需要的数乘次数为100×5×50＋10×100×50＝75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n个矩阵{A1,A2,…,An}（其中矩阵Ai的维数为pi-1×pi，i＝1,2,…,n），如何确定计算矩阵连乘积A1A2…An的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。穷举搜索法的计算量太大，它不是一个有效的算
7、法，本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。三、基本思想动态规划算法的基本思想是将待求解问题分成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，动态规划法经分解得到的子问题往往不是相互独立的，前一子问题的解为后一子问题的解提供有用的信息，可以用一个表来记录所有已解决的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。本实验的算法思路是：...专业........1、计算最优值算法MatrixChain()：建立两表（即程序中的**m和*
8、*s，利用二维指针存放），一表存储矩阵相乘的最小运算量，主对角线上的值为0，依次求2个矩阵、3个矩阵…、直到n个矩阵相乘的最小运算量，其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得，最后一次求得的值即为n个矩阵相乘的最小运算量；另一表存储最优断开位置。2、输出矩阵结合方式算法Traceback()：矩阵结合即是给矩阵加括号，打印出矩阵结合方式，由递归过程Traceback()完成。分三种情况：（1）只有一个矩阵，则只需打印出A1；（2）有两个矩阵，则需打印出（A1A2）；（3）对于矩阵数
9、目大于2，则应该调用递归过程Traceback()两次，构造出最优加括号方式。四、实验代码#includeusingnamespacestd;constintMAX=100;//p用来记录矩阵的行列，main函数中有说明//m[i][j]用来记录第i个矩阵至第j个矩阵的最优解//s[][]用来记录从哪里断开的才可得到该最优解intp[MAX+1],m[MAX][MAX],s[MAX][MAX];intn;//矩阵个数intmatrixChain(){for(inti=0;i<=n;i++).
10、..专业........m[i][i]=0;for(intr=2;r<=n;r++)//对角线循环for(inti=0;i<=n-r;i++)//行循环{intj=r+i-1;//列的控制//找m[i][j]的最小值，先初始化一下，令k=im[i][j]=m[i+1][j]+p[i+1]*p[i]*p[j+1];s[i][j]=i;//k从i+1到j-1循环找m[i][j]的最小值fo
