矩阵链乘法的例子

示例:给定序列{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) = m1  x m2
           = 4 x 10 x  10 x 3
           = 4 x 10 x 3 = 120
		   
2. m (2, 3) = m2 x m3
            = 10 x 3  x  3 x 12
            = 10 x 3 x 12 = 360
			
3. m (3, 4) = m3 x m4 
            = 3 x 12  x  12 x 20
            = 3 x 12 x 20 = 720
			
4. m (4, 5) = m4 x m5
           = 12 x 20  x  20 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. 解决这两种情况后, 我们选择存在最小输出的情况。
矩阵链乘法的DAA示例

M [2, 4] = 1320

由于在这两种情况下, 比较两个输出1320的最小值都是最小的, 因此我们将1320插入表中, 并选择M2 +(M3 x M4)进行输出组合。

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

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

矩阵链乘法的例子

现在有4个矩阵的乘积:

M [1, 4] = M1  M2 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)

解决这些情况后, 我们选择存在最小输出的情况

矩阵链乘法的DAA示例
M [2, 5] = 1350

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

矩阵链乘法的DAA示例

现在有5个矩阵的乘积:

M [1, 5] = M1  M2 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)

解决这些情况后, 我们选择存在最小输出的情况

矩阵链乘法的DAA示例
M [1, 5] = 1344

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

最终输出为:

矩阵链乘法的DAA示例

步骤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。

微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?