Cos'è la programmazione dinamica?

La programmazione dinamica, quando si fa riferimento al campo dell'informatica, descrive un gruppo di algoritmi di computer simili intesi a risolvere problemi complessi rompendo il problema in serie di problemi più piccoli.Creato per la prima volta da Richard Bellman negli anni '50, la programmazione dinamica funziona con problemi che si sovrappongono ai sottoproblemi o alle sottostrutture ottimali.Per capire come funziona la programmazione dinamica, è meglio comprendere il concetto alla base di questi due termini.

Sottoproblemi sovrapposti descrivono equazioni complicate che, se suddivise in serie più piccole di equazioni, riutilizzare parti delle equazioni più piccole più di una volta per raggiungere una risposta.Ad esempio, un'equazione matematica informata di calcolare tutti i possibili risultati usando un insieme di numeri può calcolare lo stesso risultato numerose volte mentre calcola altri risultati solo una volta.La programmazione dinamica direbbe a questo problema che dopo aver calcolato il risultato la prima volta dovrebbe salvare quel risultato e collegare la risposta all'equazione in seguito invece di calcolarla di nuovo.Quando si tratta di lunghi processi ed equazioni complessi, ciò consente di risparmiare tempo e crea una soluzione più veloce utilizzando molti meno passaggi.

Le sottostrutture ottimali creano una soluzione trovando la migliore risposta a tutti i sottoproblemi e quindi creando la migliore risposta complessiva.Dopo aver abbattuto un problema complesso in problemi più piccoli, il computer utilizza quindi un sistema matematico per determinare quale sia la risposta migliore per ogni problema.Calcola la risposta al problema originale dalle risposte più piccole.I difetti esistono con questo processo.Sebbene fornisca la soluzione che funziona meglio matematicamente, può o meno essere la migliore soluzione nella vita reale, a seconda del tipo di problema e di come si collega al mondo reale.

Durante una di queste operazioni, la programmazione dinamicaL'algoritmo cerca di trovare il percorso più breve per la soluzione.Può essere necessario uno dei due approcci per farlo.L'approccio top-down rompe l'equazione in equazioni più piccole e riutilizza le risposte per queste equazioni quando necessario.L'approccio bottom-up cerca di risolvere il valore matematico più piccolo dopo aver abbattuto l'equazione e poi si fa strada verso il più grande da lì.Entrambi gli approcci risparmiano tempo, ma la programmazione dinamica funziona solo quando il problema originale può rompersi in equazioni più piccole che ad un certo punto vengono riutilizzate per risolvere l'equazione.