Matrix Chain Multiplication
Una catena di matrici è descritta da dims: la matrice i ha dims[i] righe e dims[i+1] colonne, quindi ogni matrice si adatta alla successiva. Moltiplicare una matrice p × q per una matrice q × r richiede p × q × r moltiplicazioni scalari e produce una matrice p × r. Ogni modo di inserire le parentesi dà lo stesso prodotto finale, ma non allo stesso costo. Restituisci il minor numero di moltiplicazioni scalari necessarie per moltiplicare l'intera catena.
Funzione
- dimsinteger-array
- le dimensioni lungo la catena: la matrice i ha dimensioni dims[i] × dims[i+1]
- Restituisceinteger
- il minor numero di moltiplicazioni scalari necessarie per moltiplicare l'intera catena
Vincoli
2 ≤ dims.length ≤ 100, quindi la catena contiene tra 1 e 99 matrici.1 ≤ dims[i] ≤ 100- La risposta è al massimo 98 × 106, ben al di sotto del limite di un intero con segno a 32 bit.
Esempi
- Input
- dims = [4, 10, 3, 12]
- Output
- 264
- Spiegazione
- Moltiplicare le prime due matrici costa 4 × 10 × 3 = 120 e lascia una matrice 4 × 3, che moltiplicata per la matrice 3 × 12 aggiunge 144: 264. L’altro ordine costa 360 + 480 = 840.
- Input
- dims = [6, 2, 7, 3, 5]
- Output
- 132
- Spiegazione
- Moltiplica 2 × 7 per 7 × 3 (42), il risultato di 2 × 3 per 3 × 5 (30), poi 6 × 2 per il risultato di 2 × 5 (60): 132 in totale.
- Input
- dims = [3, 7]
- Output
- 0
- Spiegazione
- C'è una sola matrice, 3 × 7, quindi non viene eseguita alcuna moltiplicazione e il costo è 0.
Per approfondire
Puoi anche contare quante diverse parentesizzazioni raggiungono il costo minimo?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Dimentica la prima moltiplicazione e pensa all’ultima. Qualunque ordine tu scelga, l’ultimo passaggio moltiplica il prodotto di una parte iniziale della catena per il prodotto del resto.
Il prodotto delle matrici tra due confini
lefterightè sempre una matricedims[left] × dims[right]. Quindi, se l'ultimo passaggio divide quel tratto al confinesplit, il costo èdims[left] × dims[split] × dims[right]e le due parti sono versioni più piccole dello stesso problema.Memorizza in
best[left][right]il modo meno costoso per moltiplicare le matrici comprese tra i confinilefteright(0 per una singola matrice). È il minimo, considerando ognisplitstrettamente compreso tra i due, dibest[left][split] + best[split][right] + dims[left] × dims[split] × dims[right]. Calcola prima gli intervalli più stretti, poi quelli più ampi.
Soluzione
L’ordine cambia il costo: 264 contro 840 nel primo esempio. Guarda l’ultima moltiplicazione. Unisce i prodotti di una parte sinistra e di una parte destra della catena, e ciascuna parte è lo stesso problema su una catena più corta. Una tabella sugli intervalli della catena risolve ciascun problema una sola volta, in tempo O(n³).
Prova ogni suddivisione con la ricorsione semplice
Corretto, ma non termina sui test più grandi
Intuizione
Numera i confini della catena da 0 a m-1, dove m = dims.length: il confine k ha dimensione dims[k]. Le matrici tra i confini left e right si moltiplicano in una matrice dims[left] × dims[right] in qualsiasi ordine. Quindi, se l’ultimo passaggio divide quel tratto in corrispondenza di split, costa dims[left] × dims[split] × dims[right], indipendentemente da ciò che è avvenuto all’interno dei due blocchi. Ogni blocco dovrebbe essere costruito nel modo più economico possibile, quindi cheapest(left, right) è la somma minima dei costi dei due blocchi più quella dell’ultimo passaggio, considerando ogni split. Provare ogni possibile ultimo passaggio garantisce la correttezza.
Risolve gli stessi tratti più e più volte: n matrici richiedono 3^(n-1) chiamate, circa 1.2 × 10^9 per 20 matrici, mentre i tratti diversi sono solo circa m²/2.
Algoritmo
- Scrivi
cheapest(left, right)per le matrici tra i confinilefteright. - Se
right - left < 2, c'è una sola matrice: restituisci 0. - Per ogni
splitstrettamente compreso tra loro, sommacheapest(left, split),cheapest(split, right)edims[left] × dims[split] × dims[right]. - Restituisci la somma più piccola.
- La risposta è
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)Ricorsione con una memoria
Intuizione
Una chiamata dipende solo da left e right. Salva il suo risultato in memo[left][right], con ogni cella inizializzata a -1, un valore che nessun costo reale può assumere, e le chiamate successive leggono la cella invece di ricorrere. Ciascuna delle circa m²/2 coppie viene risolta una sola volta con meno di m divisioni: O(n³), ovvero 161.700 verifiche delle divisioni per 99 matrici. La ricorsione non è mai più profonda della lunghezza della catena, quindi 100 confini entrano in qualsiasi stack delle chiamate.
Algoritmo
- Alloca
memoconmrighe emcolonne, ogni cella a -1. - In
cheapest(left, right), un tratto di una sola matrice restituisce 0 e una cella diversa da -1 restituisce il costo salvato. - Altrimenti calcola il costo di ogni
splitesattamente come fa la ricorsione semplice e scegli il minimo. - Scrivi quel minimo in
memo[left][right]prima di restituirlo. - La risposta è
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)Riempi la tabella estendendola in larghezza
Intuizione
Ogni cella dipende solo da intervalli più ristretti, quindi i cicli possono riempire best[left][right] dagli intervalli più ristretti a quelli più ampi. La larghezza 1 corrisponde a una singola matrice e rimane 0; quando si raggiunge un intervallo più ampio, entrambe le parti di ogni suddivisione sono già state calcolate. Con dims = [6, 2, 7, 3, 5]:
- Larghezza 2:
best[0][2] = 84,best[1][3] = 42,best[2][4] = 105. - Larghezza 3:
best[0][3]è 78 (suddivisione 1: 0 + 42 + 36),best[1][4]è 72 (suddivisione 3: 42 + 0 + 30). - Larghezza 4: le suddivisioni 1, 2 e 3 danno 0 + 72 + 60 = 132, 84 + 105 + 210 = 399 e 78 + 0 + 90 = 168, quindi
best[0][4] = 132.
La suddivisione ottimale al confine 1 significa che la matrice 6 × 2 viene moltiplicata per ultima, come nel secondo esempio. Tempo e memoria sono paragonabili a quelli della versione con memoizzazione, senza ricorsione.
Algoritmo
- Siano
m = dims.lengthe alloca una tabellam × mbestdi zeri. - Fai scorrere
widthda 2 am-1. Al suo interno, fai scorrereleftverso l’alto a partire da 0, finchéright = left + widthresta entro i limiti. - Per quel tratto, calcola
best[left][split] + best[split][right] + dims[left] × dims[split] × dims[right]per ognisplitdaleft+1aright-1e memorizza il minimo inbest[left][right]. - La risposta si trova in
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]
Trappole e casi limite
- Moltiplicare per primo la coppia più economica. Con
[10, 10, 1, 9]l'ultima coppia è la più economica (90), ma il passaggio successivo costa 900, per un totale di 990. Moltiplicare per prima la coppia iniziale costa 190. - Leggere la risposta dalla cella sbagliata.
dimsha una voce in più rispetto al numero di matrici, quindi la risposta èbest[0][m-1], nonbest[0][m]. - Far crescere
leftnel ciclo esterno. La rigaleftlegge quindibest[split][right]da una riga successiva, che è ancora 0. Metti l'ampiezza nel ciclo esterno oppure fai diminuireleft. - Dimenticare la matrice singola.
[3, 7]deve restituire 0 e, in R, il ciclo2:(m-1)diventa2:1e procede all'indietro, quindi proteggilo con una condizione.
Domande frequenti3
Qual è la complessità temporale della moltiplicazione di una catena di matrici?
La tabella ha circa n²/2 intervalli e ciascuno prova fino a n divisioni, quindi la programmazione dinamica richiede un tempo O(n³) e una memoria O(n²). La ricorsione semplice senza memoizzazione effettua 3^(n-1) chiamate per n matrici.
Perché l’ordine della moltiplicazione tra matrici è importante?
La moltiplicazione di matrici è associativa, quindi (AB)C e A(BC) danno la stessa matrice, ma le matrici intermedie differiscono per dimensione. Nel primo esempio, (AB)C costruisce una matrice 4 × 3 e costa 264, mentre A(BC) costruisce una matrice 10 × 12 e costa 840.
Come si trova la parentetizzazione ottimale stessa?
Memorizza la divisione vincente in choice[left][right] accanto a best[left][right]. Per stampare, una singola matrice stampa il proprio nome; una sequenza più lunga stampa una parentesi aperta, la parte fino a choice[left][right], la parte successiva e una parentesi chiusa. Questo richiede O(n²) di memoria.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def matrixChainOrder(dims):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomento
dims = [4, 10, 3, 12]
Output atteso
264