矩阵链乘法的例子

示例:给定序列{4、10、3、12、20和7}。矩阵的大小为4 x 10、10 x 3、3 x 12、12 x 20、20 x7。我们需要计算M [i, j], 0≤i, j≤5。我们知道M [i, i对于所有i, = 0。

矩阵链乘法的例子

文章图片
让我们继续远离对角线。我们为2个矩阵的乘积计算最佳解。
矩阵链乘法的例子

文章图片
这里P0到P5是位置, M1到M5是大小矩阵(pi到pi-1)
在顺序的基础上, 我们做一个公式
矩阵链乘法的例子

文章图片
【矩阵链乘法的例子】在动态规划中, 所有方法的初始化均由’ 0’ 完成, 因此我们以’ 0’ 对其进行初始化, 它将按对角线排序。
我们必须对所有组合进行分类, 但要考虑最小输出组合。
Calculation of Product of 2 matrices: 1. m (1, 2) = m1x m2 = 4 x 10 x10 x 3 = 4 x 10 x 3 = 1202. m (2, 3) = m2 x m3 = 10 x 3x3 x 12 = 10 x 3 x 12 = 3603. m (3, 4) = m3 x m4 = 3 x 12x12 x 20 = 3 x 12 x 20 = 7204. m (4, 5) = m4 x m5 = 12 x 20x20 x 7 = 12 x 20 x 7 = 1680

矩阵链乘法的例子

文章图片
  • 我们用等于0的i, j值初始化对角线元素。
  • 整理完第二条对角线后, 我们得到与之对应的所有值
现在, 第三对角线将以相同的方式求解。
现在是3个矩阵的乘积:
M [1, 3] = M1 M2 M3

  1. 有两种情况可以解决此乘法:(M1 x M2)+ M3, M1 +(M2x M3)
  2. 解决这两种情况后, 我们选择存在最小输出的情况。
矩阵链乘法的例子

文章图片
M [1, 3] = 264
由于在两种情况下比较两个输出264的最小值, 因此我们在表中插入264, 并且(M1 x M2)+ M3会选择此组合进行输出。
M [2, 4] = M2 M3 M4

  1. 有两种情况可以解决此乘法:(M2x M3)+ M4, M2 +(M3 x M4)
  2. 解决这两种情况后, 我们选择存在最小输出的情况。
矩阵链乘法的例子

文章图片
M [2, 4] = 1320
由于在这两种情况下, 比较两个输出1320的最小值都是最小的, 因此我们将1320插入表中, 并选择M2 +(M3 x M4)进行输出组合。
M [3, 5] = M3M4M5

  1. 有两种情况可以解决此乘法:(M3 x M4)+ M5, M3 +(M4xM5)
  2. 解决这两种情况后, 我们选择存在最小输出的情况。
矩阵链乘法的例子

文章图片
M [3, 5] = 1140

由于在这两种情况下, 比较两个输出1140的最小值都是最小的, 因此我们在表中插入1140, 并且(M3 x M4)+ M5选择此组合进行输出。
矩阵链乘法的例子

文章图片
现在有4个矩阵的乘积:
M [1, 4] = M1M2 M3 M4

在三种情况下, 我们可以解决此乘法:
  1. (M1 x M2 x M3)M4
  2. M1 x(M2 x M3 x M4)
  3. (M1 xM2)x(M3 x M4)
解决这些情况后, 我们选择存在最小输出的情况
矩阵链乘法的例子

文章图片
M [1, 4] = 1080
在比较不同情况下的输出时, “ 1080”是最小输出, 因此我们在表中插入1080, 并在输出制作中取出(M1 xM2)x(M3 x M4)组合,
M [2, 5] = M2 M3 M4 M5

在三种情况下, 我们可以解决此乘法:
  1. (M2 x M3 x M4)x M5
  2. M2 x(M3 x M4 x M5)
  3. (M2 x M3)x(M4 x M5)
解决这些情况后, 我们选择存在最小输出的情况
矩阵链乘法的例子

文章图片
M [2, 5] = 1350

比较不同情况的输出时, “ 1350”是最小输出, 因此我们在表中插入1350, 并在输出制作中取出M2 x(M3 x M4 xM5)组合。
矩阵链乘法的例子

文章图片
现在有5个矩阵的乘积:
M [1, 5] = M1M2 M3 M4 M5

有五种情况可以解决此乘法:
  1. (M1 x M2 xM3 x M4)x M5
  2. M1 x(M2 xM3 x M4 xM5)
  3. (M1 x M2 xM3)x M4 xM5
  4. M1 x M2x(M3 x M4 xM5)
解决这些情况后, 我们选择存在最小输出的情况
矩阵链乘法的例子

文章图片
M [1, 5] = 1344

在比较不同情况下的输出时, “ 1344”是最小输出, 因此我们在表中插入1344, 并在输出制作中取出M1 x M2 x(M3 x M4 x M5)组合。
最终输出为:
矩阵链乘法的例子

文章图片
步骤3:计算最佳成本:让我们假设矩阵i的维数为pi-1x pi, 其中i = 1、2、3 … n。输入是一个序列(p0, p1, … pn), 其中长度[p] = n + 1。该过程使用辅助表m [1..n, 1 … .. n]来存储m [i, j]花费辅助表s [1 … .. n, 1 … .. .n]记录了k的哪个索引在计算m [i, j]时达到了最佳成本。
对于i = 1、2、3 … .. n, 即长度为1的链的最小成本, 该算法首先计算m [i, j]←0。

    推荐阅读