Clever Geek Handbook

Explanation for Chaining Matrix Multiplication using DP?

I couldn't understand the optimized copied matrix multiplication example (using DP) given in my algorithms book.

int MatrixChainOrder(int p[], int n)
{

    /* For simplicity of the program, one extra row and one extra column are
       allocated in m[][].  0th row and 0th column of m[][] are not used */
    int m[n][n];

    int i, j, k, L, q;

    /* m[i,j] = Minimum number of scalar multiplications needed to compute
       the matrix A[i]A[i+1]...A[j] = A[i..j] where dimention of A[i] is
       p[i-1] x p[i] */

    // cost is zero when multiplying one matrix.
    for (i = 1; i < n; i++)
        m[i][i] = 0;

    // L is chain length.  
    for (L=2; L<n; L++)   
    {
        for (i=1; i<=n-L+1; i++)
        {
            j = i+L-1;
            m[i][j] = INT_MAX;
            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;
            }
        }
    }

    return m[1][n-1];
}

Why does the first cycle start at 2? Why is j set to i + L-1 and i to nL + 1?

I figured out the recurrence, but couldn't figure out why the loops are set like this:

EDIT:

What is the way to get the order of the parentheses after DP?

+3


source to share


2 answers


From bottom to top, i.e. DP, we first try to solve the smallest possible case (we solve each smallest case). Now when we look at the recurrence (m [i, j] is the cost to install at level i, j ..)

m [i, j] represents cost to parenthise from i, j ..

We can see that the smallest possible solution (which any other larger subproblem would need) will be shorter than we need to solve ... For P (n). We need all the overhead of partitioning the expression down to length less than n. This brings us to a solution to the length problem ... (Note 1 in the outer loop represents the length of the segment we are trying to optimize for)

Now we first solve all auxiliary problems of length 1, i.e. always always (no multiplication required) ...



Now your question is L = 2 -> L = n we change the length from 2 to n to solve the sub-choices in order ...

i is the starting point of all subsections, such that they can be the beginning of an interval of length l ..

Naturally j represents the end of the sub-range -> i + l-1 is the end of the sub-range (just because we know the start point and length, we can calculate the end of the interval)

+2


source


L repeats the length of the chain. Obviously, the chain cannot be 1 piece long. i iterates over the beginning of the chain. If the first part is i, then the last part will be i + L-1, which is j. (Try to imagine the chain and count). The condition in the loop ensures that for any value of i, the last piece does not exceed the maximum length n. Soon, this is a limitation to keep values ​​within specified limits.



+1


source






More articles:


All Articles