Optimización del Producto de Matrices
El siguiente texto fue trasladado desde Wikipedia, bajo el título "Optimización del Producto de Matrices", para más detalles de los autores originales ver la discusión
Objetivo
[editar]Minimizar el coste de realizar la multiplicación de n matrices.
Descripción
[editar]El producto de un número n de matrices es optimizable en cuanto al número de multiplicaciones escalares requeridas. A la hora de multiplicar una serie de matrices se puede elegir en que orden queremos realizar las multiplicaciones entre estas. Se pueden realizar en un orden cualquiera dada la propiedad asociativa de la multiplicación.
Ejemplo:
Para cuatro matrices dadas A, B, C y D. Las posibilidades de realizar
el calculo son las siguientes:
1. ((A*B)*C)*D
2. (A*(B*C))*D
3. A*((B*C)*D)
4. A*(B*(C*D))
5. (A*B)*(C*D)
Decidamos el orden que decidamos el resultado siempre es el mismo. La diferencia esta en el número de multiplicaciones que implica elegir un orden u otro. Al multiplicar dos matrices M1 de tamaño nxm y M2 de tamaño mxk el número de multiplicaciones escalares es n*m*k. La cantidad total de multiplicaciones será, la suma de todas las multiplicaciones que hacen falta para multiplicar cada submatriz obtenida como resultado con la siguiente en el orden escogido. Y como vamos a ver en este sencillo ejemplo esta cantidad puede variar con el orden utilizado.
Ejemplo:
Para el ejemplo anterior con tamaños para las matrices A (13x5), B(5x89),
C(89x3) y D(3x34). La cantidad de multiplicaciones para cada orden es el
siguiente:
1. ((A*B)*C)*D --> 13*5*89 + 13*89*3 + 13*3*34 = 10582
2. (A*(B*C))*D --> 5*89*3 + 13*5*3 + 13*3*34 = 2856
3. A*((B*C)*D) --> 5*89*3 + 5*3*34 + 13*5*34 = 4055
4. A*(B*(C*D)) --> 89*3*34 + 5*89*34 + 13*5*34 = 26418
5. (A*B)*(C*D) --> 13*5*89 + 89*3*34 + 13*89*34 = 54201
Eligiendo un orden adecuado como podemos ver, optimizamos el coste de realizar las multiplicaciones escalares necesarias para llegar al resultado. Para encontrar el modo de ordenar las multiplicaciones vamos a utilizar un algoritmo de Programación Dinámica.
Esquema
[editar]Como vamos a emplear Programación Dinámica, buscamos que todas las subsoluciones sean óptimas, porque se debe de cumplir el principio de optimalidad de Bellman. Esto quiere decir que si la solución es buscar la forma de realizar la multiplicación de n matrices, una posible subsolución será multiplicar desde la matriz i hasta la j. El número mínimo de multiplicaciones necesarias para hallar la subsolución óptima de i a j será Mij. Si tenemos que ir calculando todas las subsoluciones hasta encontrar la M1n que es la que andamos buscando, necesitaremos una tabla de nxn donde iremos almacenando los resultados.
|
Como la i y la j cumplen que 1 <= i <= j <= n solo vamos a utilizar la mitad superior derecha de la tabla en donde se cumple la restricción. En las Mij donde la i=j, se cumple que Mij=0. Tal y como hemos definido Mij es el número de multiplicaciones escalares necesarias para obtener el resultado de multiplicar desde la matriz i hasta la j, si i y j son iguales significa que no se realiza ninguna operación porque solo tenemos una matriz. La tabla empleada para realizar los cálculos tendría la forma que muestra la imagen. |
|
Para hallar cada subsolución aplicamos la siguiente función que minimiza el coste total en número de multiplicaciones:
Mij = { min( Mik + M(k+1)j + ti-1 * tk * tj ) | para todo k siendo i<=k<=j }
Algoritmo de PD
[editar] fun Mult_Mat_PD(dimMatriz[0..n]: ent) dev sol:ent //Donde n es la dimension de la matriz solución,
var es decir, el número de matrices a solucionar
matrizSol[1..n,1..n]: ent; //Matriz solución
fvar
para i=1 hasta n hacer
matrizSol[i][i]=0; //Inicializa la diagonal principal a 0
fpara
para diagonal=1 hasta n-1 hacer
para i=0 hasta n-diagonal hacer
matrizSol[i,i+diagonal]=minProd(dimMatriz,matrizSol,i,i+diagonal);
//En cada casilla de cada diagonal escribe el su
correspondiente mínimo de multiplicaciones necesaria
fpara
fpara
dev matrizSol[0,n]);
ffun
fun minProd(dimMatriz[1..n]: ent,matrizSol[1..n,1..n]: ent,i,j: ent) dev minP:ent
var
aux: ent;
fvar
minP=+infinito;
para k=i hasta j-1 hacer
aux=matrizSol[i,k]+matrizSol[k+1,j]+(dimMatriz[i-1]*dimMatriz[k]*dimMatriz[j]);
si (aux<minP) entonces
minP=aux; //Actualiza si el número de multiplicaciones es menor
fsi
fpara
dev minP;
ffun