Universidad Tecnológica Metropolitana

Facultad de Ingeniería

Dpto. de Informática

Multiplicación de Matrices

Profesor :

Asignatura :Análisis de Algoritmos

Alumno :

Fecha :16/05/2001

1.- Dadas las matrices A,B,C,D, encontrar los costos asociados al orden asociativo del producto.

Las dimensiones de las matrices son:

A[10x30], B[30x50], C[50x1], D[1x100]

(AxB)xC)xD = 16500

(AxB)x(CxD) = 70000

(Ax(BxC)xD = 2800

Ax((BxC)xD) = 34500

Ax(Bx(CxD) = 185000

2.- Para multiplicar n matrices M1,M2,M3...Mn.

¿ De cuantas formas distintas se puede realizar este producto?

¿ Encuentre y solucione la ecuación de recurrencia que tiene el problema?

El producto de n matrices se puede realizar de p maneras posibles:

Siendo M = M1xM2XM3x...xMn-1

P = [ 2(n - 2) ]! / ( (n - 2)! (n - 1)! )

Esto implica para el caso de 4 matrices que n-1=4 ! n=5

P = [ 2(5 - 3) ]! / ( (5 - 2)! (5 - 1)! ) ! P = 5

La ecuación de recurrencia de este problema, gira en lo que es el factorial de la formula propuesta.

T(n) = 2T(n - 2) / T(n - 2) x T(n - 1)

Se sabe que existe una única forma de multiplicar 2 matrices ! T(2) = 1.

3.- Aplicar la técnica divide para vencer, al problema de multiplicar n matrices, con costo optimo.

Si S es un conjunto de matrices, el problema de multiplicar con costo optimo reside solamente en decidir que matrices se han de multiplicar primero.

Si tomamos en cuenta que al multiplicar 2 matrices, solo existe una sola opción a seguir, por lo que un algoritmo no puede decidir como multiplicar 2 matrices, en cambio al tener 3 matrices, existen 2 formas de llevar a cabo la operación. Ahora si se pretende que el algoritmo decida como multiplicar 4 matrices eso, ya lleva tomar en cuenta 5 formas distintas de realizar dicha multiplicación.

Multiplicación( S, Conjunto de matrices )

{Si #S = 0

Ent (`Error')

Si #S = 1

Ent Retornar(S)

Si #S > 1

Ent

{Si #S es par

Ent

{Dividir a S en dos conjutos de igual tamaño (S1,S2)

Multiplicación(S1)

Multiplicación(S2)

S ! S1xS2

Retornar(S)

}

Si #S es impar

Ent

{Sn ! elemento central de S

S1 ! Las matrices anteriores a Sn

S2 ! Las matrices posteriores a Sn

Multiplicación(S1)

Multiplicación(S2)

Si S1xSn es costo menor //Implica conocer el costo de SnxS2

Ent S1!S1xSn //Esta comparación se hace

Sino S2!SnxS2 // en base a las dimensiones

S ! S1xS2 // de las matrices (pxqxr)

Retornar(S)

}

}

}

Para el caso de multiplicar 3 matrices, el algoritmo funciona bien, pero si se quieren multiplicar 4 matrices, el algoritmo realiza las siguientes llamadas:

S ={ A[10x30] B[30x50] C[50x1] D[1x100] }

Multiplicar(S)

#S es par

S1 = { A,B }

S2 = { C,D }

Multiplicar(S1 = { A,B })

#S es par

S1 = { A }

S2 = { B }

Multiplicar(S1 = { A })

#S = 1

Retornar(S = { A })

Multiplicar(S2 = { B })

#S = 1

Retornar(S = { B })

S = AB

Retornar(S1 = { AB })

Multiplicar(S2 = { C,D })

#S es par

S1 = { C }

S2 = { D }

Multiplicar(S1 = { C })

#S = 1

Retornar(S = { C })

Multiplicar(S2 = { D })

#S = 1

Retornar(S = { D })

S = CD

Retornar(S2 = { CD })

S = (AB)(CD)

Retornar( S = (ABCD)

Si nos damos cuenta, el algoritmo multiplico en (AB) primero y luego (BC) y por último los resultados de dicha multiplicación, obteniendo un costo de 70000 multiplicaciones y no el costo mínimo de 2800 operaciones.

Esto es debido a la concepción del algoritmo, ya que la decisión de multiplicar con costo mínimo se toma solo en el caso que n sea impar.

Si se realiza un pequeño cambio en el algoritmo, de tal manera que en el caso que #S sea par, se elija un a " #S, de tal manera que se formen dos grupos de conjunto, #S1 = a y #S2 = #S - a.

El problema que se enfrenta ahora es derechamente la elección de a, ¿cómo elijo a para que la multiplicación tenga costo mínimo?

Si intentamos analizar las dimensiones de las matrices e inferir que a se puede elegir para multiplicar con costo mínimo, nos podremos encontrar que para el caso de las cuatro matrices se tiene que, al multiplicar BC primero obtenemos un costo mínimo.

Para que el algoritmo hubiese realizado una multiplicación con el mínimo costo, era necesario que este dividiera a S en los conjuntos:

S1 = { A,B,C }, S2 = { D }, teniendo un costo de 2800 mínimo.

En base a esto, la elección de a radica en :

#S1 = a impar

#S2 = #S - a impar

De no ser posible la condición, se debe elegir a impar.

Lo que indudablemente es poca información ya que en base a estas ecuaciones se podrían haber elegido los conjuntos de la siguiente manera:

S1 = { A }, S2 = { B,C,D }, teniendo un costo de 34500.

Si generamos un conjunto S de 5 matrices, con dimensiones al azar, podremos observar lo siguiente:

S ={ A[57x34] B[34x83] C[83x11] D[11x85] E[85x45] }

S ={ A[21x66] B[66x72] C[72x79] D[79x49] E[49x54] }

S ={ A[54x36] B[36x12] C[12x76] D[76x81] E[81x41] }

S ={ A[62x86] B[86x70] C[70x36] D[36x45] E[45x23] }

Analizando visualmente estos gráficos, es obvio que la distribución del mínimo costo sigue un orden aleatorio, que habría que estimar, transformándose el problema en la estimación de un modelo estadístico, que permita determinar un valor a, de división del conjunto s, para que la multiplicación de matrices resulte con costo mínimo la gran mayoría de las veces (más de un 15% de las veces).

Para nuestro caso de 4 matrices S = { A,B,C,D }, podemos realizar alguna comparación rápida (costo irrelevante), de tal manera que esta nos pueda entregar una pista sobre la división de el conjunto S, para así aplicar el algoritmo anterior.

No olvidar que S ={ A[10x30] B[30x50] C[50x1] D[1x100] }

De esta manera se puede inferir que el menor costo esta asociado hacia el lado izquierdo del conjunto S, de esta manera se puede elegir una a = 3, que involucra a los vértices A,B,C.

S1 = { A,B,C }

S2 = { D }

El algoritmo planteado anteriormente, multiplica con costo mínimo a un conjunto de 3 matrices.

Si tenemos un conjunto de 5 matrices, cuales quiera, de tal manera que, basándose en los principios de programación dinámica, se puedan elegir las tres mejores matrices a multiplicar.

Si S ={ A[57x34] B[34x83] C[83x11] D[11x85] E[85x45] }, si llevamos a cabo el calculo propuesto anteriormente obtendríamos que:

ABC = 57x34x83x11 = 1769394

BCD = 34x83x11x85 = 2638570

CDE = 83x11x85x45 = 3492225

Por lo que las mejores 3 matrices a multiplicar primero son ABC, si aplicamos el algoritmo de multiplicación propuesto, se obtiene que el orden de multiplicación es:

Ax(BxC) = 52360, ABC[57x11]

Si restablecemos nuestra lista, se obtiene que:

Esto implica que queda una única opción de aplicación del algoritmo de multiplicación, comportándose de la siguiente manera:

ABCx(DxE) = 70290, ABCDE[57x45]

Por lo que el costo total otorgado por este método es de 122650

Si hallamos el costo mínimo de la multiplicación de estas 5 matrices, esta resulta ser:

(Ax(BxC))x(DxE) = 122650

De tal manera, de que la combinación entre los mejores triángulos y el algoritmo de multiplicación de 3 matrices resulta entregar el costo mínimo.

Multiplicación( S, Conjunto de matrices )

{Si #S = 0

Ent (`Error')

Si #S = 1

Ent Retornar(S)

Si #S = 2

Ent

{ Dividir a S en dos conjuntos iguales de un elemento cada uno S1,S2

S ! S1xS2

Retornar(S)

}

Si #S = 3

Ent

{Sn ! elemento central de S

S1 ! La matriz anterior a Sn

S2 ! La matriz posterior a Sn

Si S1xSn es costo menor

Ent S1 ! S1xSn

Sino S2 ! SnxS2

S ! S1xS2

Retornar(S)

}

Si #S > 3

Ent

{ Elegir las mejores 3 matrices y dividir el conjunto de la siguiente manera

Si las mejores 3 matrices están al inicio

Ent

{S1 ! Tres mejores matrices

S2 ! El resto de matrices.

Multiplicación(S1)

S ! S1 + S2.

}

Si las mejores matrices están al final

Ent

{S2 ! Tres mejores matrices

S1 ! El Resto de matrices.

Multiplicación(S2)

S ! S1 + S2

}

Si las mejores matrices están en el centro

Ent

{Sn ! Tres mejores matrices

S1 ! Las matrices anteriores

S2 ! Las matrices posteriores

Multiplicación(Sn)

S ! S1 + Sn +S2

}

Multiplicación(S)

Retornar(S)

}

}

Este Algoritmo permite multiplicar n matrices con un costo mínimo.

A

B

C

D

B

10x30x50x1

A

30x50x1x100

E

D

C

D

ABC

E