Hispanopedia Wiki
Articulo de referencia

Multiplicación de cadenas de matrices

La multiplicación de cadenas de matrices (o el problema de ordenación de cadenas de matrices [ 1 ] ) es un problema de optimización que busca la forma más eficiente de multiplic...

Hispanopedia WikiContenido en espanolLectura gratuita

La multiplicación de cadenas de matrices (o el problema de ordenación de cadenas de matrices [ 1 ] ) es un problema de optimización que busca la forma más eficiente de multiplicar una secuencia dada de matrices . El problema no consiste en realizar las multiplicaciones en sí, sino simplemente en decidir la secuencia de multiplicaciones de matrices involucradas. El problema puede resolverse mediante programación dinámica .

Existen muchas opciones porque la multiplicación de matrices es asociativa . En otras palabras, independientemente de cómo se coloquen los paréntesis en el producto , el resultado obtenido seguirá siendo el mismo. Por ejemplo, para cuatro matrices A , B , C y D , existen 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 se colocan los términos entre paréntesis influye en la cantidad de operaciones aritméticas simples necesarias para calcularlo, es decir, en la complejidad computacional . La multiplicación directa de una matriz X × Y por una matriz Y × Z requiere XYZ multiplicaciones ordinarias y X ( Y − 1) Z sumas ordinarias. En este contexto, es habitual utilizar el número de multiplicaciones ordinarias como medida de la complejidad computacional.

Si A es una matriz de 10 × 30, B es una matriz de 30 × 5 y C es una matriz de 5 × 60, entonces

