in

Matrix Chain Multiplication using C++

Matrix chain multiplication or Matrix Chain Ordering Problem, MCOP is an optimization problem that to find the most efficient way to multiply a given sequence of matrices. The problem is not actually to perform the multiplications, but merely to decide the sequence of the matrix multiplications involved.

The matrix multiplication is associative as no matter how the product is parenthesized, the result obtained will remain the same. For example, for four matrices A, B, C, and D, we would have

((AB)C)D = ((A(BC))D) = (AB)(CD) = A((BC)D) = A(B(CD))

Example Code

#include <iostream>

#include <climits>

using namespace std;

// Function to find the most efficient way to multiply

// given sequence of matrices

int MatrixChainMultiplication(int dims[], int i, int j)

{

// base case: one matrix

if (j <= i + 1)

return 0;

// stores minimum number of scalar multiplications (i.e., cost)

// needed to compute the matrix M[i+1]…M[j] = M[i..j]

int min = INT_MAX;

// take the minimum over each possible position at which the

// sequence of matrices can be split

/*

(M[i+1]) x (M[i+2]………………M[j])

(M[i+1]M[i+2]) x (M[i+3………….M[j])

(M[i+1]M[i+2]…………M[j-1]) x (M[j])

*/

for (int k = i + 1; k <= j – 1; k++)

{

// recur for M[i+1]..M[k] to get a i x k matrix

int cost = MatrixChainMultiplication(dims, i, k);

// recur for M[k+1]..M[j] to get a k x j matrix

cost += MatrixChainMultiplication(dims, k, j);

// cost to multiply two (i x k) and (k x j) matrix

cost +=dims[i] * dims[k] * dims[j];

if (cost < min)

min = cost;

}

// return min cost to multiply M[j+1]..M[j]

return min;

}

// Matrix Chain Multiplication Problem

int main()

{

// Matrix M[i] has dimension dims[i-1] x dims[i] for i = 1..n

// input is 10 × 30 matrix, 30 × 5 matrix, 5 × 60 matrix

int dims[] = { 10, 30, 5, 60 };

int n = sizeof(dims) / sizeof(dims[0]);

cout << “Minimum cost is ” << MatrixChainMultiplication(dims, 0, n – 1);

return 0;

}

This post was created with our nice and easy submission form. Create your post!

What do you think?

Written by Raj Chhetri

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

Loading…

0

Valorant: Riot Games' First FPS Shooter

0-1 Knapsack Problem using C++