矩阵连乘问题

目录： 矩阵连乘问题： 1. 描 述 矩 阵 连 乘 问 题 2. 分 析 矩 阵 连 乘 问 题 以 及 对 递 归 式 的 推 导 （ 1） 直 接 递 归 思 路 （ 2） 备 忘 录 思 路 （ 3） 动 态 规 划 思 路 3. 伪 代 码 的 方 式 描 述 算 法 ： （ 1） 直 接 递 归 算 法 （ 2） 备 忘 录 算 法 （ 3） 动 态 规 划 算 法 4. 把 算 法 转 换 成 程 序 实 现 的 过 程 及 结 果 （ 1） 直 接 递 归 算 法 程 序 （ 2） 备 忘 录 算 法 程 序 （ 3） 动 态 规 划 算 法 程 序 1.描述矩阵连乘问题： 给定n 个矩阵{nAAA,2,1}，其中iA 和1iA是可乘的，i=1,2,…,n-1。考察这n 个矩阵的连乘积nAAA,2,1。由于矩阵乘法具有结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说连乘积已完全加括号，则可依次序反复调用2 个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A 是完全加括号的，则A 可表示为2 个完全加括号的矩阵连乘B 和C 的乘积并加括号，即A=（BC）。 矩阵A 和B 可乘的条件是矩阵A 的列数等于矩阵B 的行数。若A 是一个p×q 的矩阵，B 是一个q×r 的矩阵，那么 C=A×B 就是一个p×r 矩阵。它的计算是三重循环的，计算量是pqr。如果加括号后矩阵的量是不同的，所以我们的问题就是要讨论如何给连乘的矩阵加括号才能使矩阵的计算量最少。 穷举搜索法：对于n 个矩阵的连乘积，设有不同的计算次序P(n)。由于可以先在第 k个和第 k+1 个矩阵之间将原矩阵序列分为两个矩阵子序列，k=1,2,...,n-1；然后分别对这两个矩阵子序列完全加括号；最后对所得的结果加括号，得到原矩阵序列的一种完全加括号方式。由此可得 P(n)的递归式如下： 1 n=1 P（n）= 11)()(nkknPkP n>1 解此递归方程可得，P(n)=C(n-1),而 C(n)是一个指数增长的函数。因此穷举搜索法不是一个有效的算法。以下将用三种方法来解决矩阵连乘问题的最优加括号方式以及最优解。 2. 分析矩阵连乘问题以及对递归式的推导 将矩阵连乘积jiiAAA ,1,简记为A[i:j]。考察计算A[1:n]的最优计算次序。这个问题的一个关键特征是：计算A[1:n]的最优次序包含...