Solucion al problema de
El Orden de Multiplicacion de una cadena de Matrices
Usando Programacion Dinamica
La cadena de matrices separadas por coma sigue el patron del ejemplo:
Si se tienes las siguientes matrices con los siguientes tamanos :
A01 34x45
A02 45x12
A03 12x10
Se introduce la siguiente cadena:
M':34,45,12,10
Y la siguiente expresion:
((A01)(A02A03))
Codigo Fuente
La solución dinámica, a este problema implica trabajar de forma
ascendente memorizando los resultados de los subproblemas parciales para evitar
reprocesamiento. En primer lugar, solo hay una forma de multiplicar M1 por M2,
M2 por M3, ..., M(n-1) por Mn, guardar los costos optimos en la matriz de costos "M"
y el orden de esa operacion en la matriz "S" que contiene las Pocisiones de Corte de
la cadena.
Por ejemplo, para encontrar la mejor forma de multiplicar (M1) (M2) (M3), primero se
encuntra el costo de multiplicar (M1) (M2) en la tabla que memoriza y luego se anade
el costo de multiplicar el resultado por M3. Este total se compara con el costo
de multiplicar primero (M2) (M3), y luego multiplicar por M1, lo que se puede calcular
de la misma forma.
El menor de estos se memoriza, y se sigue el mismo procedimiento para todos los
demas, evitando asi recalcular subproblemas traslapados.