Page 1 of 1
1. Consider the following greedy approach to the matrix-chain multiplication problem: Whenever there are at least 3 matr
Posted: Thu Jun 30, 2022 7:39 pm
by answerhappygod
- 1 Consider The Following Greedy Approach To The Matrix Chain Multiplication Problem Whenever There Are At Least 3 Matr 1 (19.79 KiB) Viewed 26 times
1. Consider the following greedy approach to the matrix-chain multiplication problem: Whenever there are at least 3 matrices (A, ... Aj, j — i ≥ 2) remaining, always split the chain at k: (A₁...Ak)(Ak+1 ...Aj), such that Pk is the smallest number among {pi, ..., Pj-1}. Prove that this greedy approach doesn't always give optimal solution.