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

i

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

i

3.2. ELEMENTI DELLA PROGRAMMAZIONE DINAMICA

i

43

una sotto-struttura ottimale, con buona probabilità è applicabile l’approccio della programmazione dinamica. Nella programmazione dinamica, costruiamo una
soluzione ottima al problema partendo da soluzioni ottime ai sotto-problemi.
Per individuare la sotto-struttura ottimale di un problema si possono seguire i
seguenti passi:
1. Mostrare che una soluzione al problema consiste nel fare una scelta. Tale
scelta consente di non dover più risolvere uno o più sotto-problemi.
2. Supporre che per un dato problema si è in possesso della scelta che porta
ad una soluzione ottima. Non è importante come è stata ottenuta la scelta.
3. Data la scelta, si determinano i sotto-problemi che ne seguono, e come
caratterizzare al meglio lo spazio dei sotto-problemi risultante. In generale conviene cercare di tenere lo spazio dei sotto-problemi il più semplice
possibile ed espanderlo solo se necessario.
4. Mostrare che le soluzioni ai sotto-problemi utilizzate all’interno della soluzione
ottimale al problema originario devono a loro volta essere ottimali. Si
suppone per assurdo che la soluzione al sotto-problema non è ottimale e
giungere ad un assurdo. In particolare, si esclude la soluzione non ottimale
al sotto-problema e se ne aggiunge una ottimale,