0

I am going over my review worksheet and was looking for some help with finding the recurrence relation for chained matrix multiplication using dynamic programming.

The problem verbatim: Consider the optimal parenthesization problem for the chained matrix product M0M1…Mn - 1 with associated dimension sequence (d0, d1, … ,dn). Derive the recurrence relation on which the dynamic programming solution for this problem is based, i.e., a recurrence relation for the minimum number mij of multiplications over all parenthesizations of the chained product MiM1…Mj . Don’t forget the initial condition.

I understand the formula for M[i,j] (M[i,j] = M[i,k] + M[k+1,j] + pqr). This definitely has recursion. But how to I determine the recurrence relation? Is this not the recurrence relation already? Also what is mean by "associated dimension space"?

4

1 回答 1

2

请参阅第 6.5 节（链矩阵乘法）请参阅http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf

这里的关联维度是指每个矩阵的维度，即 M0 的维度为 d0，M1 的维度为 d1，M2 的维度为 d2 .... 等等。

于 2012-11-28T11:43:59.493 回答