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.

  1 2 3 4
1 0 M12 M13 M14
2   0 M23 M24
3     0 M34
4       0

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