动态规划实现矩阵乘法

Question

我正在尝试理解下面这个使用动态规划进行矩阵乘法的算法。

如果mi，j是计算产品Mi × ... × Mj的最小成本，则有：

• 如果i = j，则mi，j = 0
• 如果i < j，则mi，j = MIN，其中i ≤ k < j{ mi，k + mk + 1，j + ri-1rkrj }

算法：

for i := 1 to n do
   mi,i := 0
for length := 1 to n-1 do
   for i := 1 to n-length do
      j := i + length
      mi,j = MINi≤k<j{mi,k + mk+1,j + ri-1rkrj}

有没有关于它如何实际工作的线索，或者有没有人能够为我指出一个好的参考资料。

- ASingh

---

这段代码只是重复了数学陈述而已。您是在问这个数学公式从何而来？ - Code-Apprentice

Answer 1

算法找到了矩阵链相乘的最低成本。

给定一个行数为 p，列数为 q 的矩阵 A，和一个行数为 q，列数为 r 的矩阵 B，标准矩阵乘法 A·B 需要进行 p*q*r 次乘法 - 对于乘积的每个 p×r 元素，需要对应行的 A 元素和对应列的 B 元素进行 q 次乘法。

现在，矩阵乘法是结合律的，因此您可以将乘积括起来。

M_1 · M_2 · … · M_n

随便怎么做，结果总是相同的。

现在，设r_0为M_1的行数，r_i为M_i的列数（也必须是M_(i+1)的行数才能定义乘积）。

那么M_i · … · M_k是一个r_(i-1)×r_k矩阵，M_(k+1) · … · M_j是一个r_k×r_j矩阵。因此，如果通过先计算M_i · … · M_k和M_(k+1) · … · M_j的乘积，然后将两个结果矩阵相乘来计算乘积M_i · … · M_j，则乘法的总成本为

c_{i,k} + c_{k+1,j} + r_(i-1)×r_k×r_j

其中c_{i,k}表示计算M_i · … · M_k的所选方式的成本（对于c_{k+1,j}也是如此）。

现在，通过在M_k后分割来评估M_i · … · M_j的最小成本显然可以通过以最小成本计算两个子乘积来实现。

而评估M_i · … · M_j的最小成本是通过计算所有可能分割的最小成本来找到的，因此为：

m_{i,j} = min { m_{i,k} + m_{k+1,j} + r_(i-1)×r_k×r_j : i <= k < j }

对于 i < j，需要进行翻译。

然后，首先计算仅涉及两个矩阵的子产品的最小成本[其中只有一个可能的拆分]，然后计算涉及三个矩阵的子产品的最小成本，为此需要计算仅涉及两个矩阵的子产品的最小成本 - 这就是括号化发挥作用的地方，并且通常会产生差异 - 然后四个等等，直到找到总计算的最小成本。

要找到产生最低成本的括号化，可以搜索最小成本数组以定位产生它的拆分[然后是两个子产品等等]，但最好将产生最小成本的拆分位置的信息与m数组中的最小成本一起存储。

- Daniel Fischer

Answer 2

我不喜欢复制和粘贴，我会简短地用自己的话来表达：

这个问题的关键是：计算A*B*C只有两种可能的方式：A*(B*C)或(A*B)*C。同样，计算A*B*C*D只有三种方式：A*(B*C*D)，(A*B)*(C*D)，(A*B*C)*D。（注意：这里的(B*C*D)和(A*B*C)是一个子问题，已经在之前计算过了）

因此，计算M1*M2*...Mn有n-1种可能性：M1(M2*M3*...*Mn)，(M!M2)(M3*...*Mn)，...，(M1*M2*...*Mn-1)*Mn

这就是你所给出的伪代码的含义 :)

- songlj