CODEWITHSUNDEEP
algorithmdynamicmatrixpseudocode
ayush nigam
ayush nigam

Reputation: 177

matrix chain mutiplication dynamic programming

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

this is the pseudocode for matrix chanin multiplication i cant understand this part

  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;

why are taking i to be less than or equal to (n-L+1) and j=i+L-1

am a beginner

Upvotes: 3

Views: 1919

Answers (1)

vgru
vgru

Reputation: 51204

First of all, it's pseudocode, and these arrays are 1-based. If you are using a C-like language, that will probably be the first issue, since arrays in C start at index 0 and end at len-1, if len is the length of array. Next, the variable n is chosen to be smaller than the total number of matrices by 1. If you replace n with p.length - 1, then it may also become a bit clearer what's going on.

  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).

  2. 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 <.

  3. 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).

  4. 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.

Upvotes: 3

Related Questions