dynamic-programming
Matriz de multiplicación de la cadena
Buscar..
Solucion recursiva
La multiplicación de la cadena de matrices es un problema de optimización que se puede resolver utilizando la programación dinámica. Dada una secuencia de matrices, el objetivo es encontrar la forma más eficiente de multiplicar estas matrices. El problema no es realmente realizar las multiplicaciones, sino simplemente decidir la secuencia de las multiplicaciones matriciales involucradas.
Digamos que tenemos dos matrices A 1 y A 2 de dimensión m * n y p * q . De las reglas de la multiplicación de matrices, sabemos que,
- Podemos multiplicar A 1 y A 2 si y solo si n = p . Eso significa que el número de columnas de A 1 debe ser igual al número de filas de A 2 .
- Si la primera condición se cumple y multiplicamos A 1 y A 2 , obtendremos una nueva matriz, llamémosla A 3 de dimensión m * q .
- Para multiplicar A 1 y A 2 , necesitamos hacer algunas multiplicaciones de escalador. El número total de multiplicaciones de escalador que debemos realizar es ( m * n * q ) o ( m * p * q ).
- A 1 * A 2 no es igual a A 2 * A 1 .
Si tenemos tres matrices A 1 , A 2 y A 3 que tienen la dimensión m * n , n * p y p * q respectivamente, entonces A 4 = A 1 * A 2 * A 3 tendrá la dimensión de m * q . Ahora podemos realizar esta multiplicación de matrices de dos maneras:
- Primero multiplicamos A 1 y A 2 , luego con el resultado multiplicamos A 3 . Es decir: ( A 1 * A 2 ) * A 3 .
- Primero multiplicamos A 2 y A 3 , luego con el resultado multiplicamos A 1 . Es decir: A 1 * ( A 2 * A 3 ).
Puede observar que el orden de la multiplicación sigue siendo el mismo, es decir, no multiplicamos ( A 1 * A 3 ) * A 2 porque podría no ser válido. Solo cambiamos el paréntesis para multiplicar un conjunto antes de multiplicarlo con el restante. Cómo colocamos estos paréntesis son importantes. ¿Por qué? Digamos, la dimensión de 3 matrices A 1 , A 2 y A 3 son 10 * 100 , 100 * 5 , 5 * 50 . Entonces,
- Para ( A 1 * A 2 ) * A 3 , el número total de multiplicaciones del escalador es: ( 10 * 100 * 5 ) + ( 10 * 5 * 50 ) = 7500 veces.
- Para A 1 * ( A 2 * A 3 ), el número total de multiplicaciones del escalador es: ( 100 * 5 * 50 ) + ( 10 * 100 * 50 ) = 75000 veces.
Para el segundo tipo, ¡el número de la multiplicación del escalador es 10 veces el número del primer tipo! Entonces, si puede idear una manera de averiguar la orientación correcta del paréntesis necesaria para minimizar la multiplicación total del escalador, se reduciría el tiempo y la memoria necesarios para la multiplicación de matrices. Aquí es donde la multiplicación de la cadena de matriz es útil. Aquí, no nos ocuparemos de la multiplicación real de matrices, solo encontraremos el orden de paréntesis correcto para minimizar el número de multiplicaciones del escalador. Tendremos las matrices A 1 , A 2 , A 3 ........ A n y descubriremos el número mínimo de multiplicaciones de escalador necesarias para multiplicar estas. Asumiremos que las dimensiones dadas son válidas, es decir, satisfacen nuestro primer requisito para la multiplicación de matrices.
Usaremos el método de dividir y vencer para resolver este problema. La programación dinámica es necesaria debido a los subproblemas comunes. Por ejemplo: para n = 5 , tenemos 5 matrices A 1 , A 2 , A 3 , A 4 y A 5 . Queremos averiguar el número mínimo de multiplicaciones necesarias para realizar esta multiplicación de matrices A 1 * A 2 * A 3 * A 4 * A 5 . De las muchas maneras, concentrémonos en una: ( A 1 * A 2 ) * ( A 3 * A 4 * A 5 ).
Para este, descubriremos A izquierda = A 1 * A 2 . A derecha = A 3 * A 4 * A 5 . Luego encontraremos una respuesta = A izquierda * A derecha . El número total de multiplicaciones de escalador necesarias para encontrar una respuesta : = El número total de multiplicaciones de escalador necesarias para determinar A izquierda + El número total de multiplicaciones de escalador necesarias para determinar A derecha + El número total de multiplicaciones de escalador necesarias para determinar A izquierda * Un derecho
El último término, el número total de multiplicaciones de escalador necesarias para determinar A izquierda * A derecha puede escribirse como: El número de filas en A izquierda * el número de columnas en A izquierda * el número de columnas en A derecha . (De acuerdo con la 2a regla de la multiplicación de matrices)
Pero también podríamos poner el paréntesis de otras maneras. Por ejemplo:
- A 1 * ( A 2 * A 3 * A 4 * A 5 )
- ( A 1 * A 2 * A 3 ) * ( A 4 * A 5 )
- ( A 1 * A 2 * A 3 * A 4 ) * A 5, etc.
Para cada uno de los casos posibles, determinaremos el número de multiplicaciones de escalador necesarias para encontrar A izquierda y A derecha , luego para A izquierda * A derecha . Si tiene una idea general sobre la recursión, ya ha comprendido cómo realizar esta tarea. Nuestro algoritmo será:
- Set parenthesis in all possible ways.
- Recursively solve for the smaller parts.
- Find out the total number of scaler multiplication by merging left and right.
- Of all possible ways, choose the best one.
¿Por qué este es un problema de programación dinámica? Para determinar ( A 1 * A 2 * A 3 ), si ya ha calculado ( A 1 * A 2 ), será útil en este caso.
Para determinar el estado de esta recursión, podemos ver que para resolver cada caso, necesitamos conocer el rango de matrices con las que estamos trabajando. Así que necesitaremos un comienzo y un final . Como estamos utilizando divide y vencerás, nuestro caso base tendrá menos de 2 matrices ( inicio > = fin ), donde no necesitamos multiplicar en absoluto. Tendremos 2 matrices: fila y columna . la fila [i] y la columna [i] almacenarán el número de filas y columnas para la matriz A i . Tendremos una matriz dp [n] [n] para almacenar los valores ya calculados e inicializarlos con -1 , donde -1 representa el valor que aún no se ha calculado. dp [i] [j] representa el número de multiplicaciones de escalador necesarias para multiplicar A i , A i + 1 , ....., A j inclusive. El pseudocódigo se verá así:
Procedure matrixChain(begin, end):
if begin >= end
Return 0
else if dp[begin][end] is not equal to -1
Return dp[begin][end]
end if
answer := infinity
for mid from begin to end
operation_for_left := matrixChain(begin, mid)
operation_for_right := matrixChain(mid+1, right)
operation_for_left_and_right := row[begin] * column[mid] * column[end]
total := operation_for_left + operation_for_right + operation_for_left_and_right
answer := min(total, answer)
end for
dp[begin][end] := answer
Return dp[begin][end]
Complejidad:
El valor de inicio y final puede variar de 1 a n . Hay n 2 estados diferentes. Para cada estado, el bucle interno se ejecutará n veces. Complejidad de tiempo total: O(n³) y complejidad de memoria: O(n²) .