Sottostruttura ottima
Una scelta ottima contiene, al suo interno, scelte ottime per i sottoproblemi che genera.
Algoritmi · Ottimizzazione
Programmazione dinamica e Matrix Chain Order
La programmazione dinamica risolve una volta sola ogni sottoproblema e conserva il risultato. Matrix Chain Order rende il metodo particolarmente visibile: il costo ottimo nasce riempiendo diagonale dopo diagonale due tabelle triangolari.
Quando un problema è adatto alla programmazione dinamica
Dividere un problema non basta. La programmazione dinamica è utile quando molti percorsi ricorsivi chiedono gli stessi sottoproblemi e una soluzione globale ottima può essere composta da soluzioni ottime più piccole.
Sottoproblemi sovrapposti
La ricorsione ingenua ricalcola più volte gli stessi stati. Memorizzarli elimina la ripetizione.
Stato e scelta
Definisci precisamente cosa rappresenta una cella e quale decisione permette di passare a stati più piccoli.
Non è un algoritmo unico. È un metodo di progettazione: definisci gli stati, una ricorrenza, i casi base, l’ordine di calcolo e, se serve, come ricostruire le scelte.
Due modi di calcolare gli stessi stati
Memoization
Parti dal problema completo, usa la ricorsione e salva ogni risultato alla prima visita. Vengono calcolati soltanto gli stati effettivamente richiesti.
Tabulation
Parti dai casi base e riempi una tabella in un ordine che renda già disponibili tutte le dipendenze. MatrixChainOrder usa questo approccio.
Il problema: dove mettere le parentesi?
Il prodotto di matrici è associativo, quindi ogni parentesizzazione produce la stessa matrice finale. Cambia però enormemente il numero di moltiplicazioni scalari. Non stiamo moltiplicando le matrici: stiamo scegliendo l’ordine meno costoso.
(A₁A₂)A₃
10·30·5 + 10·5·60 = 4 500
A₁(A₂A₃)
30·5·60 + 10·30·60 = 27 000
Una catena di n matrici è descritta dal vettore p[0…n]: Aᵢ ha dimensione p[i−1] × p[i].
Stato, caso base e ricorrenza
m[i,j] è il numero minimo di moltiplicazioni scalari necessarie per calcolare Aᵢ…Aⱼ. s[i,j] memorizza il valore di k che realizza quel minimo.
Le catene di lunghezza 1 costano zero. Per una catena più lunga proviamo ogni ultimo taglio k: costo della parte sinistra, costo della parte destra e costo per moltiplicare i due risultati.
Laboratorio: riempi le matrici ruotate
Come nello schema alla lavagna, la diagonale dei casi base è in basso. Ogni nuova diagonale sale di un livello: quando calcoliamo una cella, tutte le celle da cui dipende sono già state riempite.
Avvia l’animazione per confrontare i tagli.
- Lunghezza ℓ
- 1
- Cella
- —
- Taglio k
- —
- Confronti
- 0
Pseudocodice sincronizzato
- for i ← 1 to n: m[i,i] ← 0
- for ℓ ← 2 to n
- for i ← 1 to n − ℓ + 1
- j ← i + ℓ − 1
- m[i,j] ← ∞
- for k ← i to j − 1
- q ← m[i,k] + m[k+1,j] + p[i−1]p[k]p[j]
- if q < m[i,j]: m[i,j] ← q
- s[i,j] ← k
—
Costo ottimo: —
cella da calcolare
sottoproblemi usati
nuovo minimo
cella completata
La tabella S ricostruisce le parentesi
M conserva il valore ottimo, ma da solo non dice quali scelte lo hanno prodotto. S conserva il taglio: partendo da s[1,n], ricostruiamo ricorsivamente prima A₁…Aₖ e poi Aₖ₊₁…Aₙ.
Print(i,j) → se i = j stampa Aᵢ; altrimenti stampa “(”, Print(i,s[i,j]), Print(s[i,j]+1,j), “)”.
Pattern generale. Se vuoi anche la soluzione e non soltanto il suo valore, salva la decisione migliore insieme al valore di ogni stato.
Correttezza e studio della complessità
Quando calcoliamo m[i,j], ogni possibile parentesizzazione ha un ultimo prodotto che separa la catena in Aᵢ…Aₖ e Aₖ₊₁…Aⱼ per un unico k. Per sottostruttura ottima, se una delle due parti non fosse ottima potremmo sostituirla e migliorare la soluzione globale. Provare tutti i k e scegliere il minimo è quindi sufficiente.
| Risorsa | Costo | Perché |
|---|---|---|
| Sottoproblemi | Θ(n²) | Una cella per ogni intervallo [i,j]. |
| Tempo | Θ(n³) | Per ogni intervallo si provano fino a n−1 tagli. |
| Memoria | Θ(n²) | Le due tabelle triangolari M e S. |
| Ricostruzione | Θ(n) | La parentesizzazione contiene n matrici e n−1 tagli. |
Errori comuni
- Confondere il numero di matrici n con la lunghezza n+1 del vettore p.
- Usare p[i], p[k] e p[j] invece di p[i−1], p[k] e p[j] nel costo del prodotto finale.
- Riempire per righe: m[i,j] dipende da intervalli più corti, quindi l’ordine sicuro è per lunghezza crescente.
- Salvare il costo in S: S contiene l’indice k, non il valore q.
- Pensare che l’algoritmo esegua il prodotto: calcola soltanto l’ordine ottimo.
Esercizi per fissare il metodo
- Prova p = [10, 20, 30, 40]. Prima dell’animazione, calcola a mano i due costi per m[1,3].
- Nell’esempio della lezione, individua nelle tabelle le celle usate per calcolare m[2,5] quando k = 3.
- Trova una catena di quattro matrici per cui la parentesizzazione da sinistra a destra sia ottima e una per cui sia la peggiore.
- Modifica concettualmente l’algoritmo per contare quante parentesizzazioni raggiungono lo stesso costo minimo.