In informatica, un problema possiede una sottostruttura ottimale se è possibile costruire efficientemente una soluzione ottimale a partire dalle soluzioni ottimali dei suoi sottoproblemi. Questa proprietà è necessaria per poter utilizzare tecniche di programmazione dinamica o algoritmi greedy e rappresenta uno dei principi fondamentali della progettazione algoritmica.
thumb|Ricerca del cammino minimo in un grafo utilizzando le sottostrutture ottimali.
Definizione formale
Un problema di ottimizzazione presenta sottostruttura ottimale quando una soluzione ottimale del problema contiene al suo interno soluzioni ottime ai sottoproblemi. Formalmente, sia P un problema di ottimizzazione e S una sua soluzione ottimale. Il problema P ha sottostruttura ottimale se S può essere decomposta in sottosoluzioni S₁, S₂, ..., Sₖ tali che ciascuna Sᵢ è ottimale per il corrispondente sottoproblema Pᵢ.
Proprietà matematica
La sottostruttura ottimale può essere espressa mediante il principio di ottimalità di Bellman: "Una politica ottimale ha la proprietà che, qualsiasi sia lo stato iniziale e la decisione iniziale, le rimanenti decisioni devono costituire una politica ottimale rispetto allo stato risultante dalla prima decisione".
Dimostrazione della proprietà
Per dimostrare che un problema ha sottostruttura ottimale, si utilizza tipicamente la tecnica di taglio e incollaggio (cut-and-paste):
Si assume l'esistenza di una soluzione ottimale al problema originale Si dimostra che questa soluzione deve contenere soluzioni ottime ai sottoproblemi Si utilizza la tecnica per contraddizione: se esistesse una soluzione migliore per un sottoproblema, si potrebbe "tagliare" la parte non ottimale e "incollare" quella migliore, ottenendo una soluzione complessiva migliore, contraddicendo l'ottimalità della soluzione originale.
Esempi di problemi con sottostruttura ottimale
Cammino minimo
Un esempio classico di sottostrutture ottimali è la ricerca del cammino minimo tra due vertici in un grafo, come illustrato nella figura: se il cammino minimo da A a C passa per B, allora il sottocammino da A a B deve essere ottimale. Se esistesse un cammino migliore da A a B, si potrebbe sostituirlo ottenendo un cammino complessivo da A a C migliore, contraddicendo l'ottimalità del percorso originale.
Dimostrazione: Sia P = (v₁, v₂, ..., vₖ) il cammino minimo da v₁ a vₖ. Allora per ogni 1 ≤ i < j ≤ k, il sottocammino (vᵢ, vᵢ₊₁, ..., vⱼ) è il cammino minimo da vᵢ a vⱼ.
Massima sottosequenza comune
Nel problema della Massima sottosequenza comune (LCS), date due sequenze X e Y, se LCS(X, Y) termina con lo stesso carattere, allora: Se X[m] = Y[n], allora LCS(X, Y) = LCS(X[1..m-1], Y[1..n-1]) + X[m] La sottostruttura ottimale consiste nel fatto che la LCS di X e Y contiene la LCS dei prefissi più corti
Problema dello zaino
Nel problema dello zaino 0-1, la soluzione ottimale per uno zaino di capacità W usando i primi i oggetti: Include l'oggetto i se questo porta al valore massimo Non lo include altrimenti In entrambi i casi, utilizza la soluzione ottimale per il sottoproblema rimanente
Moltiplicazione di matrici
Nell'ottimizzazione della moltiplicazione di matrici, l'ordine ottimale per moltiplicare le matrici M₁ × M₂ × ... × Mₙ si basa sulle soluzioni ottime per sottocatene più piccole.
Relazione con paradigmi algoritmici
Programmazione dinamica
La sottostruttura ottimale è una condizione necessaria per l'applicazione della programmazione dinamica. Quando un problema presenta sia sottostruttura ottimale che sottoproblemi sovrapposti, la programmazione dinamica può risolverlo efficacemente memorizzando le soluzioni dei sottoproblemi per evitare ricalcoli.
Algoritmi greedy
Solitamente, un problema con sottostruttura ottimale viene risolto con un algoritmo greedy quando possiede anche la proprietà di scelta greedy. Questa proprietà garantisce che una scelta localmente ottimale porta sempre a una soluzione globalmente ottimale.
Paradigma Sottostruttura ottimale Proprietà aggiuntiva Esempi Programmazione dinamica ✓ Sottoproblemi sovrapposti LCS, Zaino 0-1, Floyd-Warshall Algoritmi greedy ✓ Proprietà di scelta greedy Dijkstra, Kruskal, Huffman Divide et impera ✓ Sottoproblemi indipendenti Merge sort, Quicksort
Controesempi: problemi senza sottostruttura ottimale
Cammino più lungo
Il problema del cammino più lungo in un grafo generale non ha sottostruttura ottimale. Se il cammino più lungo da A a C passa per B, il sottocammino da A a B potrebbe non essere il più lungo possibile da A a B, perché un cammino più lungo da A a B potrebbe utilizzare vertici che sono già stati usati nel cammino da B a C.
Cammino più economico con vincoli
Se aggiungiamo vincoli complessi (come "il cammino deve passare attraverso esattamente k città diverse"), la sottostruttura ottimale può venire meno perché le scelte ottimali per i sottoproblemi potrebbero non essere compatibili con i vincoli globali.
Verifica della sottostruttura ottimale
Per verificare se un problema ha sottostruttura ottimale:
Caratterizzare la struttura di una soluzione ottimale Mostrare che una soluzione ottimale contiene soluzioni ottime ai sottoproblemi Dimostrare che non si può migliorare la soluzione complessiva migliorando le soluzioni dei sottoproblemi
Template di dimostrazione
VERIFICA_SOTTOSTRUTTURA_OTTIMALE(Problema P): 1. Sia S* una soluzione ottimale per P 2. Scomponi S* in soluzioni per sottoproblemi: S₁, S₂, ..., Sₖ 3. Per ogni i, dimostra per contraddizione che Sᵢ è ottimale: - Supponi ∃ S'ᵢ migliore di Sᵢ per il sottoproblema i - Sostituisci Sᵢ con S'ᵢ in S* ottenendo S' - Mostra che S' è migliore di S* - Contraddizione: S* non era ottimale 4. Concludi: P ha sottostruttura ottimale
Implementazione pratica
Memoization top-down
OTTIMO_TOPDOWN(problema, memo): if problema in memo: return memo[problema]
if caso_base(problema): return soluzione_base(problema)
migliore = None for sottoproblema in genera_sottoproblemi(problema): candidato = OTTIMO_TOPDOWN(sottoproblema, memo) if candidato è migliore di migliore: migliore = candidato
memo[problema] = costruisci_soluzione(migliore) return memo[problema]
Approccio bottom-up
OTTIMO_BOTTOMUP(problema): sottoproblemi = ordina_per_dimensione(genera_tutti_sottoproblemi(problema)) soluzioni = {}
for sp in sottoproblemi: if caso_base(sp): soluzioni[sp] = soluzione_base(sp) else: migliore = None for sotto_sp in dipendenze(sp): candidato = soluzioni[sotto_sp] if candidato è migliore di migliore: migliore = candidato soluzioni[sp] = costruisci_soluzione(migliore)
return soluzioni[problema]
Applicazioni pratiche
La sottostruttura ottimale è fondamentale in:
Bioinformatica: Allineamento di sequenze, predizione di strutture Computer graphics: Ray tracing, pathfinding nei videogiochi Networking: Protocolli di routing, ottimizzazione di reti Economia: Modelli di decisione sequenziale, ottimizzazione di portfolio Intelligenza artificiale: Pianificazione automatica, reinforcement learning
Note
Bibliografia
Voci correlate Programmazione dinamica Algoritmo greedy Principio di ottimalità di Bellman Sottoproblemi sovrapposti Cammino minimo Problema dello zaino Massima sottosequenza comune
Altri progetti
Categoria:Ottimizzazione Categoria:Programmazione dinamica