3

我试图了解以下使用动态编程进行矩阵乘法的算法。

如果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}

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

4

2 回答 2

2

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

给定一个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阵列中的最低成本分开。

于 2013-01-11T22:42:36.937 回答
0

我不喜欢复制和粘贴，我会保持简短并用我自己的话给出：

这个问题的关键是：计算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

这就是您给定的伪代码中的内容:)

于 2013-01-12T09:27:08.217 回答