2
$\begingroup$

I have been thinking about why the dynamic programming approach to finding the optimal matrix chain order is better than a brute force approach that finds the optimal order by exploring all nested orders. The more I think about it, the more I feel strongly that the dynamic programming solution considers all possible chain orders, thus contradicting the justification of choosing a dynamic programming approach to solving this problem.

For Eg. Lets consider a product of 4 matrices. There are 5 possible matrix chain orders (in the brute force method)

(A1 (A2 (A3 A4)))

(A1 ((A2 A3) A4))

((A1 A2) (A3 A4))

((A1 (A2 A3)) A4)

(((A1 A2) A3) A4)

Now, if we consider the dynamic programming approach all the sub matrix products included in each of the orders above will be computed. How then is the dynamic programming approach more efficient than the brute force approach?

EDIT: The answers and the comments have been really useful in helping me understand the DP solution better. But I am not able to visualise a brute force approach in my head. As soon as I start writing a brute force method to compute all possible matrix multiplication orders, the DP solution manifests itself naturally in my attempt. This may be because I know the optimized DP solution and I am not able to think of a rudimentary brute force solution. If someone can mention the pseudo code for generating all possible matrix multiplication orders , it will make it clearer as to what sub-problems the DP solution avoids and hence is more efficient.

EDIT (again): Let us disregard memoization. Will the DP solution still generate lesser number of computations?

$\endgroup$
  • 2
    $\begingroup$ The dynamic programming approach is faster, though you might have to look at a larger number than $4$. It doesn't explicitly consider all possible orders, but gathers enough data to find the best one. $\endgroup$ – Yuval Filmus Oct 19 '12 at 2:51
  • $\begingroup$ Notice in your example how orderings share sub-orderings. Instead of recomputing these subproblems, you can simply look them up in the table (or whatever appropriate data-structure is used to store results). $\endgroup$ – Nicholas Mancuso Oct 19 '12 at 14:54
  • 1
    $\begingroup$ This Wikipedia article on matrix chain multiplication describes both the dynamic programming algorithm and the more efficient Hu-Shing algorithm for this problem. $\endgroup$ – Peter Shor Oct 19 '12 at 16:29
  • 1
    $\begingroup$ If you disregard memoization, the dynamic programming algorithm (or at least the one described in Wikipedia), goes through each order exactly once. This means it is essentially a brute force solution, and not a dynamic programming algorithm. Memoization is the essence of dynamic programming. $\endgroup$ – Peter Shor Oct 21 '12 at 13:45
  • $\begingroup$ Peter is right! Write a recursive program: for any position $j$ it splits the sequence of matrices before and after $j$ and computes (recursively) the optimal solution for before and after parts. The sum of parts is the best solution for that $j$, so try at all $j$ to find overal best. This is recursion. Add memoization (never recompute the same segments) and voila it is dynamic programming. $\endgroup$ – Hendrik Jan Oct 21 '12 at 17:30
5
$\begingroup$

The dynamic programming solution computes a table that for each $i\le j$ has the optimal solution for $Ai$, ... $Aj$. The computation is done bottom-up, and (as one of the comments notes) many values are reused. Total complexity order $n^3$ as there is a quadratic number of $i,j$ each taking linear time to compute.

A real brute force takes exponential time, the number of binary trees, which is equal to the number of nested expressions. See Catalan numbers.

$\endgroup$
3
$\begingroup$

Your example may be too small. Consider the dynamic programming algorithm on 6 terms. Let's say that (A2 (A3 A4)) is better than ((A2 A3) A4). The dynamic programming algorithm is not going to compute any of the orders:

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

$\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.