algorithm - 使用动态规划的矩阵乘法

Question

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

如果mi, j是评估产品Mi × ... × Mj的最小成本，那么:

• mi, j = 0, 如果 i = j, 并且
• mi, j = MIN, i ≤ k < j { mi,k + mk+1,j + ri-1rkrj }，如果 i < j。

算法:

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}

关于它实际如何工作的任何线索，或者是否有人可以为我指出一个很好的引用。

Answer 1

该算法找到乘以矩阵链的最低成本。

给定一个矩阵 A与 p行和 q列和矩阵 B与 q行和 r列，标准矩阵乘法A·B需要 p*q*r乘法 - 对于 p×r 中的每一个产品条目，q A 对应行的元素之间的乘法和B对应的栏目.

现在，矩阵乘法是结合的，所以你可以用括号括起乘积

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_j通过首先计算产品 M_i · … · M_k 来计算和 M_(k+1) · … · 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_i · … · M_j在 M_k 之后拆分如果以最小成本评估两个子产品，则显然可以实现。

和最小的评估成本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 中以最低成本分割的位置数组。