Background   

If two matrix A and B whose dimension is (m,n) and (n,p) respectively then the multiplication of A and B needs m*n*p scalar multiplication.

Suppose you are given a sequence of n matrix A₁,A₂,.....A_n. Matrix A_i has dimension (P_i-1,P_i). Your task is to parenthesize the product A₁,A₂,.....A_n such a way that minimize the number of scalar product.

As matrix multiplication is associative so all the parenthesizations yield the same product.

A brute force approach of finding the optimal sequence is enumerating all sequences and finding the optimum one which takes too much time. However, We have a Dynamic Programming solution for this problem. For details, you are refer to Introduction to Algorithm, By by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest second edition chapter 15 (Dynamic Programming), I will write the algorithm first and then code of this, written in C++, ready to use.

The  algorithm :

MATRIX_CHAIN_ORDER(P)
The input  is a sequrnce P = <P₀,P₁,P₂,.....P_n> where length[P] = n+1. The procedure uses an auxlary table m[1....n,1....n] for storing the m[i,j] costs and auxlary table s[1...n,1...n] that records which index of k achive the optimal cost in computing m[i,j].

1. n <- length[P]-1

2. for i <- 1 to n

3.        do m[i,j] <- 0

4. for l <- 2 to n

5.        do for i <- 1 to n – l + 1

6.                  do j <- i + l – 1

7.                       m[i,j] <- INF     //  INF is infnity

8.                       for k <- i  to j –1

9.                             do q <- m[i,k]+m[k+1,j]+ P_i-1P_kP_j

10.                                   if q < m[i,j]

11.                                       then m[i,j] <- q

12.                                               s[i,j] <- k

13. return m,s

 

PRINT(s,i,j)
The following recursive procedure prints an optimal parentathesization of (A_i,A_i+1,.....Aj) given the s table computed by MATRIX_CHAIN_ORDER and indices i and j. The initial call PRINT(s,1,n) prints optimal parentathesization of (A₁,A₂,.....A_n). 

1. if i == j

2.     then print “A”i

3.     else  print “(“

4.             PRINT(s,i,s[i,j])

5.             PRINT(s,s[i,j]+1,j)

6.             print “)”

Code

/* matrix.cpp

 

   Implementation of general matrix chain multiplication algorithm

 

   Compiled : CYGNU & Microsoft Visual C++ 6.0

 

   Copyright 2003 by M H Rasel & CUET Old Sailor ; all rights reserved.

 

   Permission is granted for use in non-commerical applications provided this copyrightnotice remains intact and

    unchanged.

*/

 

#include<stdio.h>

 

#define MAX 15               /* number of matrix */

#define INF 4294967295       /* a maximum number of multiplication */

 

int num;

/* ************************************************* */

/*     Print out the sequence                        */

/*     Input : A two dimentional array(created       */

/*             by the matrix chan order function)    */

/*             with there starting point             */

/*     Return : None                                 */

/* ************************************************* */

void print(unsigned long s[][MAX],int i,int j)

{

   if(i==j)

      printf("A%d",num++);

   else

   {

      printf("(");

      print(s,i,s[i][j]);

      printf(" x ");

      print(s,s[i][j]+1,j);

      printf(")");

   }

}

 

/* *********************************************** */

/*      Find out the order                         */

/*      Input : A sequence of dimention and the    */

/*              number of matrix                   */

/*      Return : none                              */

/* *********************************************** */

void matrix_chan_order(int *p,int n)

{

   unsigned long m[MAX][MAX] = {0};

   unsigned long s[MAX][MAX] = {0};

   unsigned int q;

   int l,j,i,k;

   for(l = 2; l <= n ;l++)

   {

       for(i = 1 ; i <= n - l +1 ; i++)

       {

          j = i + l -1;

          m[i][j] = INF;

          for(k=i ; k < j ; 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;

                 s[i][j] = k;

             }

          }

       }

   }

   num =1;

   print(s,1,n);

}

 

/* A sample main function */

main(void)

{

   int n;

   int p[MAX]={0};

   int i;

 

   while(scanf("%d",&n),n)

   {

      for(i=1;i<=n;i++)

          scanf("%d %d",&p[i-1],&p[i]);

      matrix_chan_order(p,n);

      putchar('\n');

   }

 

   return 0;

}