La programmazione dinamica è un concetto sviluppato da Richard Bellman, matematico ed economista.
A quel tempo, Bellman stava cercando un modo per risolvere complessi problemi di ottimizzazione. I problemi di ottimizzazione richiedono di scegliere la soluzione migliore da una serie di opzioni.
Un esempio di problema di ottimizzazione è il problema del commesso viaggiatore. L’obiettivo è trovare il percorso più breve per consentire al venditore di visitare ogni città esattamente una volta e tornare alla città di partenza.
L’approccio di Bellman a questi problemi consisteva nel suddividerli in sottoproblemi più piccoli e risolvere i sottoproblemi dal più piccolo al più grande. Ha quindi archiviato i risultati dei sottoproblemi e li ha riutilizzati per risolvere sottoproblemi più grandi. Questa è l’idea principale alla base della programmazione dinamica.
Sommario:
Che cos’è la programmazione dinamica?
La programmazione dinamica risolve i problemi di ottimizzazione suddividendoli in sottoproblemi più piccoli, risolvendo ogni sottoproblema una volta e memorizzando le loro soluzioni in modo che possano essere riutilizzate e combinate per risolvere il problema più grande. I problemi vengono risolti dal più piccolo al più grande, consentendo il riutilizzo delle soluzioni.
Come funziona la programmazione dinamica?
La risoluzione di un problema utilizzando la programmazione dinamica prevede i seguenti passaggi:
Per vedere questo in azione, calcoliamo il sesto numero di Fibonacci, F(6), usando questo processo.
Innanzitutto, definisci i sottoproblemi che devono essere risolti.
F(n) = F(n-1) + F(n-2) per n > 1
Quindi: F(6) = F(5) + F(4)
F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)
F(2) = F(1) + F(0)
F(1) = 1
F(0) = 0
Il secondo passaggio prevede la risoluzione di ogni sottoproblema utilizzando una funzione ricorsiva o un processo iterativo. Risolviamo i sottoproblemi dal più piccolo al più grande, riutilizzando i risultati di sottoproblemi più piccoli. Questo ci dà quanto segue:
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
F(6) = F(5) + F(4) = 5 + 3 = 8
Mentre risolviamo ciascuno dei sottoproblemi, memorizziamo le soluzioni in un array o in una tabella in modo che possano essere riutilizzate per risolvere sottoproblemi più grandi in questo modo:
Una volta risolti tutti i sottoproblemi, usiamo le soluzioni per costruire la soluzione al problema originale.
In questo caso la soluzione al problema originario è il 6° numero di Fibonacci, che si trova sommando i risultati di F(5) e F(4), sottoproblemi individuati dal problema più grande. Il risultato ci dà 8.
Dove e perché viene utilizzata la programmazione dinamica?
La programmazione dinamica viene utilizzata in aree in cui abbiamo problemi che possono essere suddivisi in sottoproblemi più piccoli e le loro soluzioni vengono utilizzate per risolvere problemi più grandi.
Queste aree includono informatica, economia, matematica e ingegneria. In informatica, viene utilizzato per risolvere problemi che coinvolgono sequenze, grafici e valori interi e nella programmazione competitiva.
In economia, viene utilizzato per risolvere problemi di ottimizzazione nella finanza, nella produzione e nell’allocazione delle risorse. In matematica, la programmazione dinamica viene utilizzata nella teoria dei giochi, nella statistica e nella probabilità, dove viene utilizzata per risolvere problemi di ottimizzazione.
In ingegneria, viene utilizzato per risolvere problemi nell’allocazione delle risorse, nella programmazione, nella produzione, nella comunicazione e nei sistemi di controllo.
Ci sono diversi vantaggi nell’usare la programmazione dinamica per risolvere i problemi di ottimizzazione:
Quando si tratta di risolvere problemi di ottimizzazione, la programmazione dinamica è uno strumento molto utile per garantire l’efficienza nelle soluzioni.
Approcci utilizzati nella programmazione dinamica
Nella programmazione dinamica, vengono utilizzati due approcci per risolvere i problemi di ottimizzazione. Questi sono l’approccio dall’alto verso il basso e l’approccio dal basso verso l’alto.
Approccio dall ‘alto verso il basso
Questo approccio è noto anche come memoizzazione. La memoizzazione è una tecnica di ottimizzazione utilizzata principalmente per rendere i programmi per computer più veloci memorizzando i risultati delle chiamate di funzione nella cache e restituendo i risultati memorizzati nella cache la volta successiva che sono necessari anziché calcolarli nuovamente.
L’approccio dall’alto verso il basso prevede la ricorsione e la memorizzazione nella cache. La ricorsione coinvolge una funzione che chiama se stessa con versioni più semplici del problema come argomento. La ricorsione viene utilizzata per scomporre il problema in sottoproblemi più piccoli e risolvere i sottoproblemi.
Una volta risolto un sottoproblema, il suo risultato viene memorizzato nella cache e riutilizzato ogni volta che si verifica un problema simile. Il top-down è facile da capire e implementare e risolve un sottoproblema solo una volta. Uno svantaggio, tuttavia, è che occupa molta memoria a causa della ricorsione. Questo può portare a un errore di overflow dello stack.
Approccio dal basso verso l’alto
L’approccio bottom-up, noto anche come tabulazione, elimina la ricorsione, sostituendola con l’iterazione, evitando così errori di overflow dello stack.
In questo approccio, un problema di grandi dimensioni viene suddiviso in sottoproblemi più piccoli e le soluzioni per i sottoproblemi vengono utilizzate per risolvere il problema più grande.
I sottoproblemi più piccoli vengono prima risolti dal più grande al più piccolo e i loro risultati vengono memorizzati in una matrice, matrice o tabella, da cui il nome tabulazione.
I risultati memorizzati risolvono problemi più grandi che dipendono dai sottoproblemi. Il risultato del problema originale viene quindi trovato risolvendo il sottoproblema più grande utilizzando i valori calcolati in precedenza.
Questo approccio ha il vantaggio di essere efficiente in termini di memoria e tempo eliminando la ricorsione.
Esempi di problemi risolvibili con la programmazione dinamica
Di seguito sono riportati alcuni problemi di programmazione che possono essere risolti utilizzando la programmazione dinamica:
#1. Problema dello zaino
Fonte: Wikipedia
Uno zaino è una borsa fatta di tela, nylon o pelle tipicamente legata sul retro e utilizzata da soldati ed escursionisti per trasportare rifornimenti.
Nel problema dello zaino, ti viene presentato uno zaino e, data la sua capacità di carico, devi scegliere gli oggetti, ciascuno con il suo valore. La tua selezione dovrebbe essere tale da ottenere il valore totale massimo degli articoli raccolti e il peso degli articoli è inferiore o uguale alla capacità dello zaino.
Di seguito è riportato un esempio del problema dello zaino:
Immagina di fare un’escursione e di avere uno zaino con una capacità di 15 chilogrammi. Hai un elenco di articoli che puoi portare con te, insieme ai loro valori e pesi, come mostrato nella tabella seguente:
OggettoValorePesoTenda2003Sacco a pelo1502Stufa501Cibo1002Borraccia100,5Kit pronto soccorso251
Scegli un sottoinsieme degli articoli da portare in modo tale che il valore totale degli articoli sia massimizzato mentre il peso totale è inferiore o uguale alla capacità dello zaino, che è di 15 chilogrammi.
Le applicazioni del mondo reale del problema dello zaino implicano la selezione di titoli da aggiungere a un portafoglio per ridurre al minimo il rischio e massimizzare il profitto e trovare i modi meno dispendiosi per tagliare le materie prime.
#2. Problema di programmazione
Un problema di pianificazione è un problema di ottimizzazione in cui l’obiettivo è assegnare in modo ottimale le attività a un insieme di risorse. Le risorse possono essere macchine, personale o altre risorse utilizzate per completare le attività.
Di seguito è riportato un esempio di problema di pianificazione:
Immagina di essere un project manager responsabile della pianificazione di una serie di attività che devono essere completate da un team di dipendenti. Ogni attività ha un’ora di inizio, un’ora di fine e un elenco di dipendenti qualificati per completarla.
Ecco una tabella che descrive i compiti e le loro caratteristiche:
CompitoOra di inizioOra di fineDipendenti qualificatiT1911A, B, CT21012A, CT31113B, CT41214A, B
Assegna ogni attività a un dipendente per ridurre al minimo il tempo di completamento totale.
Il problema della pianificazione può essere riscontrato nell’industria manifatturiera quando si cerca di ottimizzare l’allocazione di risorse come macchine, materiali, strumenti e manodopera.
Può anche essere riscontrato in ambito sanitario quando si ottimizza l’uso di posti letto, personale e forniture mediche. Altri settori in cui può verificarsi questo problema sono la gestione dei progetti, la gestione della catena di approvvigionamento e l’istruzione.
#3. Problema del commesso viaggiatore
Fonte: Wikipedia
Questo è uno dei problemi di ottimizzazione più studiati che possono essere risolti utilizzando la programmazione dinamica.
Il problema del commesso viaggiatore fornisce un elenco di città e le distanze tra ciascuna coppia di città. Devi trovare il percorso più breve possibile che visiti ogni città esattamente una volta e ritorni alla città di origine.
Di seguito è riportato un esempio di problema del commesso viaggiatore:
Immagina di essere un venditore che ha bisogno di visitare un insieme di città nel più breve tempo possibile. Hai un elenco delle città che devi visitare e le distanze tra ogni coppia di città, come mostrato nella tabella qui sotto:
CittàABCDEA010152030B100352515C153503020D202530010E301520100
Il problema del venditore ambulante può essere riscontrato nell’industria del tempo libero quando si cerca di pianificare i percorsi per i turisti, nella logistica quando si pianifica la spedizione di merci, nei trasporti quando si pianificano i percorsi degli autobus e nel settore delle vendite, tra gli altri.
Chiaramente, la programmazione dinamica ha molte applicazioni nel mondo reale, il che aiuta a saperne di più.
Considera le seguenti risorse per esporre la tua conoscenza della programmazione dinamica.
Risorse
Programmazione dinamica di Richard Bellman
La programmazione dinamica è un libro di Richard Bellman, che ha ideato la programmazione dinamica e l’ha sviluppata nelle sue fasi iniziali.
Il libro è scritto in un modo di facile comprensione che richiede solo conoscenze di base di matematica e calcolo per comprendere il testo. Nel libro, Bellman introduce la teoria matematica di un processo decisionale a più stadi che è fondamentale nella programmazione dinamica.
Il libro esamina quindi i problemi del collo di bottiglia nei processi di produzione a più stadi, i teoremi di esistenza e unicità e l’equazione dell’inventario ottimale.
La cosa migliore del libro è che Bellman offre esempi di molti problemi complessi in campi come la logistica, la teoria della programmazione, la teoria della comunicazione, l’economia matematica e i processi di controllo e mostra come la programmazione dinamica può risolvere i problemi.
Il libro è disponibile in versione Kindle, copertina rigida e tascabile.
Corso di Laurea Magistrale in Algoritmi di Programmazione Dinamica
Questo corso master sugli algoritmi di programmazione dinamica di Udemy è offerto da Apaar Kamal, un ingegnere del software di Google, e Prateek Narang, che ha anche lavorato con Google.
Il corso è ottimizzato per aiutare gli studenti a eccellere nella competizione di programmazione che presenta molti problemi che richiedono una programmazione dinamica.
A parte i concorrenti di programmazione, il corso è ideale per i programmatori che desiderano migliorare la loro comprensione degli algoritmi e per le persone che si preparano per colloqui di programmazione e turni di programmazione online.
Il corso, della durata di oltre 40 ore, approfondisce la programmazione dinamica. Il corso offre innanzitutto un aggiornamento su concetti come ricorsione e backtracking.
Copre quindi la programmazione dinamica nella teoria dei giochi, stringhe, alberi e grafici, esponenziazione di matrici, maschere di bit, combinatoria e sottosequenze, problemi di partizione e programmazione dinamica multidimensionale, tra molti altri concetti.
Elementi essenziali di programmazione competitiva, algoritmi principali
Udemy offre un corso di base sulla programmazione competitiva di Prateek Narang e Amal Kamaar che copre la programmazione dinamica, la matematica, la teoria dei numeri e le strutture dati e gli algoritmi avanzati in un modo utile e pertinente per i programmatori competitivi.
Il corso offre un aggiornamento sulle strutture dati e sugli algoritmi prima di immergersi in algoritmi e tecniche più complessi che tornano utili nella programmazione competitiva.
Il corso copre la programmazione dinamica, la matematica, la teoria dei giochi, il pattern matching, il Bitmasking e una miriade di algoritmi avanzati utilizzati e testati nelle competizioni di programmazione.
Il corso Udemy è suddiviso in 10 moduli e 42 sezioni e fornisce molte domande pratiche dopo ogni sezione. Questo corso bestseller è un must per chiunque sia interessato alla programmazione competitiva.
Parole finali
La programmazione dinamica è un’abilità utile per qualsiasi programmatore per imparare a migliorare la risoluzione dei problemi del mondo reale. Pertanto, i programmatori dovrebbero considerare di passare attraverso le risorse suggerite per aggiungere questo strumento cruciale alla loro cassetta degli attrezzi.
Successivamente, puoi controllare i linguaggi di programmazione da utilizzare nella scienza dei dati.