Matrix Chain Multiplication

Traditional Problems Dynamic Programming

We are given a sequence (chain) <A1,A2,A3,...,AN> of N matrices to be multiplied, and we wish to compute the product : A1A2A3...AN. We can evaluate the expression using the standard algorithm for multiplying pairs of matrices as a subroutine once we have paranthesized it to resolve all ambiguities in how the matrices are multiplied together. We will use the standard algorithm for multiplying matrices. If A is a p*q matrix and B is a q*r matrix, the resulting C is a p*r matrix, which requires p*q*r scalar multiplications.

A product of matrices is fully paranthesized if it is either a single matrix or the product of two fully paranthesized matrix products, surrounded by parantheses. Matrix multiplication is associative, and so all paranthesization yield the same product. But different paranthesization requires more scalar multiplication than the others.

Consider the problem of a chain <A1,A2,A3> of three matrices. Suppose that the dimensions of the matrices are 10*100, 100*5, and 5*50 respectively. If we multiply according to the paranthesization ((A1A2)A3), we perform 7500 scalar multiplications. If instead, we multiply according to the paranthesizaton (A1(A2A3)), we perform 75000 scalar multiplications. Thus, computing the product according to the first paranthesization is 10 times faster.

You are required to give the optimal paranthesization of a product that requires the minimal number of scalar multiplication.

The Input

The first line in the input will be an integer N, 1<=N<=100, the number of matrices in the chain. On the second line, there will be N+1 integer numbers for the elements of an array d, 1<=d[i]<=100, i=1..N+1. The dimension of the i-th matrix is d[i]*d[i+1]

The Output

The first line will be the optimum paranthesization of the matrices and the second line will be the number of scalar multiplication required to multiply the matrices according to the paranthesization.

Sample Input and Output

  Sample Input A            Sample Input B
  3                         6
  10 100 5 50               30 35 15 5 10 20 25

  Sample Output A           Sample Output B
  ((1*2)*3)                 ((1*(2*3))*((4*5)*6))
  7500                      15125

Solution :

Let x be the minimal number of scalar multiplication required to multiply matrices <AiAi+1Ai+2...Ak>. Let y be the minimal number of scalar multiplication required to multiply matrices <Ak+1Ak+2...Aj>. The result of multiplying matrix <AiAi+1Ai+2...Ak> is a d[i]*d[k+1] matrix, and the result of multiplying matrix <Ak+1Ak+2...Aj> is a d[k+1]*d[j+1] matrix. Let z be the cost of multiplying these matrices together, which is equal to d[i]*d[k+1]*d[j+1]. Thus we can multiply matrix <AiAi+1...Aj> for the cost of x+y+z. For each i and j, we will try to find the best k.
We will use a two dimentional array Best to make a record of the best paranthesizations. Best[i,j].Cost is the minimum cost to multiply matrices <AiAi+1...Aj>. Best[i,j].k is the best k for that chain.
yogy-n@sby.mega.net.id GeoCities