矩阵连乘

\(A_{n×p}\)和\(B_{p×m}\) 是两个矩阵,这两个矩阵进行相乘的乘法次数为n×p×m。那么考虑一共有N个矩阵进行连续乘法的时候,求最优的乘法次序,使得乘法的次数最少,前提是矩阵乘法满足结合律。

穷举法:所有乘法次序为(N-1)!种,代价太大。

贪心策略:容易观察,矩阵维度 n p p m 变为 n m ,如果p较大的会带来较大的乘法开销,所以我们希望在顺次确定第一步乘法是,贪心地优先消去最大的那个p。

如何确定该贪心策略是否是正确的,举个反例?

。上面是一个反例,这种贪心主要面对当一个最大维度周围是次大或者次次大维度时,造成一步的乘法次数剧增。因此这种贪心策略不满足最优条件。

逆向地思考问题,最优结构的乘法次序总有最后两个矩阵之间进行,可以这两个矩阵将原始矩阵序列划分为,两个子矩阵序列,那么这两个子矩阵序列的乘法序列也应该是最优的,否则与前提矛盾。因此这样思考,矩阵连乘存在最优子结构特性

具有最优子结构特性,那么就动态规划三步走。

最简单的方法,第一步:暴力搜索(通常是用递归来实现),遍历所有的可能,但是对于这个问题,最终的结果是各个步骤的累加,因此在暴力搜素中掺杂了回溯的思想。(自顶向下)

第二步,带有备忘录的暴力搜索,暴力搜索生成树中存在大量的重复子树,可以将已经计算的结果存下来,下次遇到直接取就可以了。 (自顶向下)

第三部,动态规划法(四个步骤) (自底向上)

  • 定义dp数组,这里用cost[i,j],表示矩阵i到矩阵j的最优的乘法次序的代价
  • 写出dp数组包含的最优子结构的递推关系
  • 确定问题的初始条件以及边界条件
  • 自底向上开始计算结果

发表评论

电子邮件地址不会被公开。 必填项已用*标注