# Recursive Matrix Chain

• 11-05-2002
Stewdent
Recursive Matrix Chain
having trouble implementing the Recursive-Matrix-Chain algorithm found in the Cormen, Leiserson "Intro to Algorithms" books.

this algorithm looks for the minimum number of scalar multiplications needed to compute the product of a series of matrices, NOT the actual product of multiplying the matrices

the results are stored in a two dimensional array M[][]

this is a sample of dynamic programming

here is what I have come up with, and if you run this you can see that not every position is being examined

Any help would be appreciated

Code:

```#include <iostream> #include <cstdlib> using namespace std; const int SIZE = 7; const int MAX = 99999; int M[SIZE][SIZE]; int i, k, q, j; int P[SIZE] = { 25,10,15,5,30,10,15}; int Recursive_Matrix(int i, int j); void Print_M(); int main() {         Recursive_Matrix( 1, SIZE-1);         Print_M();             system("PAUSE");         return 0; } int Recursive_Matrix(int i, int j) {         if( i == j )                 return 0;         else         {                 M[i][j] = MAX;                 for(k = i; k <= j-1; k++)                 {                         q =  Recursive_Matrix(i, k) + Recursive_Matrix( k+1, j) +  ( P[i-1] * P[k] * P[j] );                         if( q < M[i][j])                                 M[i][j] = q;                 }         }         return M[i][j]; } void Print_M() {         for(int x = 1; x<= SIZE; x++)         {                 for(int y = 1; y <= SIZE; y++)                 {                         cout << M[x][y] << "  ";                 }                 cout << endl;         } }```
• 11-05-2002
Nick
The algorithm looks correct, have you tried the nonrecursive
one? You have to remember
that arrays in the book are 1-based while arrays in
c++ are 0-based.
• 11-05-2002
Stewdent
Nick, thanks for checking...

I had no problem implementing the nonrecursive algorithm

just banging my head with this one

maybe someone else will notice something
• 11-05-2002
Nick
You shouldn't have the global variables at the start.
• 11-05-2002
OneStiffRod
Why do you need a 2-dimensional array to hold the values of q???

Code:

```if( q < M[i][j])                                 M[i][j] = q;```
it doesn't seem like your incrementing the values of i or j so M[i][j] is always in the same postion.
• 11-05-2002
Nick
Does this work? Since you have SIZE matrices your going to
have SIZE + 1 dimensions P.

Code:

```#include <iostream> #include <cstdlib> using namespace std; const int SIZE = 7; const int MAX = 999999; int M[SIZE][SIZE]; // multiply // 1x1, 1x2, 2x3, 4x5, 6x7 int P[SIZE + 1] = { 1, 1, 2, 3, 4, 5, 6, 7}; int Recursive_Matrix(int i, int j); void Print_M(); int main() {     Recursive_Matrix( 1, SIZE - 1);     Print_M();     return 0; } int Recursive_Matrix(int i, int j) {     int q;     if( i == j )         return 0;     else     {         M[i][j] = MAX;         for(int k = i; k <= j - 1; k++)         {             q =  Recursive_Matrix(i, k);             q += Recursive_Matrix( k+1, j);             q +=  P[i-1] * P[k] * P[j];             if( q < M[i][j])         M[i][j] = q;         }     }     return M[i][j]; } void Print_M() {     for(int x = 0; x < SIZE; x++)     {         for(int y = 0; y < SIZE; y++)         {             cout << M[x][y] << "  ";         }         cout << endl;     } }```
• 11-05-2002
Nick
// 1x1, 1x2, 2x3, 4x5, 6x7
int P[SIZE + 1] = { 1, 1, 2, 3, 4, 5, 6, 7};

should be
// 1x1, 1x2, 2x3, 3x4, 4x5, 5x6, 6x7
• 11-05-2002
Nick
I did something wrong ...
• 11-05-2002
Stewdent
Nick, you don't have to make size+1

it works with your changing the structure of the statement that makes the recursive calls

i get the correct reults now, THANKS!

The parenthization is wrong, but i can fix that!

Code:

