November 27

A reasonable question might be whether there is some easier way to calculate the optimal grouping of matrices (optimal BST structure, etc.) than the Dynamic Programming solution I presented.

In particular, a class of algorithms called greedy algorithms attempt to build up a solution to an optimization question one step at a time, never reconsidering a step once it has been taking (perhaps myopic algorithms would be a better name than greedy algorithms).

For example, in the case of grouping matrices for optimal multiplication, you might wonder whether you would get the optimal grouping by always choosing the top-level parenthesization so as to minimize (or, alternatively, maximize) the number of multiplications in the last step.

In the first case, consider matrices $A_0$, with dimensions $2\times 3$, $A_1$, with dimensions $3\times 4$, and $A_2$, with dimensions $4\times 3$. If we group them so that the last matrix multiplication is minimal, we get:

$$(A_0 (A_1 A_2))$$

...for a total of 54 multiplications. But the grouping

$$((A_0 A_1) A_2)$$

...yields 48 multiplications. So that greedy algorithms doesn't work.

The opposite approach (maximize the number of multiplications at the top level) runs into trouble with $A_0$ and $A_1$ having the same dimensions as previously, but $A_2$ having dimensions $4\times 2$. The greedy criterion leads to

$$((A_0 A_1) A_2)$$

...with 40 multiplications, versus 36 multiplications if we group the matrices:

$$(A_0 (A_1 A_2)).$$

So greediness doesn't work so far for matrix grouping. How about BST structure? A likely choice is to place the most frequent keys as high as possible, but that doesn't seem to work for key 'A' has frequency 3, key 'B' has frequency 2, and key 'C' has frequency 2.

Of course, these counterexamples don't prove that there doesn't exist any greedy algorithm for solving these problems, I've just dealt with the first ones that come to mind.