Show that the greedy choice of computing the cheapest multip

Show that the greedy choice of computing the cheapest multiplication at each step does not lead to an optimal solution for the matrix-chain multiplication problem

Solution

We show a counterexample for each greedy algorithm.
Assume we contain chain matrix multiplication M = A1 × A2 × A3, and the matrices A1, A2, A3 are of dimension p × q, q × r, r × s, in that order.
We attempt to set the dimensions p, q, r, s
the given algorithm chooses
M = (A1 × A2) × A3,
As the optimal solution is M = A1 × (A2 × A3).
M = A1 × (A2 × A3) is optimal qrs + pqs < pqr + prs.
(a) The algorithm prefers M = (A1 × A2) × A3 when
pqr < qrs p < s
Therefore, we set the dimensions as p = 2, q = 2, r = 10, s = 3 and we obtain
a counterexample.