Prerequisite : Dynamic Programming | Set 8 (Matrix Chain Multiplication)

Given a sequence of matrices, find the most efficient way to multiply these matrices together. The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications.

We have many options to multiply a chain of matrices because matrix multiplication is associative. In other words, no matter how we parenthesize the product, the result will be the same. For example, if we had four matrices A, B, C, and D, we would have:

(ABC)D = (AB)(CD) = A(BCD) = ....

However, the order in which we parenthesize the product affects the number of simple arithmetic operations needed to compute the product, or the efficiency. For example, suppose A is a 10 × 30 matrix, B is a 30 × 5 matrix, and C is a 5 × 60 matrix. Then,

(AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.

Clearly the first parenthesization requires less number of operations.

*Given an array p[] which represents the chain of matrices such that the ith matrix Ai is of dimension p[i-1] x p[i]. We need to write a function MatrixChainOrder() that should return the minimum number of multiplications needed to multiply the chain.*

Input: p[] = {40, 20, 30, 10, 30} Output: Optimal parenthesization is ((A(BC))D) Optimal cost of parenthesization is 26000There are 4 matrices of dimensions 40x20, 20x30, 30x10 and 10x30. Let the input 4 matrices be A, B, C and D. The minimum number of multiplications are obtained by putting parenthesis in following way (A(BC))D --> 20*30*10 + 40*20*10 + 40*10*30Input: p[] = {10, 20, 30, 40, 30}Output: Optimal parenthesization is (((AB)C)D) Optimal cost of parenthesization is 30000There are 4 matrices of dimensions 10x20, 20x30, 30x40 and 40x30. Let the input 4 matrices be A, B, C and D. The minimum number of multiplications are obtained by putting parenthesis in following way ((AB)C)D --> 10*20*30 + 10*30*40 + 10*40*30Input: p[] = {10, 20, 30}Output: Optimal parenthesization is (AB) Optimal cost of parenthesization is 6000There are only two matrices of dimensions 10x20 and 20x30. So there is only one way to multiply the matrices, cost of which is 10*20*30

This problem is mainly an extension of previous post. In the previous post, we have discussed algorithm for finding optimal cost only. Here we need print parenthssization also.

The idea is to store optimal break point for every subexpression (i, j) in a 2D array bracket[n][n]. Once we have bracket array us constructed, we can print parenthesization using below code.

// Prints parenthesization in subexpression (i, j) printParenthesis(i, j, bracket[n][n], name) { // If only one matrix left in current segment if (i == j) { print name; name++; return; } print "("; // Recursively put brackets around subexpression // from i to bracket[i][j]. printParenthesis(i, bracket[i][j], bracket, name); // Recursively put brackets around subexpression // from bracket[i][j] + 1 to j. printParenthesis(bracket[i][j]+1, j, bracket, name); print ")"; }

Below is C++ implementation of above steps.

` ` `// C++ program to print optimal parenthesization ` `// in matrix chain multiplication. ` `#include<bits/stdc++.h> ` `using` `namespace` `std; ` ` ` `// Function for printing the optimal ` `// parenthesization of a matrix chain product ` `void` `printParenthesis(` `int` `i, ` `int` `j, ` `int` `n, ` ` ` `int` `*bracket, ` `char` `&name) ` `{ ` ` ` `// If only one matrix left in current segment ` ` ` `if` `(i == j) ` ` ` `{ ` ` ` `cout << name++; ` ` ` `return` `; ` ` ` `} ` ` ` ` ` `cout << ` `"("` `; ` ` ` ` ` `// Recursively put brackets around subexpression ` ` ` `// from i to bracket[i][j]. ` ` ` `// Note that "*((bracket+i*n)+j)" is similar to ` ` ` `// bracket[i][j] ` ` ` `printParenthesis(i, *((bracket+i*n)+j), n, ` ` ` `bracket, name); ` ` ` ` ` `// Recursively put brackets around subexpression ` ` ` `// from bracket[i][j] + 1 to j. ` ` ` `printParenthesis(*((bracket+i*n)+j) + 1, j, ` ` ` `n, bracket, name); ` ` ` `cout << ` `")"` `; ` `} ` ` ` `// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n ` `// Please refer below article for details of this ` `// function ` `void` `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]; ` ` ` ` ` `// bracket[i][j] stores optimal break point in ` ` ` `// subexpression from i to j. ` ` ` `int` `bracket[n][n]; ` ` ` ` ` `/* m[i,j] = Minimum number of scalar multiplications ` ` ` `needed to compute the matrix A[i]A[i+1]...A[j] = ` ` ` `A[i..j] where dimension of A[i] is p[i-1] x p[i] */` ` ` ` ` `// cost is zero when multiplying one matrix. ` ` ` `for` `(` `int` `i=1; i<n; i++) ` ` ` `m[i][i] = 0; ` ` ` ` ` `// L is chain length. ` ` ` `for` `(` `int` `L=2; L<n; L++) ` ` ` `{ ` ` ` `for` `(` `int` `i=1; i<n-L+1; i++) ` ` ` `{ ` ` ` `int` `j = i+L-1; ` ` ` `m[i][j] = INT_MAX; ` ` ` `for` `(` `int` `k=i; k<=j-1; k++) ` ` ` `{ ` ` ` `// q = cost/scalar multiplications ` ` ` `int` `q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; ` ` ` `if` `(q < m[i][j]) ` ` ` `{ ` ` ` `m[i][j] = q; ` ` ` ` ` `// Each entry bracket[i,j]=k shows ` ` ` `// where to split the product arr ` ` ` `// i,i+1....j for the minimum cost. ` ` ` `bracket[i][j] = k; ` ` ` `} ` ` ` `} ` ` ` `} ` ` ` `} ` ` ` ` ` `// The first matrix is printed as 'A', next as 'B', ` ` ` `// and so on ` ` ` `char` `name = ` `'A'` `; ` ` ` ` ` `cout << ` `"Optimal Parenthesization is : "` `; ` ` ` `printParenthesis(1, n-1, n, (` `int` `*)bracket, name); ` ` ` `cout << ` `"nOptimal Cost is : "` `<< m[1][n-1]; ` `} ` ` ` `// Driver code ` `int` `main() ` `{ ` ` ` `int` `arr[] = {40, 20, 30, 10, 30}; ` ` ` `int` `n = ` `sizeof` `(arr)/` `sizeof` `(arr[0]); ` ` ` `matrixChainOrder(arr, n); ` ` ` `return` `0; ` `} ` |

Output:

Optimal Parenthesization: ((A(BC))D) Minimum Cost of Multiplication: 26000

Time Complexity: O(n^3)

Auxiliary Space: O(n^2)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

## leave a comment

## 0 Comments