矩阵链乘法的例子

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

有两种情况可以解决此乘法：（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] = M3  M4  M5

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

M [3, 5] = 1140

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

现在有4个矩阵的乘积：

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

猜你喜欢