-
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;
}
}
-
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.
-
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
-
You shouldn't have the global variables at the start.
-
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.
-
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;
}
}
-
// 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
-
I did something wrong ...
-
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;
}
}
-
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;
}
}