Matrix- Chain- Multiplication Algorithm
The Matrix-Chain-Multiplication Algorithm is a dynamic programming algorithm used to solve the matrix chain multiplication problem, which aims to find the most efficient way to multiply a series of matrices. The algorithm focuses on determining the optimal parenthesization of the matrices, that is, the order in which the matrices should be multiplied to minimize the total number of scalar multiplications. The matrix chain multiplication problem arises in various scientific and engineering applications, including computer graphics, robotics, and optimization, where large matrix multiplications are common.
The Matrix-Chain-Multiplication Algorithm works by utilizing a bottom-up approach, where it builds an optimal solution by solving smaller subproblems and combining their results. The algorithm computes the minimum number of scalar multiplications required for each possible subchain of matrices, and stores the results in a table. This table is then used to determine the optimal parenthesization by backtracking through the table and constructing the optimal solution. By using dynamic programming, the Matrix-Chain-Multiplication Algorithm avoids redundant calculations and reduces the time complexity of the problem from exponential (in the naive recursive approach) to polynomial time (O(n^3) for n matrices). This makes it an efficient and practical solution for large matrix chain multiplication problems.
#include <iostream>
#include <climits>
using namespace std;
#define MAX 10
// dp table to store the solution for already computed sub problems
int dp[MAX][MAX];
// Function to find the most efficient way to multiply the given sequence of matrices
int MatrixChainMultiplication(int dim[], 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;
// if dp[i][j] is not calculated (calculate it!!)
if (dp[i][j] == 0)
{
// take the minimum over each possible position at which the
// sequence of matrices can be split
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(dim, i, k);
// recur for M[k+1]..M[j] to get a k x j matrix
cost += MatrixChainMultiplication(dim, k, j);
// cost to multiply two (i x k) and (k x j) matrix
cost += dim[i] * dim[k] * dim[j];
if (cost < min)
min = cost; // store the minimum cost
}
dp[i][j] = min;
}
// return min cost to multiply M[j+1]..M[j]
return dp[i][j];
}
// main function
int main()
{
// Matrix i has Dimensions dim[i-1] & dim[i] for i=1..n
// input is 10 x 30 matrix, 30 x 5 matrix, 5 x 60 matrix
int dim[] = {10, 30, 5, 60};
int n = sizeof(dim) / sizeof(dim[0]);
// Function Calling: MatrixChainMultiplications(dimensions_array, starting, ending);
cout << "Minimum cost is " << MatrixChainMultiplication(dim, 0, n - 1) << "\n";
return 0;
}
