matrix_chain_order.c File Reference

Matrix Chain Order More...

#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

Include dependency graph for matrix_chain_order.c:

Functions
int	matrixChainOrder (int l, const int *p, int *s)
	for assert for INT_MAX macro
void	printSolution (int l, int *s, int i, int j)
	Recursively prints the solution.
static void	test ()
	Self-test implementations.
int	main ()
	Main function.

Detailed Description

Matrix Chain Order

From Wikipedia: Matrix chain multiplication (or the matrix chain ordering problem) is an optimization problem concerning the most efficient way to multiply a given sequence of matrices. The problem is not actually to perform the multiplications, but merely to decide the sequence of the matrix multiplications involved.

Author

CascadingCascade

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0

{
    test();  // run self-test implementations
    return 0;
}

Here is the call graph for this function:

matrixChainOrder()

int matrixChainOrder	(	int	l,
		const int *	p,
		int *	s
	)

for assert for INT_MAX macro

for IO operations for malloc() and free()

Finds the optimal sequence using the classic O(n^3) algorithm.

Parameters

l	length of cost array
p	costs of each matrix
s	location to store results

Returns

number of operations

{
    // mat stores the cost for a chain that starts at i and ends on j (inclusive
    // on both ends)
    int **mat = malloc(l * sizeof(int *));
    for (int i = 0; i < l; ++i)
    {
        mat[i] = malloc(l * sizeof(int));
    }
 
    for (int i = 0; i < l; ++i)
    {
        mat[i][i] = 0;
    }
    // cl denotes the difference between start / end indices, cl + 1 would be
    // chain length.
    for (int cl = 1; cl < l; ++cl)
    {
        for (int i = 0; i < l - cl; ++i)
        {
            int j = i + cl;
            mat[i][j] = INT_MAX;
            for (int div = i; div < j; ++div)
            {
                int q = mat[i][div] + mat[div + 1][j] + p[i] * p[div] * p[j];
                if (q < mat[i][j])
                {
                    mat[i][j] = q;
                    s[i * l + j] = div;
                }
            }
        }
    }
    int result = mat[0][l - 1];
 
    // Free dynamically allocated memory
    for (int i = 0; i < l; ++i)
    {
        free(mat[i]);
    }
    free(mat);
 
    return result;
}

printSolution()

void printSolution	(	int	l,
		int *	s,
		int	i,
		int	j
	)

Recursively prints the solution.

Parameters

l	dimension of the solutions array
s	solutions
i	starting index
j	ending index

Returns

void

{
    if (i == j)
    {
        printf("A%d", i);
        return;
    }
    putchar('(');
    printSolution(l, s, i, s[i * l + j]);
    printSolution(l, s, s[i * l + j] + 1, j);
    putchar(')');
}

Here is the call graph for this function:

test()

static void test ( void  )

static

Self-test implementations.

Returns

void

{
    int sizes[] = {35, 15, 5, 10, 20, 25};
    int len = 6;
    int *sol = malloc(len * len * sizeof(int));
    int r = matrixChainOrder(len, sizes, sol);
    assert(r == 18625);
    printf("Result : %d\n", r);
    printf("Optimal ordering : ");
    printSolution(len, sol, 0, 5);
    free(sol);
 
    printf("\n");
}

Here is the call graph for this function: