com.mhhe.clrs2e
Class MatrixChainMultiply

java.lang.Object
  |
  +--com.mhhe.clrs2e.MatrixChainMultiply

public class MatrixChainMultiply

extends java.lang.Object

Implements the dynamic-programming algorithm to determine the optimal order in which to multiply a chain of matrices, as described in Section 15.2 of Introduction to Algorithms, Second edition.

Field Summary

private int[][]	m The value of an optimal solution to a subproblem.
private int	n How many matrices are in the chain.
private int[][]	s The position to split an optimal solution to a subproblem.

Constructor Summary

MatrixChainMultiply(int[] p)
Computes an optimal parenthesization of a matrix-chain product, allocating the instance variables and storing the result in them.

Method Summary

private void	matrixChainOrder(int[] p) Computes an optimal parenthesization of a matrix-chain product, storing the result in the instance variables.
private java.lang.String	printOptimalParens(int i, int j) Returns a String describing an optimal parenthesization of a subproblem.
java.lang.String	toString() Returns a String describing an optimal parenthesization of the entire matrix chain.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

m

private int[][] m

The value of an optimal solution to a subproblem. m[i][j] is the minimum number of scalar multiplications needed to compute A_i A_i+1 ... A_j, for 1 ≤ i ≤ j ≤ n. Entries m[i][j] for i = 0, j = 0, or i > j are unused.

s

private int[][] s

The position to split an optimal solution to a subproblem. s[i][j] is an index k such that m[i][j] = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j], for i = 1, 2, ..., n-1 and j = 2, 3, ..., n. Entries s[i][j] for i = 0, i = n, j ≤ 1, or i > j are unused.

n

private int n

How many matrices are in the chain.

Constructor Detail

MatrixChainMultiply

public MatrixChainMultiply(int[] p)

Computes an optimal parenthesization of a matrix-chain product, allocating the instance variables and storing the result in them.

Parameters:

p - An array of dimensions, where matrix A_i is p[i-1] x p[i], for i = 1, 2, ..., n.

Method Detail

matrixChainOrder

private void matrixChainOrder(int[] p)

Computes an optimal parenthesization of a matrix-chain product, storing the result in the instance variables. The instance variables are assumed to be already allocated. Implements the Matrix-Chain-Order procedure on page 336.

Parameters:

p - An array of dimensions, where matrix A_i is p[i-1] x p[i], for i = 1, 2, ..., n.

printOptimalParens

private java.lang.String printOptimalParens(int i,
                                            int j)

Returns a String describing an optimal parenthesization of a subproblem. Implements the Print-Optimal-Parens procedure on page 338.

Parameters:

i - Index of one array.

j - Index of another array.

Returns:

A String describing an optimal parenthesization of A_i A_i+1 ... A_j.

toString

public java.lang.String toString()

Returns a String describing an optimal parenthesization of the entire matrix chain.

Overrides:

toString in class java.lang.Object