DAA - Programmazione dinamica
La programmazione dinamica viene utilizzata anche nei problemi di ottimizzazione. Come il metodo divide et impera, la programmazione dinamica risolve i problemi combinando le soluzioni dei sottoproblemi. Inoltre, l'algoritmo di programmazione dinamica risolve ogni sottoproblema una sola volta e poi salva la sua risposta in una tabella, evitando così il lavoro di rielaborare la risposta ogni volta.
Due proprietà principali di un problema suggeriscono che il problema dato può essere risolto utilizzando la programmazione dinamica. Queste proprietà sonooverlapping sub-problems and optimal substructure.
Problemi secondari sovrapposti
Simile all'approccio Divide-and-Conquer, la programmazione dinamica combina anche soluzioni a problemi secondari. Viene utilizzato principalmente quando è necessaria ripetutamente la soluzione di un sottoproblema. Le soluzioni calcolate vengono memorizzate in una tabella, in modo che non debbano essere ricalcolate. Quindi, questa tecnica è necessaria laddove esistono problemi secondari sovrapposti.
Ad esempio, la ricerca binaria non presenta problemi secondari sovrapposti. Considerando che il programma ricorsivo di numeri di Fibonacci ha molti problemi secondari sovrapposti.
Sottostruttura ottimale
Un dato problema ha una proprietà di sottostruttura ottimale, se la soluzione ottimale del problema dato può essere ottenuta utilizzando soluzioni ottimali dei suoi problemi secondari.
Ad esempio, il problema del percorso più breve ha la seguente proprietà di sottostruttura ottimale:
Se un nodo x si trova nel percorso più breve da un nodo di origine u al nodo di destinazione v, quindi il percorso più breve da u per v è la combinazione del percorso più breve da u per xe il percorso più breve da x per v.
Gli algoritmi standard All Pair Shortest Path come Floyd-Warshall e Bellman-Ford sono esempi tipici di programmazione dinamica.
Fasi dell'approccio dinamico alla programmazione
L'algoritmo di programmazione dinamica è progettato utilizzando i seguenti quattro passaggi:
- Caratterizzano la struttura di una soluzione ottimale.
- Definisci ricorsivamente il valore di una soluzione ottimale.
- Calcola il valore di una soluzione ottimale, in genere dal basso verso l'alto.
- Costruisci una soluzione ottimale dalle informazioni calcolate.
Applicazioni dell'approccio dinamico alla programmazione
- Matrix Chain Moltiplicazione
- Successione comune più lunga
- Problema del commesso viaggiatore