矩阵链乘法的例子 _矩阵链乘法

示例：给定序列{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

有两种情况可以解决此乘法：（M1 x M2）+ M3, M1 +（M2x M3）
解决这两种情况后, 我们选择存在最小输出的情况。

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

M [2, 4] = M2 M3 M4

有两种情况可以解决此乘法：（M2x M3）+ M4, M2 +（M3 x M4）
解决这两种情况后, 我们选择存在最小输出的情况。

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

M [3, 5] = M3M4M5

有两种情况可以解决此乘法：（M3 x M4）+ M5, M3 +（M4xM5）
解决这两种情况后, 我们选择存在最小输出的情况。

文章图片

M [3, 5] = 1140

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

文章图片
现在有4个矩阵的乘积：

M [1, 4] = M1M2 M3 M4

在三种情况下, 我们可以解决此乘法：

（M1 x M2 x M3）M4
M1 x（M2 x M3 x M4）
（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

在三种情况下, 我们可以解决此乘法：

（M2 x M3 x M4）x M5
M2 x（M3 x M4 x M5）
（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

有五种情况可以解决此乘法：

（M1 x M2 xM3 x M4）x M5
M1 x（M2 xM3 x M4 xM5）
（M1 x M2 xM3）x M4 xM5
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。