# matrix_chain_brute

matrix_chain_brute, a Python code which finds the cost of the most efficient ordering to use when multiplying a sequence of matrices, using brute force.

We are given a sequence of n matrices of conformable dimensions. Matrix Ai has D(i) rows and D(i+1) columns. The product A1 * A2 * ... * An is to be computed. In terms of scalar multiplications, the cost of computing A(i) * A(i+1) is D(i) * D(i+1) * D(i+2). We may carry out the pairs of multiplication in any order we wish. The total cost of the computation will, in general, vary depending on the order in which we compute the individual matrix multiplications. The goal of the algorithm is simply to determine the cost of the most efficient ordering.

Given n matrices, there are (n-1)! possible orderings for the sequence of matrix multiplications. The brute force approach considers each of these orderings, determines each cost, and reports the minimum.

### Languages:

matrix_chain_brute is available in a C version and a C++ version and a Fortran90 version and a MATLAB version and an Octave version and a Python version.

### Related Data and Programs:

closest_pair_brute, a Python code which uses brute force to solve a 2D version of the closest pair problem, which identifies the closest pair of points in a given collection.

knapsack_01_brute, a Python code which uses brute force to solve small versions of the 0/1 knapsack problem;

matrix_chain_dynamic, a Python code which finds the cost of the most efficient ordering to use when multiplying a sequence of matrices, using dynamic programming.

mxm, a Python code which sets up a matrix multiplication problem A=B*C of arbitrary size, and compares the time required for IJK, IKJ, JIK, JKI, KIJ and KJI orderings of the loops.

partition_brute, a Python code which uses brute force to find solutions of the partition problem, in which a set of integers must be split into two subsets with equal sum.

satisfy_brute, a Python code which uses brute force to find all assignments of values to a set of logical variables which make a complicated logical statement true.

subset_sum_brute, a Python code which uses brute force to solve the subset sum problem, to find a subset of a set of integers which has a given sum.

tsp_brute, a Python code which is given a city-to-city distance table, and solves a (small) traveling salesperson problem (TSP), using brute force.

### Reference:

1. Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein,
Introduction to Algorithms,
MIT Press, 2001,
ISBN: 978-0-262-03293-3,
LC: QA76.C662.
2. Matrix Chain Multiplication,