Tesi Robotica Un coprocessore per Stereo-Matching: Profiling ... | Page 41

i

i
“MF_Tesi” — 2011/9/12 — 11:39 — page 41 — #41

i

Capitolo

i

3

Programmazione Dinamica
3.1

Introduzione

La programmazione dinamica, così come l’approccio ricorsivo divide-et-impera,
è utilizzato per risolvere problemi combinando le soluzioni di sotto-problemi.
In generale gli algoritmi basati su divide-et-impera partizionano il problema
in sotto-problemi indipendenti, risolvono ricorsivamente i sotto-problemi, ed
infine combinano le soluzioni per risolvere il problema di partenza. La programmazione dinamica, invece è applicabile quando i sotto-problemi non sono indipendenti, cioè quando i sotto-problemi condividono dei “sotto sotto-problemi”.
In situazioni come questa, un algoritmo divide-et-impera esegue più lavoro del
necessario, in quanto risolve più di una volta lo stesso sotto-problema comune.
Un algoritmo di programmazione dinamica risolve ogni sotto sotto-problema
una sola volta, dopo di ché il risultato viene memorizzato in una tabella, in modo da evitare di rielaborare nuovamente la risposta ad un sotto sotto-problema
già incontrato.
La programmazione dinamica di solito si applica ai problemi di ottimizzazione.
In questa categoria di problemi ci sono molte possibili soluzioni. Ogni soluzione
ha un valore, e noi desideriamo la soluzione con il valore ottimale (il massimo o
il minimo, dipende dal problema). Tale soluzione è detta una soluzione ottima

41

i

i
i

i