5.3.3. Multiplicación encadenada de matrices.
Ejemplo. Sean las matrices A, B, C y D, de dimensiones: A= 13x5, B= 5x89, C= 89x3 y D= 3x34. Podemos multiplicarlas de 5 formas:
- ((AB)C)D Requiere 10.582 = 13·5·89 + 13·89·3 + 13·3·34
- (AB)(CD) “ 54.201
- (A(BC))D “ 2.856 = 5·89·3 + 13·5·3 + 13·3·34
- A((BC)D) “ 4.055
- A(B(CD)) “ 26.418
Objetivo: obtener un orden de multiplicación que minimice el número de multiplicaciones escalares.
Solución sencilla: estimar el número de multiplicaciones necesarias para todas las ordenaciones posibles. Quedarse con la que tenga menor valor.
¿Cuál es el número de ordenaciones posibles, T(n)?