2
$\begingroup$

We solve Matrix chain multiplication problem considering the optimal solution to subproblems but what I cant get through my mind is how this problem has an optimal substructure?

For eg. consider if these are optimal solutions for matrices A1.A2.A3.A4.A5.An:

(((((A1.A2)A3)A4)A5)A6)An)
(((((A1.A2)A3)A4)A5)(A6.An))

If any of above is optimal solution then we won't be able to consider any optimal substructre.No?

|cite|improve this question
$\endgroup$
  • $\begingroup$ It's unclear to me what your question is. You say "If any of above is optimal solution..." but how would you know it's optimal? You would have to compare it to other subsctructures like (((A1.A2)A3)(A4.A5))(A6.An) $\endgroup$ – Albert Hendriks Mar 24 '18 at 11:44
  • $\begingroup$ I was just assuming the worst case where the optimal solution is, let's assume, (((((A1.A2)A3)A4)A5)A6)An). This made me wonder if the problem actually had any substructure and we consider dp to solve it. But now I understood, if the optimal solution is any other solution that worst case, that has optimal substructure. $\endgroup$ – Sachin Verma Mar 24 '18 at 14:30
4
+25
$\begingroup$

First of all, it is correct and important to know that optimal solutions need not necessarily be unique! However, this doesn't mean we cannot have optimal substructure. Recall what optimal substructure means: the structure is such that if we know to make an 'optimal' decision on some 'local' criterion, we can get the actual 'global' optimum by making such decisions repeatedly (usually via divide and rule)

Note that again, the 'optimal' decision need not be unique! So, by making different locally optimal decisions, it is possible to end up with multiple globally optimal results. So, the seeming contradiction of multiple optima and optimal substructure doesn't exist.

|cite|improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.