La multiplicación de cadenas de matrices (o el problema de ordenación de cadenas de matrices [ cita requerida ] ) es un problema de optimización relacionado con la forma más eficiente de multiplicar una secuencia dada de matrices . El problema no es realmente realizar las multiplicaciones, sino simplemente decidir la secuencia de las multiplicaciones de matrices involucradas. El problema puede resolverse mediante programación dinámica .
Hay muchas opciones porque la multiplicación de matrices es asociativa . En otras palabras, no importa cómo esté entre paréntesis el producto , el resultado obtenido seguirá siendo el mismo. Por ejemplo, para cuatro matrices A , B , C y D , hay cinco opciones posibles:
- (( AB ) C ) D = ( A ( BC )) D = ( AB ) ( CD ) = A (( BC ) D ) = A ( B ( CD )).
Aunque no afecta al producto, el orden en que los términos están entre paréntesis afecta el número de operaciones aritméticas simples necesarias para calcular el producto, es decir, la complejidad computacional . Por ejemplo, si A es una matriz de 10 × 30, B es una matriz de 30 × 5 y C es una matriz de 5 × 60, entonces
- computación ( AB ) C necesita (10 × 30 × 5) + (10 × 5 × 60) = 1500 + 3000 = 4500 operaciones, mientras que
- El cálculo de A ( BC ) necesita (30 × 5 × 60) + (10 × 30 × 60) = 9000 + 18000 = 27000 operaciones.
Claramente, el primer método es más eficiente. Con esta información, el enunciado del problema se puede refinar como "¿cómo determinar el paréntesis óptimo de un producto de n matrices?" Verificar cada posible paréntesis ( fuerza bruta ) requeriría un tiempo de ejecución exponencial en el número de matrices, lo cual 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.
Un algoritmo de programación dinámica
Para comenzar, supongamos que todo lo que realmente queremos saber es el costo mínimo, o el número mínimo de operaciones aritméticas necesarias para multiplicar las matrices. Si solo multiplicamos dos matrices, solo hay una forma de multiplicarlas, por lo que el costo mínimo es el costo de hacer esto. En general, podemos encontrar el costo mínimo utilizando el siguiente algoritmo recursivo :
- Tome la secuencia de matrices y sepárela en dos subsecuencias.
- Encuentre el costo mínimo de multiplicar cada subsecuencia.
- Sume estos costos y agregue el costo de multiplicar las dos matrices de resultados.
- Haga esto para cada posición posible en la que se pueda dividir la secuencia de matrices y tome el mínimo de todas.
Por ejemplo, si tenemos cuatro matrices ABCD , calculamos el costo requerido para encontrar cada uno 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 el 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: agrúpelo de la manera que arroje el costo total más bajo y haga lo mismo para cada factor.
Sin embargo, este algoritmo tiene una complejidad de tiempo de ejecución exponencial que lo hace tan ineficaz como el enfoque ingenuo de probar todas las permutaciones. La razón es que el algoritmo hace 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 recursividad se hace más profunda, ocurre más y más este tipo de repetición innecesaria.
Una solución simple se llama memorización : cada vez que calculamos el costo mínimo necesario para multiplicar una subsecuencia específica, lo guardamos. Si alguna vez se nos pide que lo calculemos nuevamente, simplemente damos la respuesta guardada y no la volvemos a calcular. Puesto que hay sobre n 2 /2 diferentes subsecuencias, donde n es el número de matrices, el espacio necesario para hacer esto es razonable. Se puede demostrar que este simple truco reduce el tiempo de ejecución a O ( n 3 ) desde O (2 n ), que es lo suficientemente eficiente para aplicaciones reales. Esta es una programación dinámica de arriba hacia abajo .
El siguiente enfoque ascendente [1] calcula, para cada 2 ≤ k ≤ n, los costos mínimos de todas las subsecuencias de longitud k utilizando los costos de las subsecuencias más pequeñas ya calculadas. Tiene el mismo tiempo de ejecución asintótico y no requiere recursividad.
Pseudocódigo:
// La matriz A [i] tiene dimensión atenúa [i-1] x atenúa [i] para i = 1..n MatrixChainOrder ( int atenúa [] ) { // longitud [atenúa] = n + 1 n = atenúa . longitud - 1 ; // m [i, j] = Número mínimo de multiplicaciones escalares (es decir, costo) // necesario para calcular la matriz A [i] A [i + 1] ... A [j] = A [i..j ] // El costo es cero al multiplicar una matriz por ( i = 1 ; i <= n ; i ++ ) m [ i , i ] = 0 ; for ( len = 2 ; len <= n ; len ++ ) { // Longitudes posteriores para ( i = 1 ; i <= n - len + 1 ; i ++ ) { j = i + len - 1 ; m [ i , j ] = MAXINT ; para ( k = i ; k <= j - 1 ; k ++ ) { costo = m [ i , k ] + m [ k + 1 , j ] + atenúa [ i - 1 ] * atenúa [ k ] * atenúa [ j ] ; si ( costo < m [ i , j ] ) { m [ i , j ] = costo ; s [ i , j ] = k ; // Índice de la división de subsecuencias que logró un costo mínimo } } } } }
- Nota: El primer índice de atenuación es 0 y el primer índice de my s es 1.
Una implementación de Java que utiliza índices de matriz basados en cero junto con un método de conveniencia para imprimir el orden resuelto de las operaciones:
público clase MatrixOrderOptimization { protegido int [] [] m ; protegido int [] [] s ; public void matrixChainOrder ( int [] atenúa ) { int n = atenúa . longitud - 1 ; m = nuevo int [ n ] [ n ] ; s = new int [ n ] [ n ] ; for ( int lenMinusOne = 1 ; lenMinusOne < n ; lenMinusOne ++ ) { for ( int i = 0 ; i < n - lenMinusOne ; i ++ ) { int j = i + lenMinusOne ; m [ i ] [ j ] = Número entero . MAX_VALUE ; for ( int k = i ; k < j ; k ++ ) { int cost = m [ i ] [ k ] + m [ k + 1 ] [ j ] + atenúa [ i ] * atenúa [ k + 1 ] * atenúa [ j + 1 ] ; si ( costo < m [ i ] [ j ] ) { m [ i ] [ j ] = costo ; s [ i ] [ j ] = k ; } } } } } public void printOptimalParenthesizations () { boolean [] inAResult = new boolean [ s . longitud ] ; printOptimalParenthesizations ( s , 0 , s . longitud - 1 , inAResult ); } void printOptimalParenthesizations ( int [] [] s , int i , int j , / * para impresiones bonitas: * / boolean [] inAResult ) { if ( i ! = j ) { printOptimalParenthesizations ( s , i , s [ i ] [ j ] , inAResult ); printOptimalParenthesizations ( s , s [ i ] [ j ] + 1 , j , inAResult ); Cadena istr = inAResult [ i ] ? "_result" : "" ; String jstr = inAResult [ j ] ? "_result" : "" ; Sistema . fuera . println ( "A_" + i + istr + "* A_" + j + jstr ); inAResult [ i ] = verdadero ; inAResult [ j ] = verdadero ; } } }
Al final de este programa, tenemos el costo mínimo para la secuencia completa.
Algoritmos más eficientes
Hay algoritmos que son más eficientes que el algoritmo de programación dinámica O ( n 3 ), aunque son más complejos.
Hu y Shing (1981)
Un algoritmo publicado en 1981 por Hu y Shing logra una complejidad computacional O ( n log n ) . [2] [3] [4] Mostraron 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 catalán . El algoritmo aprovecha que también hay C n −1 triangulaciones posibles de un polígono con n +1 lados.
Esta imagen ilustra posibles triangulaciones de un hexágono regular . Estos corresponden a las diferentes formas en que se pueden colocar los paréntesis para ordenar las multiplicaciones para un producto de 5 matrices.
Para el siguiente ejemplo, 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 4 gon, es decir, un cuadrado:
El producto matricial AB es una matriz de 10x5 y BC es una matriz de 30x60. Las dos triangulaciones posibles en este ejemplo son:
Representación poligonal de (AB) C
Representación poligonal de A (BC)
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:
- ( AB ) C : (10 × 30 × 5) + (10 × 5 × 60) = 1500 + 3000 = 4500 multiplicaciones
- A ( BC ): (30 × 5 × 60) + (10 × 30 × 60) = 9000 + 18000 = 27000 multiplicaciones
Hu & Shing desarrolló un algoritmo que encuentra una solución óptima para el problema de partición de costo mínimo en tiempo O ( n log n ).
Algoritmo de aproximación de Chin-Hu-Shing
En la introducción de [4] se presenta un algoritmo de aproximación, el algoritmo de aproximación de Chin-Hu-Shing. Si bien este algoritmo produce una aproximación de la triangulación óptima, vale la pena explicarlo ya que facilita la comprensión de las técnicas utilizadas por Hu-Shing en su trabajo.
A cada vértice V del polígono se le asocia un peso w . Supongamos que tenemos tres vértices consecutivos, y eso es el vértice con peso mínimo . Miramos el cuadrilátero con vértices(en el orden de las agujas del reloj). Podemos triangularlo de dos formas:
- y , con costo
- y con costo .
Por tanto, si
o equivalente
quitamos el vértice del polígono y agregue el lado a la triangulación. Repetimos este proceso hasta que nosatisface la condición anterior. Para todos los vértices restantes, agregamos el lado a la triangulación. Esto nos da una triangulación casi óptima.
Generalizaciones
El problema de 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 en esos objetos y una forma de calcular el costo de realizar esa operación en dos objetos dados cualesquiera (así como todos los parciales resultados), calcule la forma de costo mínimo de agrupar los objetos para aplicar la operación sobre la secuencia. [5] Un caso especial algo artificial de esto es la concatenación de cadenas de una lista de cadenas. En C , por ejemplo, el costo de la concatenación de dos cadenas de longitud m y n usando strcat es O ( m + n ), ya que necesitamos O ( m tiempo) para encontrar el final de la primera cadena y O ( n ) tiempo para copie la segunda cuerda al final de la misma. 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 el tiempo proporcional a la suma de sus longitudes. Existe un problema similar para las listas enlazadas individualmente .
Otra generalización consiste en resolver el problema cuando se dispone de procesadores en paralelo. 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 el costo mínimo como la agrupación óptima final; Se favorecen las agrupaciones más "equilibradas" que mantienen ocupados a todos los procesadores. Hay enfoques aún más sofisticados. [6]
Ver también
Referencias
- ^ Cormen, Thomas H ; Leiserson, Charles E ; Rivest, Ronald L ; Stein, Clifford (2001). "15.2: Multiplicación de cadenas de matrices". Introducción a los algoritmos . Segunda edicion. MIT Press y McGraw-Hill. págs. 331–338. ISBN 978-0-262-03293-3.
- ^ Hu, TC; Shing, MT (1982). "Cálculo de los productos de la cadena de matrices, parte I" (PDF) . Revista SIAM de Computación . 11 (2): 362–373. CiteSeerX 10.1.1.695.2923 . doi : 10.1137 / 0211028 . ISSN 0097-5397 .
- ^ Hu, TC; Shing, MT (1984). "Cálculo de los productos de la cadena de matrices, parte II" (PDF) . Revista SIAM de Computación . 13 (2): 228-251. CiteSeerX 10.1.1.695.4875 . doi : 10.1137 / 0213017 . ISSN 0097-5397 .
- ^ a b Artur, Czumaj (1996). "Aproximación muy rápida del problema del producto de la cadena de matriz" (PDF) . Revista de algoritmos . 21 : 71–79. CiteSeerX 10.1.1.218.8168 . doi : 10.1006 / jagm.1996.0037 . Archivado desde el original (PDF) el 27 de julio de 2018.
- ^ G. Baumgartner, D. Bernholdt, D. Cociorva, R. Harrison, M. Nooijen, J. Ramanujam y P. Sadayappan. Un marco de optimización del rendimiento para la compilación de expresiones de contracción tensorial en programas paralelos. 7º Taller Internacional sobre Modelos de Programación Paralela de Alto Nivel y Entornos de Apoyo (HIPS '02). Fort Lauderdale, Florida. 2002 disponible en http://citeseer.ist.psu.edu/610463.html y en http://www.csc.lsu.edu/~gb/TCE/Publications/OptFramework-HIPS02.pdf
- ^ Heejo Lee, Jong Kim, Sungje Hong y Sunggu Lee. Asignación de procesadores y programación de tareas de productos Matrix Chain en sistemas paralelos Archivado el 22 de julio de 2011 en Wayback Machine . IEEE Trans. sobre sistemas paralelos y distribuidos, vol. 14, núm. 4, págs. 394–407, abril de 2003