Las Matrices (2º Bachillerato; Ciencias y Tecnología)

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