Thread: Recursive Matrix Chain

  1. #1
    Stewdent
    Guest

    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;
    	}
    }

  2. #2
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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.

  3. #3
    Stewdent
    Guest
    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

  4. #4
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    You shouldn't have the global variables at the start.

  5. #5
    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.
    My Avatar says: "Stay in School"

    Rocco is the Boy!
    "SHUT YOUR LIPS..."

  6. #6
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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;
        }
    }

  7. #7
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    // 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

  8. #8
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    I did something wrong ...

  9. #9
    Stewdent
    Guest
    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;
    	}
    }

  10. #10
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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;
        }
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C - access violation
    By uber in forum C Programming
    Replies: 2
    Last Post: 07-08-2009, 01:30 PM
  2. Matrix Help
    By HelpmeMark in forum C++ Programming
    Replies: 27
    Last Post: 03-06-2008, 05:57 PM
  3. What is a matrix's purpose in OpenGL
    By jimboob in forum Game Programming
    Replies: 5
    Last Post: 11-14-2004, 12:19 AM
  4. Matrix and vector operations on computers
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 05-11-2004, 06:36 AM