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 alequazione più tardi invece di calcolarlo di nuovo. Quando si tratta di lunghi processi ed equazioni complessi, ciò consente di risparmiare tempo e crea una soluzione più veloce usando molti meno passaggi.
Le sottostrutture ottimali creano una soluzione trovando la migliore risposta a tutti i sottoproblemi e quindi creando la migliore risposta generale. 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 soluzione migliore nella vita reale, a seconda del tipo di problema e di come si collega al mondo reale.
Durante una di queste operazioni, l'algoritmo di programmazione dinamica cerca di trovare il percorso più breve per la soluzione. Può prendere uno diDue 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.