矩阵链乘法动态规划

Question

矩阵链乘法动态规划

3

  // 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？

我是一个初学者。

- ayush nigam

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- vgru · Accepted Answer

首先，这是伪代码，这些数组从1开始计数。如果你使用类似C的语言，那可能会是第一个问题，因为在C中，数组从索引0开始，以len-1结束，如果len是数组的长度。接下来，选择变量n比矩阵的总数少1。如果你将n替换为p.length - 1，那么可能会更加清晰地理解正在发生的事情。

You want to run the outer loop (i.e. the chain length L) for all possible chain lengths. You start with the smallest chain length (only two matrices) and end with all matrices (i.e. L goes from 2 to n). Prior to that, the cost array was initialized for the trivial case of only one matrix (i.e. no multiplication).
This means that i can go from 1 until the last item minus the chain length (n-L+1, note that n is p.length - 1 so this is effectively p.length - L). For example, if you are currently checking chains of length 4, your i loop would effectively run like this:
```
L = 4;
for (i = 1; i <= p.length - 4; i++)
{
   ...
}
```
In C, you would write for (i = 0; i < p.length - 4; i++). Note that <= is replaced with <.
Next, you are trying to get the cost of multiplying chain starting at i, of length L. This means that the last element in the chain is j = i + L -1. Again, if the current chain length is L, then you have:
```
L = 4;
for (i = 1; i <= p.length - 4; i++)
{
    j = i + 3;
    ...
}
```
In other words, if i is 10, you want j to be 13, because that's a chain of length 4 (10,11,12,13).
Finally, you need to check costs of all chains in between i and j. That's why k is going from i to j-1. For the example with chain length L=4, you have:
```
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)
    }
}
```
In other words, if L is 4, and i is 10, and j is 13, you want to test chains (10)(11,12,13), (10,11)(12,13) and (10,11,12)(13). Hence the k must go from i to j-1.