矩阵链相乘(动态规划法)

矩阵链乘法是耳熟能详的问题了,有很多矩阵,排列成矩阵链,矩阵链的要求是相邻的两个是可以相乘的,可以相乘是有条件的,两个矩阵能够相乘的条件就是行、列之间是有关系的,两个矩阵如果能够相乘,就是前面矩阵的列号和后面矩阵的行号是一致的。 如何确定矩阵的乘法顺序,使得元素相乘的总次数最少。

一、问题描述

1、问题

设A1 _,A2 , … ,An为矩阵序列, Ai为 Pi-1 X Pi 阶矩阵,i = 1, 2, … , n. 试确定矩阵的乘法顺序,使得元素相乘的总次数最少。

2、输入:向量

矩阵链相乘(动态规划法)
矩阵链相乘(动态规划法)

3、输出:矩阵链乘法加括号的位置.

二、矩阵相乘基本运算次数

矩阵A: i 行 j 列,B: j 行 k 列,以元素相乘作基本运算,计算 AB的工作量
matrix-001

cts = at1 b1s + at2 b2s + … + atj bjs

AB: i 行 k列,计算每个元素需要做 j 次乘法, 总计乘法次数 为 i j k

Notes:两个矩阵相乘的工作量就是,A、B相乘得到C矩阵,C矩阵里面有i行k列个元素,每一个元素的计算是由列数j的地方的行数来决定的,j次的乘法,这里面有多少次元素j次元素相乘,每一个元素是由j次乘法决定的,一共有i 行 k列(ik)个元素,(ik)是它的总个数,每个元素个数要进行k次乘法,所以总计乘法次数 为 i j k

三、实例说明

1、实例

现在有三个矩阵,A1,A2,A3
矩阵链相乘(动态规划法)

最终乘完后是10 X 50的矩阵,这个时候做相乘有两种乘法顺序

(1)比如A1,A2先乘,乘法次数 为 i j k,需要10 X 100 X 50次乘法,(A1 A2)乘完之后的矩阵大小是10 X 5的矩阵,这个矩阵再和A3相乘,它的乘法次数 为10 X 5 X 50,运算次数是7500次

(2)另外一种运算,先让A2,A3先乘,需要100 X 5 X 50次乘法,乘完之后的矩阵大小是100 X 50的矩阵,这个矩阵再和A1相乘,它的乘法次数 为10 X 100 X 50,运算次数是75000次
矩阵链相乘(动态规划法)

这两种乘法的次数明显差别非常大,第一种次序计算次数最少,次序的不同计算的次数也会不同,这个时候问题就变成了加括号的问题

2、蛮力算法

现在有n个矩阵,决定先乘的次序,量级是非常高的
加n个括号

3、动态规划算法

矩阵链里面的子问题就是将原问题划分成两段的时候,不管怎样分割,最后一次分割的位置一旦确定以后,原问题就变成了两段。

一个是在最后一次分割最后一次加括号的位置一定会分成左边和右边,左边这一段就是新的矩阵链相乘的问题,在这个里面依然存在要去找一个最好的括号化的方法(也就是往里面加括号),加入的括号能够得到最少的乘法的次数,然后原问题整个矩阵链从左边界到右边界分割成两段以后,原问题加括号的方法,在子问题里面加括号的方法加进去之后的乘法的次数,其实是一样的。

原问题的最优的加括号的方法一定也是也是子问题的最优的加括号的方法,否则我们就可以用剪切粘贴的方法来构成一个新的最优解,最优子结构就不满足了。

  • 子问题划分
    Ai…j:矩阵链 Ai Ai+1 … Aj,边界i, j
    输入向量: < Pi-1, PI, … , Pj>
    其最好划分的运算次数: m[i, j]
  • 子问题的依赖关系
    最优划分最后一次相乘发生在矩阵k 的位置,即
    A~i …j~ = Ai…k Ak+1…j

Ai…j最优运算次数依赖于 Ai…k与 Ak+1…j 的最优运算次数

四、总结

动态规划算法设计要素 :

  • 多阶段决策过程,每步处理一个子问题,界定子问题的边界
  • 列出优化函数的递推方程及初值
  • 问题要满足优化原则或最优子结构性质,即:一个最优决策序列的任何子序列本身一定是相对于子序列的初始和结束状态的最优决策序列

文章出处登录后可见!

已经登录?立即刷新

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
上一篇 2022年6月1日 上午11:57
下一篇 2022年6月1日 下午12:00

相关推荐

本站注重文章个人版权,不会主动收集付费或者带有商业版权的文章,如果出现侵权情况只可能是作者后期更改了版权声明,如果出现这种情况请主动联系我们,我们看到会在第一时间删除!本站专注于人工智能高质量优质文章收集,方便各位学者快速找到学习资源,本站收集的文章都会附上文章出处,如果不愿意分享到本平台,我们会第一时间删除!