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;
            }
        }
    }
}
}

これは、行列 chanin 乗算の擬似コードです。この部分は理解できません。

  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 と見なすのですか

初心者です

4

1 に答える 1