Matrix Chain Multiplication
Una cadena de matrices se describe mediante dims: la matriz i tiene dims[i] filas y dims[i+1] columnas, por lo que cada matriz encaja con la siguiente. Multiplicar una matriz de p × q por una matriz de q × r requiere p × q × r multiplicaciones escalares y da como resultado una matriz de p × r. Todas las formas de colocar los paréntesis dan el mismo producto final, pero no tienen el mismo costo. Devuelve el menor número de multiplicaciones escalares necesarias para multiplicar toda la cadena.
Función
- dimsinteger-array
- los tamaños a lo largo de la cadena: la matriz i tiene dimensiones dims[i] × dims[i+1]
- Devuelveinteger
- la menor cantidad de multiplicaciones escalares necesarias para multiplicar toda la cadena
Restricciones
2 ≤ dims.length ≤ 100, por lo que la cadena contiene entre 1 y 99 matrices.1 ≤ dims[i] ≤ 100- La respuesta es como máximo 98 × 106, muy por debajo del límite de un entero con signo de 32 bits.
Ejemplos
- Entrada
- dims = [4, 10, 3, 12]
- Salida
- 264
- Explicación
- Multiplicar los dos primeros cuesta 4 × 10 × 3 = 120 y deja una matriz de 4 × 3, que al multiplicarse por la matriz de 3 × 12 añade 144: 264. El otro orden cuesta 360 + 480 = 840.
- Entrada
- dims = [6, 2, 7, 3, 5]
- Salida
- 132
- Explicación
- Multiplica 2 × 7 por 7 × 3 (42), el resultado de 2 × 3 por 3 × 5 (30), después 6 × 2 por el resultado de 2 × 5 (60): 132 en total.
- Entrada
- dims = [3, 7]
- Salida
- 0
- Explicación
- Solo hay una matriz, 3 × 7, así que no se multiplica nada y el costo es 0.
Para ir más allá
¿También puedes contar cuántas parentizaciones diferentes alcanzan el costo mínimo?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Olvida la primera multiplicación y piensa en la última. Sea cual sea el orden que elijas, el paso final multiplica el producto de una parte izquierda de la cadena por el producto del resto.
El producto de las matrices entre dos límites
leftyrightsiempre es una matrizdims[left] × dims[right]. Así que, si el último paso divide ese tramo en el límitesplit, cuestadims[left] × dims[split] × dims[right], y las dos partes son versiones más pequeñas del mismo problema.Almacena en
best[left][right]la forma más económica de multiplicar las matrices entre los límitesleftyright(0 para una sola matriz). Es el mínimo, considerando cadasplitestrictamente entre ellos, debest[left][split] + best[split][right] + dims[left] × dims[split] × dims[right]. Calcula los tramos estrechos antes que los anchos.
Solución
El orden cambia el costo: 264 frente a 840 en el primer ejemplo. Fíjate en la última multiplicación. Une los productos de una parte izquierda y una parte derecha de la cadena, y cada parte es el mismo problema en una cadena más corta. Una tabla sobre los tramos de la cadena resuelve cada uno una sola vez, en tiempo O(n³).
Prueba cada división con recursión simple
Correcto, pero no termina con las pruebas más grandes
Intuición
Numera los límites de la cadena del 0 al m-1, donde m = dims.length: el límite k tiene tamaño dims[k]. Las matrices entre los límites left y right se multiplican para dar una matriz de dimensiones dims[left] × dims[right], en cualquier orden. Así que, si el último paso divide ese tramo en split, cuesta dims[left] × dims[split] × dims[right], independientemente de lo que ocurra dentro de los dos bloques. Cada bloque debe construirse con el menor costo posible, así que cheapest(left, right) es la suma más pequeña de los costos de ambos bloques más ese último paso, entre todos los valores de split. Probar cada posible último paso garantiza que el resultado sea correcto.
Resuelve los mismos tramos una y otra vez: n matrices requieren 3^(n-1) llamadas, aproximadamente 1.2 × 10^9 para 20 matrices, aunque solo hay alrededor de m²/2 tramos diferentes.
Algoritmo
- Escribe
cheapest(left, right)para las matrices entre los límitesleftyright. - Si
right - left < 2, hay una matriz: devuelve 0. - Para cada
splitque esté estrictamente entre ellos, sumacheapest(left, split),cheapest(split, right)ydims[left] × dims[split] × dims[right]. - Devuelve la suma más pequeña.
- La respuesta es
cheapest(0, m-1).
def matrixChainOrder(dims):
def cheapest(left, right):
# The fewest multiplications for the matrices between boundaries left and right
if right - left < 2:
return 0 # a single matrix costs nothing
best = None
for split in range(left + 1, right):
cost = (cheapest(left, split) + cheapest(split, right)
+ dims[left] * dims[split] * dims[right])
if best is None or cost < best:
best = cost
return best
return cheapest(0, len(dims) - 1)Recursión con una memoización
Intuición
Una llamada depende únicamente de left y right. Guarda su resultado en memo[left][right], con cada celda inicializada en -1, un valor que ningún costo real puede tener, y las llamadas posteriores leen la celda en lugar de volver a hacer llamadas recursivas. Cada uno de los aproximadamente m²/2 pares se resuelve una sola vez con menos de m divisiones: O(n³), o 161,700 comprobaciones de divisiones para 99 matrices. La recursión nunca tiene más profundidad que la longitud de la cadena, así que 100 límites caben en cualquier pila de llamadas.
Algoritmo
- Asigna
memoconmfilas ymcolumnas, y todas las celdas en -1. - En
cheapest(left, right), un tramo de una matriz devuelve 0, y una celda distinta de -1 devuelve su costo guardado. - De lo contrario, calcula el costo de cada
splitexactamente como lo hace la recursión simple y toma el mínimo. - Escribe ese mínimo en
memo[left][right]antes de devolverlo. - La respuesta es
cheapest(0, m-1).
def matrixChainOrder(dims):
m = len(dims)
# memo[left][right]: the answer for boundaries left and right, -1 while unknown
memo = [[-1] * m for _ in range(m)]
def cheapest(left, right):
if right - left < 2:
return 0 # a single matrix costs nothing
if memo[left][right] != -1:
return memo[left][right]
best = None
for split in range(left + 1, right):
cost = (cheapest(left, split) + cheapest(split, right)
+ dims[left] * dims[split] * dims[right])
if best is None or cost < best:
best = cost
memo[left][right] = best
return best
return cheapest(0, m - 1)Rellena la tabla estirándola a lo ancho
Intuición
Cada celda depende solo de tramos más estrechos, así que los bucles pueden llenar best[left][right] de los más estrechos a los más anchos. El ancho 1 corresponde a una sola matriz y se mantiene en 0; cuando llegas a un tramo más ancho, ambas partes de cada división ya están calculadas. Con dims = [6, 2, 7, 3, 5]:
- Ancho 2:
best[0][2] = 84,best[1][3] = 42,best[2][4] = 105. - Ancho 3:
best[0][3]es 78 (división 1: 0 + 42 + 36),best[1][4]es 72 (división 3: 42 + 0 + 30). - Ancho 4: las divisiones 1, 2 y 3 dan 0 + 72 + 60 = 132, 84 + 105 + 210 = 399 y 78 + 0 + 90 = 168, así que
best[0][4] = 132.
La división principal en el límite 1 significa que la matriz 6 × 2 se multiplica al final, como en el segundo ejemplo. El tiempo y la memoria son iguales que en la versión con memoización, sin recursión.
Algoritmo
- Sea
m = dims.lengthy asigna una tabla de ceros dem × mllamadabest. - Recorre
widthdesde 2 hastam-1. Dentro de ese bucle, recorreleften orden ascendente desde 0 mientrasright = left + widthsiga siendo un límite. - Para ese tramo, calcula
best[left][split] + best[split][right] + dims[left] × dims[split] × dims[right]para cadasplitdesdeleft+1hastaright-1, y guarda el mínimo enbest[left][right]. - La respuesta está en
best[0][m-1].
def matrixChainOrder(dims):
m = len(dims)
# best[left][right]: the fewest multiplications for the matrices
# between boundary left and boundary right (0 for a single matrix)
best = [[0] * m for _ in range(m)]
for width in range(2, m):
for left in range(m - width):
right = left + width
low = None
for split in range(left + 1, right):
# the last product joins a dims[left] x dims[split] block
# with a dims[split] x dims[right] block
cost = best[left][split] + best[split][right] + dims[left] * dims[split] * dims[right]
if low is None or cost < low:
low = cost
best[left][right] = low
return best[0][m - 1]
Errores comunes y casos límite
- Multiplicar primero el par más barato. En
[10, 10, 1, 9], el último par es el más barato (90), pero el paso siguiente cuesta 900, para un total de 990. Multiplicar primero el primer par cuesta 190. - Leer la respuesta de la celda equivocada.
dimstiene una entrada más que la cantidad de matrices, así que la respuesta esbest[0][m-1], nobest[0][m]. - Recorrer
lefthacia arriba en el bucle externo. La filaleftlee entoncesbest[split][right]de una fila posterior que todavía es 0. Pon el ancho en el bucle externo o cuentalefthacia abajo. - Omitir la matriz única.
[3, 7]debe devolver 0, y en R el bucle2:(m-1)se convierte en2:1y se ejecuta hacia atrás, así que protégelo con una condición.
Preguntas frecuentes3
¿Cuál es la complejidad temporal de la multiplicación de cadenas de matrices?
La tabla tiene aproximadamente n²/2 tramos y cada uno prueba hasta n divisiones, por lo que la programación dinámica se ejecuta en tiempo O(n³) con O(n²) de memoria. La recursión simple sin memorización realiza 3^(n-1) llamadas para n matrices.
¿Por qué importa el orden de la multiplicación de matrices?
La multiplicación de matrices es asociativa, así que (AB)C y A(BC) dan la misma matriz, pero las matrices intermedias tienen tamaños distintos. En el primer ejemplo, (AB)C construye una matriz de 4 × 3 y cuesta 264, mientras que A(BC) construye una matriz de 10 × 12 y cuesta 840.
¿Cómo encuentras la parentización óptima?
Guarda la división ganadora en choice[left][right] junto a best[left][right]. Para imprimir, una sola matriz imprime su nombre; una secuencia más larga imprime un paréntesis de apertura, la parte hasta choice[left][right], la parte posterior y un paréntesis de cierre. Esto añade memoria O(n²).
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def matrixChainOrder(dims):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumento
dims = [4, 10, 3, 12]
Salida Esperada
264