我正在尝试理解以下使用动态规划进行矩阵乘法的算法。
如果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}
关于它实际如何工作的任何线索,或者是否有人可以为我指出一个很好的引用。
最佳答案
该算法找到乘以矩阵链的最低成本。
给定一个矩阵 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
中以最低成本分割的位置数组。
关于algorithm - 使用动态规划的矩阵乘法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14286150/