Question

Matrix-Chain Multiplication ProblemState and prove a theorem that establishes that the principle optimality holds for the Matrix-Chain Multiplication problem. (Input: p=(p0,p1,p2,...p????)giving the sizes p0×p1,p1×p2,...p????−1×p????of the matrices in a Matrix-Chain product ????1⋅????2⋯????????. Output: a parenthesization of the product that minimizes the number of real number multiplications that must be performed to computethe product.)In other words, show how and why an optimal parenthesization is composed of optimal parenthesization of subproducts.

Answer 1

Answer:

Some answers are attached below

Explanation:

The principle of optimality states that an optimal sequence of decisions has the property that whatever the initial state

and decision are, the remaining states must constitute an optimal decision sequence with regard to the state resulting from

the first decision.

Multiplication of matrix chain is an optimization problem. Here the goal is to find the most efficient way to multiply the

matrices. Matrix multiplication is associative. The problem is to find the way of matrix multiplication which involves less and

easy arithmetic operations. If each way of multiplication of matrix is verified, it would take a long time and the process will be

very slow when there are many matrices involved.

The solution to this is breaking up the problem into smaller sets of related matrices, so that solutions of sub problems can be

reused.

The dynamic programming algorithm is recursive and is as follows :

1. Split the given matrix expression in to two sub expressions.

2. Calculate the minimum cost of multiplying each sub sequence.

3. Add the costs together, to find it for the whole expression.

4. Repeat the same with the sub sequences and find the minimum cost of computation.

The results of each stage are stored so that they can be reused. Multiplying of two matrices involves the minimum cost.