C++ Program for Matrix Chain Multiplication














































C++ Program for Matrix Chain Multiplication




This is a Program to understand Matrix Chain Multiplication.

So First of all What is the Problem Statement?

We are given a sequence (chain) <A1, A2, ...... ,An> of n matrices to be multiplied, and we wish to compute the product 

A1*A2* .... *  An


One Nive Way is

We can evaluate the expression (15.5) using the standard algorithm for multiplying pairs of matrices as a subroutine once we have parenthesized it to resolve all ambiguities in how the matrices are multiplied together.


Matrix multiplication is associative, and so all parenthesizations yield the same product. A product of matrices is fully parenthesized if it is either a single matrix or the product of two fully parenthesized matrix products, surrounded by parentheses. For example, if the chain of matrices is <A1, A2, A3,  A4>  then we can fully parenthesize the product

 A1*A2*A3*A4 in five distinct ways:

  1. ( A1( A2 ( A3 * A4 ) ) )
  2. ( A1( ( A2 * A3 ) A4 ) )
  3. ( ( A1 * A2) (A3 * A4 ) )
  4. ( ( A1 ( A2 * A3  ) A4 )
  5. ( ( ( A1 * A2 ) A3 ) A4 )

How we parenthesize a chain of matrices can have a dramatic impact on the cost of evaluating the product. Consider first the cost of multiplying two matrices.


So here is the Formula we will be used for solving our problem in an optimized way,



Of course we will be using dynamic programming and our approach will be as follow 

1. Characterize the structure of an optimal solution. 

2. Recursively define the value of an optimal solution. 

3. Compute the value of an optimal solution

4. Construct an optimal solution from computed information.

MATRIX-MULTIPLY.A; B/
1 if A:columns ¤ B:rows
2 error “incompatible dimensions”
3 else let C be a new A:rows 	 B:columns matrix
4 for i D 1 to A:rows
5 for j D 1 to B:columns
6 cij D 0
7 for k D 1 to A:columns
8 cij D cij C aik  bkj
9 return C


Here is the sample code for more clarification.

C++ CODE 

#include <bits/stdc++.h> using namespace std; int MatrixChainOrder(int p[], int i, int j) { if (i == j) return 0; int k; int min = INT_MAX; int count; for (k = i; k < j; k++) { count = MatrixChainOrder(p, i, k) + MatrixChainOrder(p, k + 1, j) + p[i - 1] * p[k] * p[j]; if (count < min) min = count; } return min; } int main() { int arr[] = {1, 2, 3, 4, 3}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Minimum number of multiplications is "<< MatrixChainOrder(arr, 1, n - 1); } /* OUTPUT Minimum number of multiplications is 30 */

More Articles of Anand Dasani:

Name Views Likes
C++ Program for OBST (Optimal Binary Search Tree) 4135 1
C++ Program for Matrix Chain Multiplication 3028 1
C++ Program for Huffman Code 3601 1
C++ Program for 8 Queen problem 2794 1
C++ Program for KnapSack Problem TopDown Solution 576 1
C++ Program for KnapSack Problem Memoization Solution 722 1
C++ Program for KnapSack Problem Recursive Solution 629 1
C++ Program for Tower Of Hanoi problem 507 1
C++ Program to Evaluate the Postfix string using stack 439 1
C++ Program to check Balanced Parenthesis in string using stack 447 1
C++ Program for String Palindrome check using stack 2997 1
C++ Program to Convert Infix Expression to Prefix Expression including Parenthesis 337 1
C++ Program To Convert Infix Expression to Prefix Expression without Parenthesis 663 1
C++ PROGRAM TO CONVERT INFIX EXPRESSION TO POSTFIX EXPRESSION WITHOUT PARENTHESIS 333 1
C++ Program to Convert Infix Expression to Postfix Expression including Parenthesis 357 1
C++ Program to Convert Decimal Value to Hexa Decimal using Stack 798 1
C++ Program to Convert Decimal Value to Octal using Stack 983 1
C++ Program to Convert Decimal Value to Binary using Stack 612 1
C++ Program for Upper Triangular Matrix 587 1
C++ Program for Lower Triangular Matrix 317 1
C++ Program for Diagonal Matrix 465 1
C++ Program to Perform Full Deletion operation in BST 278 1
C++ Program to count the nodes having Degree 2 in BST 649 1
C++ Program to count the nodes having 1 Degree in BST 482 1
C++ Program to count the nodes having 0 Degree in BST 338 1
C++ Program to count the Height of Binary Search Tree 299 1
C++ Program to prevent deletion of node having degree 2 in Binary Search Tree 261 2
C++ Program to prevent deletion of node having degree 0 or 1 in Binary Search Tree 279 1

Comments