矩阵链乘法和一些不同的问题？

user4627889 发表于 Dev

用户名

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

我们想要找到一个矩阵乘法的顺序，以使中间矩阵中的元素数量（在生产的所有步骤中计算出的数量）最小化（我们称其为生产成本）。我们有A_1 * A_2 * A_3 * ... * A_n，尺寸A_i在d_ {i-1}和d_i上。C_ {ij} =最小生产成本A_i * ... * A_j子问题，C_ {ii} = 0。他说解决这个问题的关系是：

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

我能理解，这种关系背后的想法是什么？有什么可以帮助我的吗？

克拉斯科维奇

假设我们要最小化C(i, j)。我们可以选择什么？我们可以选择将要执行的最后一个乘法的位置。固定后，我们有两个独立的子问题（最后一个乘法之前的所有问题，以及它之后的所有问题）。因此C_{ij}=min i<=k < j max{C_{ik}, C_{k+1,j}, d_{i-1}*d_j}，普通英语中的等式意味着：

让我们选择最后一个乘法的位置，并表示它是k。
让我们解决两个子问题：一个用于(i, k)，另一个用于(k + 1, j)。
对于一个固定的k，答案是这两个子问题的结果的最大值以及在(i, j)范围内的所有矩阵相乘后得到的最终矩阵的大小（即，d_{i-1}*d_j它不取决于乘法的顺序）。
我们想要最小化结果，因此我们在所有有效值中选择最小值k。