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

Minimizar el coste de realizar la multiplicación de n matrices.

Descripción

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 M₁ de tamaño nxm y M₂ 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

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á M_ij. Si tenemos que ir calculando todas las subsoluciones hasta encontrar la M_1n 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 M_ij donde la i=j, se cumple que M_ij=0. Tal y como hemos definido M_ij 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.

	1	2	3	4
1	0	M₁₂	M₁₃	M₁₄
2		0	M₂₃	M₂₄
3			0	M₃₄
4				0

Para hallar cada subsolución aplicamos la siguiente función que minimiza el coste total en número de multiplicaciones:

       M_ij = { min( M_ik + M_(k+1)j + t_i-1 * t_k * t_j )   |    para todo k  siendo  i<=k<=j }

Algoritmo de PD

 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