## 2.2.2 MULTIPLICACIÓN DE UNA SECUENCIA DE MATRICES

Tenemos una secuencia (cadena) de n matrices a ser multiplicadas y queremos calcular el producto: A1A2...An.

Esto se puede resolver con una subrutina de multiplicación de pares de matrices una vez que se ha decidido el orden en que serán multiplicadas. La multiplicación de matrices es asociativa, así que cualquier orden dará el mismo resultado.

Por ejemplo, si tenemos la cadena , el producto ABCD se puede realizar de 5 formas distintas:

1. (A(B(CD)))

2. (A((BC)D))

3. ((AB)(CD))

4. ((A(BC))D)

5. (((AB)C)D)

Sin embargo, el orden tendrá un impacto dramático en el costo de realizar el producto.

Por ejemplo: 10 x 100, 100 x 5, 5 x 50.

- ((A1A2)A3) =(10X100X5) + (10X5X50) = 5000 + 2500 = 7,500
- (A1(A2A3) = (100X5X50) + (10X100X50) = 25000 + 50000 = 75,000

• Dada una cadena de n matrices, donde i=1,2,...,n la matriz Ai tiene dimensiones pi-1x pi, poner los paréntesis del producto minimizando el número de multiplicaciones escalares.

• No buscamos multiplicar las matrices sino minimizar el costo de la multiplicación en general.

Programación dinámica: producto de una cadena de matrices

Paso 1: estructura de una parentesización óptima.

• Sea Ai...j (i ≤ j) la matriz que resulta de evaluar la multiplicación de AiAi+1...Aj .

• Para i<j cualquer parentización del producto AiAi+1...Aj divide el producto entre Ak y Ak+1 para cualquier entrero en el rango i<=k<=j.

Esto es, para un valor de k calculamos primero los productos Ai..k y Ak+1..j y luego los multiplicamos para tener el producto final Ai..j

El costo de esta parentización es la suma de:

- el costo de calcular la matriz Ai..k, más
- el costo de calcular la matriz Ak+1..j, más
- el costo de multiplicar ambas matrices.

• La subestructura óptima de este problema es la siguiente:

• Supongase que una parentesización óptima de AiAi+1...Aj divide el producto entre Ak y Ak+1,

• La parentesización de la cadena AiAi+1...Ak dentro la parentesización óptima de AiAi+1...Aj debe ser la óptima.

• Mismo razonamiento para Ak+1Ak+2...Aj.

• Problema: encontrar el valor óptimo del valor de división k.

Paso 2: solución recursiva.

• Subproblema: determinar el costo mínimo de la parentesización de AiAi+1...Aj para 1 ≤ i ≤ j ≤ n.

• Sea m[i,j] el número mínimo de multiplicaciones de escalares necesarias para calcular el producto Ai...j. Para el problema entero el costo de la operación más eficiente para calcular A1...n es m[1,n].

• ¿Qué pasa con m[i,j] cuando i=j?

• El subproblema consta de una sola matriz Ai...i=i, no hay multiplicaciones y m[i,i]=0 para i=1,2,...,n.

• Para m[i,j] cuando i<j: (Ai tiene dimensiones pi-1 x pi para i=1,2,...,n).

- m[i,j] = m[i,k] + m[k+1,j] + pi-1pkpj.

No conocemos k pero solo hay j-i posibilidades a examinar.

• La definición recursiva es entonces:

m[i,j]= 0 si i=j;

min[[i,j] + m[k+1,j] + pi-1pkpj] si i<j.

y llamaremos s[i,j] al valor de k en el que dividimos AiAi+1...Aj para obtener una parentesización óptima.

Paso 3: cálculo de los costos óptimos

• Implementación con programación dinámica bottom-up.

• Ai tiene dimensiones pi-1 × pi para i=1,2,...,n.

• La entrada es una secuencia p, donde length[p] = n+1.

• Se utiliza la tabla auxiliar m[1...n, 1...n] para almacenar los m[i,j] costos.

• Se utiliza la tabla auxiliar s[1...n, 1...n] que almacene el índice de k que produjo los valores óptimos.

###