CODEWITHSUNDEEP
algorithmmathdata-structuresdynamic-programmingmatrix-multiplication
user4627889
user4627889

Reputation:

Matrix-chain Multiplication and a bit different problems?

We know Matrix-chain Multiplication Problem. My professor solve one close problem as:

We want to find an order of Matrix multiplication such that number of elements in middle matrixes (calculated in all steps of production) is minimized (we called it cost of production). We have A_1*A_2*A_3*...* A_n and dimension A_i is on d_{i-1} and d_i. C_{ij} = min cost of production A_i*...*A_j sub problems and C_{ii}=0. he says the relation for solving this problem is:

C_{ij}=min i<=k < j  max{C_{ik}, C_{k+1,j}, d_{i-1}*d_j}

I couldent get it, what is the idea behind this relation? how can help me ?

Upvotes: 3

Views: 324

Answers (1)

kraskevich
kraskevich

Reputation: 18576

Let's assume that we want to minimize C(i, j). What can we choose? We can choose the position of the last multiplication we will perform. When it is fixed, we have two independent subproblems(everything before the last multiplication and everything after it). So the equation C_{ij}=min i<=k < j max{C_{ik}, C_{k+1,j}, d_{i-1}*d_j} in plain English means:

  1. Let's choose the position of the last multiplication and denote it is k.

  2. Let's solve two subproblems: one for (i, k) and another one for (k + 1, j).

  3. For a fixed k, the answer is maximum of the results for these two subproblems and the size of the final matrix which we get after multiplying all matrices in (i, j) range(namely, d_{i-1}*d_j, and it does not depend on the order of multiplication).

  4. We want to minimize the result, so we choose the smallest value among all valid k.

That's it.

Upvotes: 1

Related Questions