algorithm - 矩阵链乘法和有点不同的问题？

Question

我们知道矩阵链乘法问题。我的教授解决了一个密切的问题:

We want to find an order of Matrix multiplication such that number of elements in middle matrixes (calculated in all steps of production) is minimized (we called it cost of production). We have A_1*A_2*A_3*...* A_n and dimension A_i is on d_{i-1} and d_i. C_{ij} = min cost of production A_i*...*A_j sub problems and C_{ii}=0. he says the relation for solving this problem is:

C_{ij}=min i<=k < j  max{C_{ik}, C_{k+1,j}, d_{i-1}*d_j}

我不明白，这个关系背后的想法是什么？怎么帮我？

Answer 1

假设我们要最小化 C(i, j) .我们可以选择什么？我们可以选择要执行的last 乘法的位置。当它固定时，我们有两个独立的子问题(最后一次乘法之前的所有内容和最后一次乘法之后的所有内容)。所以等式C_{ij}=min i<=k < j max{C_{ik}, C_{k+1,j}, d_{i-1}*d_j}用简单的英语表示:

1. 让我们选择最后一次乘法的位置并表示它是k .

2. 让我们解决两个子问题:一个用于 (i, k)另一个 (k + 1, j) .

3. 对于一个固定的k ，答案是这两个子问题的结果的最大值和我们在将 (i, j) 中的所有矩阵相乘后得到的最终矩阵的大小。范围(即 d_{i-1}*d_j ，不依赖于乘法顺序)。

4. 我们想要最小化结果，所以我们选择所有有效 k 中的最小值.

就是这样。