matrix chain multiplication Algorithm

Matrix chain multiplication algorithm is an optimization technique used to find the most efficient way to multiply a chain of matrices. The problem of matrix chain multiplication is to determine the optimal sequence of multiplying a series of matrices in order to minimize the total number of scalar multiplications involved. This algorithm is based on dynamic programming, which enables it to efficiently compute the optimal solution by breaking the problem down into smaller overlapping subproblems and reusing the solutions of these subproblems to build the final solution. The algorithm is mainly concerned with determining the optimal parenthesization of the matrices, and not with performing the actual multiplications. Given a sequence of matrices, the algorithm finds the optimal way to multiply them by exploiting the associative property of matrix multiplication, i.e., (A*B)*C = A*(B*C), where A, B, and C are matrices. This property allows us to parenthesize the matrices in different ways, without affecting the result. However, different parenthesizations may lead to different numbers of scalar multiplications, and that's where the algorithm comes in to minimize this number. The algorithm uses a table to store the minimum number of multiplications required to multiply a chain of matrices, which is then used to calculate the minimum number of multiplications for a longer chain. The table is filled in a bottom-up manner, starting with chains of length 2 and going up to the full length of the chain. Once the table is filled, the algorithm can backtrack through it to find the optimal parenthesization. Overall, the matrix chain multiplication algorithm provides an efficient solution to a common problem in many applications, such as computer graphics, data analysis, and scientific computing.
#include<iostream>
#include<limits.h>

using namespace std;


int MatrixChainMultiplication(int p[], int n)
{
    int m[n][n];
    int i, j, k, L, q;

    for (i=1; i<n; i++)
        m[i][i] = 0;
    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 = 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];

}

int main()
{
    int n,i;
    cout<<"Enter number of matrices\n";
    cin>>n;


    int arr[n];

    cout<<"Enter dimensions \n";

    for(i=0;i<n;i++)
    {
        cout<<"Enter d"<<i+1<<" :: ";
        cin>>arr[i];
    }

    int size = sizeof(arr)/sizeof(arr[0]);

    cout<<"Minimum number of multiplications is "<<MatrixChainMultiplication(arr, size);

    return 0;
}

LANGUAGE:

DARK MODE: