La multiplicación de matrices en cadena (o el problema de ordenamiento de matrices en cadena [1] ) es un problema de optimización que se ocupa de la forma más eficiente de multiplicar una secuencia dada de matrices . El problema no consiste en realizar las multiplicaciones, sino simplemente en decidir la secuencia de las multiplicaciones de matrices involucradas. El problema se puede resolver utilizando programación dinámica .
Existen muchas opciones porque la multiplicación de matrices es asociativa . En otras palabras, no importa cómo se ponga entre paréntesis el producto , el resultado obtenido será el mismo. Por ejemplo, para cuatro matrices A , B , C y D , existen cinco opciones posibles:
Aunque no afecta al producto, el orden en el que se ponen los términos entre paréntesis afecta el número de operaciones aritméticas simples necesarias para calcular el producto, es decir, la complejidad computacional . La multiplicación sencilla de una matriz que es X × Y por una matriz que es Y × Z requiere multiplicaciones ordinarias XYZ y sumas ordinarias X ( Y − 1) Z. En este contexto, es típico utilizar el número de multiplicaciones ordinarias como una medida de la complejidad en tiempo de ejecución.
Si A es una matriz de 10 × 30, B es una matriz de 30 × 5 y C es una matriz de 5 × 60, entonces
Claramente, el primer método es más eficiente. Con esta información, el enunciado del problema puede refinarse como "¿cómo determinar la paréntesis óptima de un producto de n matrices?". El número de paréntesis posibles está dado por el ( n –1) ésimo número de Catalan , que es O (4 n / n 3/2 ), por lo que comprobar cada paréntesis posible ( fuerza bruta ) requeriría un tiempo de ejecución exponencial en el número de matrices, lo que es muy lento y poco práctico para n grandes . Se puede lograr una solución más rápida a este problema dividiendo el problema en un conjunto de subproblemas relacionados.
Para empezar, supongamos que lo único que realmente queremos saber es el coste mínimo, o el número mínimo de operaciones aritméticas necesarias para multiplicar las matrices. Si solo estamos multiplicando dos matrices, solo hay una forma de hacerlo, por lo que el coste mínimo es el coste de realizar esta operación. En general, podemos encontrar el coste mínimo utilizando el siguiente algoritmo recursivo :
Por ejemplo, si tenemos cuatro matrices ABCD , calculamos el costo requerido para encontrar cada una de ( A )( BCD ), ( AB )( CD ) y ( ABC )( D ), haciendo llamadas recursivas para encontrar el costo mínimo para calcular ABC , AB , CD y BCD . Luego elegimos la mejor. Mejor aún, esto produce no solo el costo mínimo, sino que también demuestra la mejor manera de hacer la multiplicación: agruparla de la manera que produce el costo total más bajo y hacer lo mismo para cada factor.
Sin embargo, este algoritmo tiene una complejidad de ejecución exponencial que lo hace tan ineficiente como el enfoque ingenuo de probar todas las permutaciones. La razón es que el algoritmo realiza mucho trabajo redundante. Por ejemplo, arriba hicimos una llamada recursiva para encontrar el mejor costo para calcular ABC y AB . Pero encontrar el mejor costo para calcular ABC también requiere encontrar el mejor costo para AB . A medida que la recursión se vuelve más profunda, se produce cada vez más de este tipo de repetición innecesaria.
Una solución sencilla se llama memorización : cada vez que calculamos el coste mínimo necesario para multiplicar una subsecuencia específica, lo guardamos. Si alguna vez nos piden que lo calculemos de nuevo, simplemente damos la respuesta guardada y no la volvemos a calcular. Dado que hay alrededor de n 2 /2 subsecuencias diferentes, donde n es el número de matrices, el espacio necesario para hacer esto es razonable. Se puede demostrar que este sencillo truco reduce el tiempo de ejecución a O( n 3 ) desde O(2 n ), lo que es más que suficiente para aplicaciones reales. Esto es programación dinámica de arriba hacia abajo .
El siguiente enfoque ascendente [2] calcula, para cada 2 ≤ k ≤ n, los costos mínimos de todas las subsecuencias de longitud k utilizando los costos de subsecuencias más pequeñas ya calculadas. Tiene el mismo tiempo de ejecución asintótico y no requiere recursión.
Pseudocódigo:
// La matriz A[i] tiene dimensión dims[i-1] x dims[i] para i = 1..n MatrixChainOrder ( int dims [] ) { // length[dims] = n + 1 n = dims.length - 1 ; // m [i,j] = Número mínimo de multiplicaciones escalares (es decir, costo) // necesarias para calcular la matriz A[i]A[i+1]...A[j] = A[i..j] // El costo es cero al multiplicar una matriz para ( i = 1 ; i <= n ; i ++ ) m [ i , i ] = 0 ; for ( len = 2 ; len <= n ; len ++ ) { // Longitudes de subsecuencia for ( i = 1 ; i <= n - len + 1 ; i ++ ) { j = i + len - 1 ; m [ i , j ] = MAXINT ; for ( k = i ; k <= j - 1 ; k ++ ) { cost = m [ i , k ] + m [ k + 1 , j ] + dims [ i - 1 ]* dims [ k ]* dims [ j ] ; if ( cost < m [ i , j ] ) { m [ i , j ] = cost ; s [ i , j ] = k ; // Índice de la división de subsecuencia que logró el costo mínimo } } } } } Una implementación de Python que utiliza el decorador de memorización de la biblioteca estándar:
desde functools importar cachédef matrixChainOrder ( dims : lista [ int ]) -> int : @cache def a ( i , j ): devuelve min (( a ( i , k ) + dims [ i ] * dims [ k ] * dims [ j ] + a ( k , j ) para k en el rango ( i + 1 , j )), predeterminado = 0 ) devuelve un ( 0 , len ( dims ) - 1 )Hay algoritmos que son más eficientes que el algoritmo de programación dinámica O ( n 3 ), aunque son más complejos.
Un algoritmo publicado por TC Hu y M.-T. Shing logra una complejidad computacional de O ( n log n ) . [3] [4] [5] Demostraron cómo el problema de multiplicación de cadenas de matrices se puede transformar (o reducir ) en el problema de triangulación de un polígono regular . El polígono está orientado de tal manera que hay un lado inferior horizontal, llamado base, que representa el resultado final. Los otros n lados del polígono, en el sentido de las agujas del reloj, representan las matrices. Los vértices en cada extremo de un lado son las dimensiones de la matriz representada por ese lado. Con n matrices en la cadena de multiplicación hay n −1 operaciones binarias y C n −1 formas de colocar paréntesis, donde C n −1 es el ( n −1)-ésimo número de Catalan . El algoritmo explota que también hay C n −1 posibles triangulaciones de un polígono con n +1 lados.
Esta imagen ilustra posibles triangulaciones de un hexágono regular . Estas corresponden a las diferentes formas en que se pueden colocar los paréntesis para ordenar las multiplicaciones de un producto de 5 matrices.
En el ejemplo que se muestra a continuación, hay cuatro lados: A, B, C y el resultado final ABC. A es una matriz de 10×30, B es una matriz de 30×5, C es una matriz de 5×60 y el resultado final es una matriz de 10×60. El polígono regular de este ejemplo es un cuadrágono, es decir, un cuadrado:
El producto matricial AB es una matriz de 10 x 5 y BC es una matriz de 30 x 60. Las dos triangulaciones posibles en este ejemplo son:
El costo de un solo triángulo en términos del número de multiplicaciones necesarias es el producto de sus vértices. El costo total de una triangulación particular del polígono es la suma de los costos de todos sus triángulos:
Hu y Shing desarrollaron un algoritmo que encuentra una solución óptima para el problema de partición de costo mínimo en tiempo O ( n log n ). Su prueba de corrección del algoritmo se basa en el "Lema 1", demostrado en un informe técnico de 1981 y omitido del artículo publicado. [6] [4] La prueba del lema en el informe técnico es incorrecta, pero Shing ha presentado una prueba corregida. [1]
Wang, Zhu y Tian han publicado un algoritmo simplificado O ( n log m ), donde n es el número de matrices en la cadena y m es el número de mínimos locales en la secuencia de dimensiones de la cadena de matrices dada. [7]
Nimbark, Gohel y Doshi han publicado un algoritmo codicioso O ( n log n ), [8] pero su prueba de optimalidad es incorrecta y su algoritmo no produce la asignación de paréntesis más eficiente para algunas cadenas de matrices. [1]
Un algoritmo creado independientemente por Chin [9] y Hu & Shing [10] se ejecuta en O( n ) y produce una paréntesis que es como máximo un 15,47 % peor que la opción óptima. En la mayoría de los casos, el algoritmo produce la solución óptima o una solución que es solo un 1-2 % peor que la óptima. [5]
El algoritmo comienza trasladando el problema al problema de partición de polígonos. A cada vértice V del polígono se le asocia un peso w . Supongamos que tenemos tres vértices consecutivos , y que ese es el vértice con el peso mínimo . Observamos el cuadrilátero con vértices (en el sentido de las agujas del reloj). Podemos triangularlo de dos maneras:
Por lo tanto, si
o equivalentemente
Eliminamos el vértice del polígono y añadimos el lado a la triangulación. Repetimos este proceso hasta que no se cumpla la condición anterior. Para todos los vértices restantes , añadimos el lado a la triangulación. Esto nos da una triangulación casi óptima.
El problema de la multiplicación de cadenas de matrices se generaliza para resolver un problema más abstracto: dada una secuencia lineal de objetos, una operación binaria asociativa sobre esos objetos y una forma de calcular el costo de realizar esa operación sobre cualesquiera dos objetos dados (así como todos los resultados parciales), calcule la forma de costo mínimo de agrupar los objetos para aplicar la operación sobre la secuencia. [11] Un ejemplo práctico de esto proviene del ordenamiento de las operaciones de unión en bases de datos ; consulte Optimización de consultas § Ordenamiento de unión .
Otro caso especial un tanto artificial de esto es la concatenación de cadenas de una lista de cadenas. En C , por ejemplo, el costo de concatenar dos cadenas de longitud m y n utilizando strcat es O( m + n ), ya que necesitamos O( m ) tiempo para encontrar el final de la primera cadena y O( n ) tiempo para copiar la segunda cadena al final de esta. Usando esta función de costo, podemos escribir un algoritmo de programación dinámica para encontrar la forma más rápida de concatenar una secuencia de cadenas. Sin embargo, esta optimización es bastante inútil porque podemos concatenar directamente las cadenas en un tiempo proporcional a la suma de sus longitudes. Existe un problema similar para las listas enlazadas simples .
Otra generalización es resolver el problema cuando se dispone de procesadores paralelos. En este caso, en lugar de sumar los costos de calcular cada factor de un producto matricial, tomamos el máximo porque podemos hacerlo simultáneamente. Esto puede afectar drásticamente tanto al costo mínimo como a la agrupación óptima final; se favorecen las agrupaciones más "equilibradas" que mantienen ocupados a todos los procesadores. Existen incluso enfoques más sofisticados. [12]
