0
$\begingroup$

I want to develop an algorithm which finds the optimal sequence of multiplications to multiply n matrices. For example, if we have:

M1 x M2 x M3 x M4 x M5 x Mn

The algorithm should place the optimal parenthesis to reduce overall number of scalar multiplications. For example, a possible output may be:

(M1 x M2) x (M3 x M4 x (M5 x Mn))

I realize we can place the parenthesis after finding an order for all of the multiplication (x) operators to operate in.

There is certainly a cost associated with each multiplication:

Cost (M1,M2) = rows(M1) x columns(M1) or rows(M2) x columns(M2)

At each step, if we find the subproblem associated with each (x) operator. For example, at the first step, we have:

OPT(do M1 x M2 first)
OPT(do M2 x M3 first)
OPT(do M3 x M4 first)
OPT(do M4 x M5 first)
OPT(do M5 x Mn first)

The problem is, that the number of OPTimal subproblems is not a fixed number. Normally, in a dynamic programming algorithm, we have a fixed number of OPT operations of which we take min or max of.

Is it valid to take n (variable number of) OPT operations in a dynamic programming algorithm?

P.S. I realize another feature of dynamic programming algorithms is the ability to memoize. We can certainly memoize since we will have repeated subproblems through different paths. For example, the following set of parenthesis can be approached through two different paths:

(M1 x M2) x (M3 x M4) x M5 x Mn

  1. Do M1 x M2 first then do M3 x M4
  2. Do M3 x M4 first then do M1 x M2
$\endgroup$
  • $\begingroup$ This is a classic problem solvable with dynamic programming, covered in many standard algorithms textbooks. I suggest you do some reading and/or searching and you'll probably find a description of how to solve it. $\endgroup$ – D.W. Mar 22 '18 at 19:18
  • 1
    $\begingroup$ Normally, in a dynamic programming algorithm, we have a fixed number of OPT operations of which we take min or max of. This is only true for algorithms you have seen so far. Dynamic programming is in fact more general, as the problem at hand shows. $\endgroup$ – Yuval Filmus Mar 23 '18 at 8:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.