《04实验四 动态规划 矩阵连乘问题》由会员分享，可在线阅读，更多相关《04实验四 动态规划 矩阵连乘问题（2页珍藏版）》请在金锄头文库上搜索。
1、实验四实验四 动态规划动态规划 矩阵连乘问题矩阵连乘问题一、实验目的一、实验目的1、掌握动态规划算法的基本思想。2、掌握设计动态规划算法的基本步骤。3、掌握用动态规划算法求矩阵连乘问题。二、实验环境二、实验环境Windows XP 以上版本的操作系统，Visual Studio 2010 编程环境。三、实验内容三、实验内容【问题】：矩阵链乘问题：给定 n 个矩阵A1,A2,.,An ，其中 Ai 与 Ai+1 是 可乘的，i=1，2.，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序 计算矩阵连乘积需要的数乘次数最少。1、按设计动态规划算法的步骤解题。 (1)找出最优解的性质，并刻划其结
2、构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息，构造最优解(由子结构的最优解得到原先大问 题的最优解)。2、求算法的时间复杂性，和空间复杂性3、体会动态规划和穷举法在解决该问题中的本质差异。（1）问题的描述 给定 n 个矩阵A1,A2,An，其中 Ai 与 Ai+1 是可乘的，i=1,2,n-1。要算出这 n 个矩阵的连乘积 A1A2An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可 以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵 连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反 复调
3、用 2 个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递 归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积 A 是完全加括 号的，则 A 可表示为 2 个完全加括号的矩阵连乘积 B 和 C 的乘积并加括号，即 A=(BC)。 例如，矩阵连乘积 A1A2A3A4 有 5 种不同的完全加括号的方式： （A1（A2（A3A4），（A1（A2A3）A4），（A1A2）（A3A4）， （A1（A2A3）A4），（A1A2）A3）A4）。每一种完全加括号的方式对 应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若 A 是一个pq 矩阵，B 是一个 qr 矩阵，则计
4、算其乘积 C=AB 的标准算法中，需要进行pqr 次数乘。 为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先 考察 3 个矩阵A1,A2,A3连乘的情况。设这三个矩阵的维数分别为10100，1005，550。加括号的方式只有两种：（A1A2）A3），（A1（A2A3），第一种方式需要的数乘次数为101005105507500，第二种方式需要的数乘次数为100550101005075000。第二种加括号方式的计算量时第一种方式计算量的 10 倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量 有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相 继
5、n 个矩阵A1,A2,An（其中矩阵 Ai 的维数为 pi-1pi，i1,2,n），如何确 定计算矩阵连乘积 A1A2An 的计算次序（完全加括号方式），使得依此次序计 算矩阵连乘积需要的数乘次数最少。 穷举搜索法的计算量太大，它不是一个有效的算法，本实验采用动态规划算法解矩 阵连乘积的最优计算次序问题。（2）算法设计思想 动态规划算法的基本思想是将待求解问题分成若干个子问题，先求解子问题，然后 从这些子问题的解得到原问题的解。与分治法不同的是，动态规划法经分解得到的 子问题往往不是相互独立的，前一子问题的解为后一子问题的解提供有用的信息， 可以用一个表来记录所有已解决的子问题的答案，不管该子问题以后是否被用到， 只要它被计算过，就将其结果填入表中。
