Strutture dati - Programmazione dinamica
L'approccio alla programmazione dinamica è simile al divide et impera nella scomposizione del problema in possibili sottoproblemi più piccoli e tuttavia più piccoli. Ma a differenza di divide et impera, questi sotto-problemi non vengono risolti in modo indipendente. Piuttosto, i risultati di questi problemi secondari più piccoli vengono ricordati e utilizzati per problemi secondari simili o sovrapposti.
La programmazione dinamica viene utilizzata dove abbiamo problemi, che possono essere suddivisi in sotto-problemi simili, in modo che i loro risultati possano essere riutilizzati. Per lo più, questi algoritmi vengono utilizzati per l'ottimizzazione. Prima di risolvere il sotto-problema in mano, l'algoritmo dinamico cercherà di esaminare i risultati dei sotto-problemi risolti in precedenza. Le soluzioni dei sotto-problemi vengono combinate per ottenere la migliore soluzione.
Quindi possiamo dire che -
Il problema dovrebbe essere suddiviso in più piccoli sottoproblemi sovrapposti.
Una soluzione ottimale può essere ottenuta utilizzando una soluzione ottimale di sottoproblemi più piccoli.
Gli algoritmi dinamici utilizzano Memoization.
Confronto
A differenza degli algoritmi avidi, in cui viene affrontata l'ottimizzazione locale, gli algoritmi dinamici sono motivati per un'ottimizzazione complessiva del problema.
A differenza degli algoritmi di divisione e conquista, in cui le soluzioni vengono combinate per ottenere una soluzione globale, gli algoritmi dinamici utilizzano l'output di un sottoproblema più piccolo e quindi cercano di ottimizzare un sotto-problema più grande. Gli algoritmi dinamici utilizzano Memoization per ricordare l'output di sottoproblemi già risolti.
Esempio
I seguenti problemi del computer possono essere risolti utilizzando un approccio di programmazione dinamica:
- Serie di numeri di Fibonacci
- Problema dello zaino
- Torre di Hanoi
- All pair shortest path by Floyd-Warshall
- Sentiero più breve di Dijkstra
- Pianificazione del progetto
La programmazione dinamica può essere utilizzata sia dall'alto verso il basso che dal basso verso l'alto. E naturalmente, la maggior parte delle volte, fare riferimento all'output della soluzione precedente è più economico del ricalcolo in termini di cicli della CPU.