El cálculo de ( 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 la paréntesis óptima de un producto de n matrices?". El número de paréntesis posibles viene dado por el ( n -1) -ésimo número de Catalan , que es Θ (4n / n³ / ² ) , 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 cual es muy lento e impráctico para n grande . Se puede lograr una solución más rápida a este problema dividiéndolo en un conjunto de subproblemas relacionados.

Un algoritmo de programación dinámica

Para empezar, supongamos que lo único 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 hacerlo, por lo que el costo mínimo es el costo de realizar esta multiplicación. En general, podemos encontrar el costo mínimo utilizando el siguiente algoritmo recursivo :

  • Toma la secuencia de matrices y sepárala en dos subsecuencias.
  • Encuentra el costo mínimo de multiplicar cada subsecuencia .
  • Suma estos costos y añade el costo de multiplicar las dos matrices resultantes.
  • Haz esto para cada posición posible en la que se pueda dividir la secuencia de matrices y toma el mínimo de todas ellas.

Por ejemplo, si tenemos cuatro matrices ABCD , calculamos el costo necesario para encontrar cada una de ellas ( A ) ( BCD ) , ( AB ) ( CD ) y ( ABC ) ( D ) , realizando llamadas recursivas para encontrar el costo mínimo para calcular ABC , AB , CD y BCD . Luego elegimos la mejor. Mejor aún, esto no solo proporciona el costo mínimo, sino que también demuestra la mejor manera de realizar la multiplicación: agruparla de la forma que produzca el menor costo total y hacer lo mismo para cada factor.

Sin embargo, este algoritmo tiene una complejidad temporal exponencial, lo 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, anteriormente hicimos una llamada recursiva para encontrar el mejor costo para calcular tanto ABC como 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 profundiza, se produce cada vez más repetición innecesaria de este tipo.

Una solución sencilla se llama memorización : cada vez que calculamos el costo mínimo necesario para multiplicar una subsecuencia específica, lo guardamos. Si se nos pide que lo calculemos de nuevo, simplemente proporcionamos la respuesta guardada y no la volvemos a calcular. Dado que existen aproximadamente n² / 2 subsecuencias diferentes, donde n es el número de matrices, el espacio requerido para esto es razonable. Se puede demostrar que este sencillo truco reduce el tiempo de ejecución de exponencial a O( n³ ) , lo cual es más que suficiente para aplicaciones reales. Esto es programación dinámica descendente .

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 cuando se multiplica una matriz para ( i = 1 ; i <= n ; i ++ ) m [ i , i ] = 0 ;for ( len = 2 ; len <= n ; len ++ ) { // Longitudes de subsecuencias 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 } } } } }
  • Nota: El primer índice para dims es 0 y el primer índice para m y s es 1.

Una implementación en Python que utiliza el decorador de memorización de la biblioteca estándar:

from functools import cachedef matrix_chain_order ( dims : list [ int ]) -> int : @cache def a ( i , j ): return min ( ( a ( i , k ) + dims [ i ] * dims [ k ] * dims [ j ] + a ( k , j ) for k in range ( i + 1 , j )), default = 0 , )devolver a ( 0 , len ( dims ) - 1 )

Algoritmos más eficientes

Existen algoritmos más eficientes que el algoritmo de programación dinámica O ( n³ ) , aunque son más complejos.

Hu y Shing

Un algoritmo publicado por TC Hu y M.-T. Shing alcanza una complejidad computacional de O ( n  log n ) . [ 3 ] [ 4 ] [ 5 ] Mostraron cómo el problema de la multiplicación de cadenas de matrices puede transformarse (o reducirse ) en el problema de la 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 sentido horario, 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 las posibles triangulaciones de un hexágono regular . Estas corresponden a las diferentes maneras 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 para este ejemplo es un cuadrilátero, 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:

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 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 en el artículo publicado. [ 6 ] [ 4 ] La demostración del lema en el informe técnico es incorrecta, pero Shing ha presentado una demostración corregida. [ 1 ] 

Otros algoritmos O ( n  log n ) 

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 ] 

Solución aproximada de Chin-Hu-Shing

Un algoritmo creado independientemente por Chin [ 8 ] y Hu & Shing [ 9 ] 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 traduciendo 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.Vi−1,Vi,Vi+1{\displaystyle V_{i-1},V_{i},V_{i+1}}y queVmin{\displaystyle V_{\min }}es el vértice con peso mínimowmin{\displaystyle w_{\min }}. Observamos el cuadrilátero con vérticesVmin,Vi−1,Vi,Vi+1{\displaystyle V_{\min },V_{i-1},V_{i},V_{i+1}}(en sentido horario). Podemos triangularlo de dos maneras:

  • (Vmin,Vi−1,Vi){\displaystyle (V_{\min},V_{i-1},V_{i})}y(Vmin,Vi+1,Vi){\displaystyle (V_{\min},V_{i+1},V_{i})}, con costowminwi−1wi+wminwi+1wi{\displaystyle w_{\min }w_{i-1}w_{i}+w_{\min }w_{i+1}w_{i}}
  • (Vmin,Vi−1,Vi+1){\displaystyle (V_{\min},V_{i-1},V_{i+1})}y(Vi−1,Vi,Vi+1){\displaystyle (V_{i-1},V_{i},V_{i+1})}con costowminwi−1wi+1+wi−1wiwi+1{\displaystyle w_{\min }w_{i-1}w_{i+1}+w_{i-1}w_{i}w_{i+1}}.

Por lo tanto, si

wminwi−1wi+1+wi−1wiwi+1<wminwi−1wi+wminwi+1wi{\displaystyle w_{\min }w_{i-1}w_{i+1}+w_{i-1}w_{i}w_{i+1}<w_{\min }w_{i-1}w_{i}+w_{\min }w_{i+1}w_{i}}

o equivalentemente

1wi+1wmin<1wi+1+1wi−1{\displaystyle {\frac {1}{w_{i}}}+{\frac {1}{w_{\min }}}<{\frac {1}{w_{i+1}}}+{\frac {1}{w_{i-1}}}}

eliminamos el vérticeVi{\displaystyle V_{i}}desde el polígono y agregar el lado(Vi−1,Vi+1){\displaystyle (V_{i-1},V_{i+1})}a la triangulación. Repetimos este proceso hasta que noVi{\displaystyle V_{i}}satisface la condición anterior. Para todos los vértices restantesVnorte{\displaystyle V_{n}}, añadimos el lateral(Vmin,Vnorte){\displaystyle (V_{\min},V_{n})}a la triangulación. Esto nos da una triangulación casi óptima.

Generalizaciones

El problema de la multiplicación de cadenas de matrices se generaliza a la resolución de 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 en cualquier par de objetos dados (así como todos los resultados parciales), calcular la forma de costo mínimo para agrupar los objetos para aplicar la operación sobre la secuencia. [ 10 ] Un ejemplo práctico de esto proviene del ordenamiento de las operaciones de unión en bases de datos ; véase Optimización de consultas §  Ordenamiento de uniones .

Otro caso especial, algo 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 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 copiar la segunda cadena al final de ella. 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. Un problema similar existe para las listas enlazadas simples . 

Otra generalización consiste en 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. [ 11 ]

Véase también

Referencias

  1. 1 2 Schwartz, Oded; Weiss, Elad (enero de 2019). "Revisitando el cálculo de productos de cadenas de matrices ". SIAM Journal on Computing . 48 (5): 1481– 1486. ​​doi : 10.1137/18m1195401 . S2CID 203009883 . 
  2. ↑ 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 . Vol. Segunda edición. MIT Press y McGraw-Hill. págs. 331–338 . ISBN   978-0-262-03293-3.
  3. ↑ Hu, TC ; Shing, M.-T. (1982). "Cálculo de productos de cadenas de matrices, parte I" (PDF) . SIAM Journal on Computing . 11 (2): 362–373 . CiteSeerX 10.1.1.695.2923 . doi : 10.1137/0211028 . ISSN 0097-5397 . Archivado del original (PDF) el 4 de agosto de 2016. Recuperado el 20 de enero de 2015 .  
  4. 1 2 Hu, TC ; Shing, M.-T. (1984). "Cálculo de productos de cadenas de matrices, parte II" (PDF) . SIAM Journal on Computing . 13 (2): 228– 251. CiteSeerX 10.1.1.695.4875 . doi : 10.1137/0213017 . ISSN 0097-5397 . Archivado del original (PDF) el 4 de agosto de 2016 . Recuperado el 20 de enero de 2015 .  
  5. 1 2 Artur, Czumaj (1996). "Aproximación muy rápida del problema del producto de cadenas de matrices" (PDF) . Journal of Algorithms . 21 : 71–79 . CiteSeerX 10.1.1.218.8168 . doi : 10.1006/jagm.1996.0037 . S2CID 2818053. Archivado del original (PDF) el 27 de julio de 2018.  
  6. ↑ Hu, TC; Shing, MT (1981). Cálculo de productos de cadenas de matrices, Parte I, Parte II (PDF) (Informe técnico). Universidad de Stanford, Departamento de Ciencias de la Computación. Parte II, página 3. STAN-CS-TR-81-875.
  7. ↑ Wang, Xiaodong; Zhu, Daxin; Tian, ​​Jun (abril de 2013). "Cálculo eficiente de cadenas de matrices". 8.ª Conferencia Internacional de Ciencias de la Computación y Educación de 2013. págs. 703–707 . doi : 10.1109/ICCSE.2013.6553999 . ISBN  978-1-4673-4463-0. S2CID 17303326 . 
  8. ↑ Chin, Francis Y. (julio de 1978). "Un algoritmo O(n) para determinar un orden de cálculo casi óptimo de productos de cadenas de matrices" . Communications of the ACM . 21 (7): 544– 549. doi : 10.1145/359545.359556 .
  9. ↑ Hu, TC; Shing, MT (junio de 1981). "Un algoritmo O(n) para encontrar una partición casi óptima de un polígono convexo". Journal of Algorithms . 2 (2): 122– 138. doi : 10.1016/0196-6774(81)90014-6 .
  10. ↑ 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 Soporte (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
  11. ↑ Heejo Lee, Jong Kim, Sungje Hong y Sunggu Lee. Asignación de procesadores y planificación de tareas de productos de cadenas de matrices en sistemas paralelos . Archivado el 22 de julio de 2011 en Wayback Machine . IEEE Trans. on Parallel and Distributed Systems, vol. 14, n.º 4, págs. 394-407, abril de 2003.