```Results: Recursive 0  0  0  0  0  0  0 0  0  15750  7875  9375  11875  15125 0  0  0  2625  4375  7125  10500 0  0  0  0  750  2500  5375 0  0  0  0  0  1000  3500 0  0  0  0  0  0  5000 0  0  0  0  0  0  0 0  1  2  3  4  5 0  0  2  3  4  5 0  0  0  3  4  5 0  0  0  0  4  5 0  0  0  0  0  5 (((((A1A2)A3)A4)A5)A6) Non-Recursive 0  15750  7875  9375  11875  15125 0  0  2625  4375  7125  10500 0  0  0  750  2500  5375 0  0  0  0  1000  3500 0  0  0  0  0  5000 0  1  1  3  3  3 0  0  2  3  3  3 0  0  0  3  3  3 0  0  0  0  4  5 0  0  0  0  0  5 ((A1(A2A3))((A4A5)A6)) ********************CODE #include <iostream> #include <cstdlib> using namespace std; const int SIZE = 7; const int MAX = 999999; int M[SIZE][SIZE]; int S[SIZE][SIZE]; // multiply // 1x1, 1x2, 2x3, 4x5, 6x7 //int P[SIZE + 1] = { 1, 1, 2, 3, 4, 5, 6, 7}; int P[SIZE] = {30,35,15,5,10,20,25}; int Recursive_Matrix(int i, int j); void Print_Optimal_Parens(int S[][SIZE], int i, int j); void Print_M(); void Print_S(); int main() {     Recursive_Matrix( 1, SIZE - 1);     Print_M();         cout << endl << endl;         Print_S();         cout << endl << endl;     Print_Optimal_Parens( S, 1, SIZE-1);         cout << endl << endl;     system("PAUSE");     return 0; } int Recursive_Matrix(int i, int j) {     int q;     if( i == j )         return 0;     else     {         M[i][j] = MAX;         for(int k = i; k <= j - 1; k++)         {             q =  Recursive_Matrix(i, k);             q += Recursive_Matrix( k+1, j);             q +=  P[i-1] * P[k] * P[j];             if( q < M[i][j])         M[i][j] = q;         S[i][j] = k;                 }     }     return M[i][j]; } void Print_M() {     for(int x = 0; x < SIZE; x++)     {         for(int y = 0; y < SIZE; y++)         {             cout << M[x][y] << "  ";         }         cout << endl;     } } void Print_Optimal_Parens(int S[][SIZE], int i, int j) {     if(i == j)                 cout << "A" << i;     else     {         cout << "(";         Print_Optimal_Parens(S, i, S[i][j]);         Print_Optimal_Parens(S, (S[i][j])+1, j);         cout << ")";     } } void Print_S() {         for(int x = 1; x<= SIZE-2; x++)         {                 for(int y = 1; y <= SIZE-1; y++)                 {                         cout << S[x][y] << "  ";                 }                 cout << endl;         } }```
• 11-05-2002
Nick
This version works. I thought you had SIZE for being
the number of matrices.

Code:

```#include <iomanip> #include <iostream> #include <cstdlib> using namespace std; const int SIZE = 6; const int MAX = 999999; int M[SIZE][SIZE]; // multiply // 1x1, 1x2, 2x3, 3x4, 4x5, 5x6, 6x7 int P[SIZE + 1] = { 30, 35, 15, 5, 10, 20, 25}; int Recursive_Matrix(int i, int j); void Print_M(); int main() {     Recursive_Matrix( 0, SIZE - 1);     Print_M();     return 0; } int Recursive_Matrix(int i, int j) {     int q;     if( i == j )         return 0;     else     {         M[i][j] = MAX;         for(int k = i; k <= j - 1; k++)         {             q =  Recursive_Matrix(i, k);             q += Recursive_Matrix( k+1, j);             q +=  P[i] * P[k + 1] * P[j + 1];             if( q < M[i][j])                 M[i][j] = q;         }     }     return M[i][j]; } void Print_M() {     for(int x = 0; x < SIZE; x++)     {         for(int y = 0; y < SIZE; y++)         {             cout << setw(7) << M[x][y];         }         cout << endl;     } }```