algorithm - 矩阵链乘法动态规划

Question

  // Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
    Matrix-Chain-Order(int p[])
{
// length[p] = n + 1
n = p.length - 1;
// m[i,j] = Minimum number of scalar multiplications (i.e., cost)
// needed to compute the matrix A[i]A[i+1]...A[j] = A[i..j]
// cost is zero when multiplying one matrix
for (i = 1; i <= n; i++) 
   m[i,i] = 0;

for (L=2; L<=n; L++) { // L is chain length
    for (i=1; i<=n-L+1; i++) {
        j = i+L-1;
        m[i,j] = MAXINT;
        for (k=i; k<=j-1; k++) {
            // q = cost/scalar multiplications
            q = m[i,k] + m[k+1,j] + p[i-1]*p[k]*p[j];
            if (q < m[i,j]) {
                m[i,j] = q;
                // s[i,j] = Second auxiliary table that stores k
                // k      = Index that achieved optimal cost
                s[i,j] = k;
            }
        }
    }
}
}

这是矩阵链乘法的伪代码我无法理解这部分

  for (L=2; L<=n; L++) { // L is chain length
    for (i=1; i<=n-L+1; i++) {
        j = i+L-1;
        m[i,j] = MAXINT;

为什么取 i 小于或等于 (n-L+1) 且 j=i+L-1

我是初学者

score 3 · Accepted Answer

首先，它是伪代码，而且这些数组都是从 1 开始的。如果您使用的是类 C 语言，那可能是第一个问题，因为 C 中的数组从 index 开始，以0结束len-1，如果len是数组的长度。接下来，n选择比矩阵总数小的变量1。如果你用替换n，p.length - 1那么它也可能会变得更清楚发生了什么。

您想L针对所有可能的链长运行外循环（即链长）。您从最小的链长度开始（只有两个矩阵）并以所有矩阵结束（即L从2到n）。在此之前，成本数组被初始化为只有一个矩阵的平凡情况（即没有乘法）。
这意味着i可以从1直到最后一项减去链长度（n-L+1注意这n是p.length - 1有效的p.length - L）。例如，如果您当前正在检查长度链4，您的i循环将像这样有效地运行：
```
L = 4;
for (i = 1; i <= p.length - 4; i++)
{
   ...
}
```
在 C 中，你会写for (i = 0; i < p.length - 4; i++). 请注意，<=替换为<.
接下来，您试图获得从i, 的长度开始的乘法链的成本L。这意味着链中的最后一个元素是j = i + L -1。同样，如果当前链长度为L，那么您有：
```
L = 4;
for (i = 1; i <= p.length - 4; i++)
{
    j = i + 3;
    ...
}
```
换句话说，如果i是 10，你想j成为 13，因为那是一个长度为 4（10、11、12、13）的链。
最后，您需要检查和之间的所有链的i成本j。这就是为什么k要从i到j-1。对于 chain length 的示例L=4，您有：
```
L = 4;
for (i = 1; i <= p.length - 4; i++)
{
    j = i + 3;
    m[i,j] = MAXINT;
    for (k = i; k <= j - 1; k++)
    { 
        // get the cost of splitting at `k`, 
        // i.e. chains (i, k) and (k + 1, j)
    }
}
```
换句话说，如果L是 4，并且i是 10，并且j是 13，你要测试链(10)(11,12,13)，(10,11)(12,13)和(10,11,12)(13)。因此k必须从i到j-1。

algorithm - 矩阵链乘法动态规划

1 回答 1

Related

Reference