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

i

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

i

3.2. ELEMENTI DELLA PROGRAMMAZIONE DINAMICA

i

42

al problema, in contrapposizione alla soluzione ottima, dato che possono esserci
più di una soluzione tale che il suo valore è quello ottimo.
Lo sviluppo di un algoritmo di programmazione dinamica può essere suddiviso
in una sequenza di quattro passi:
1. Caratterizzazione della struttura di una soluzione ottima.
2. Definizione ricorsiva della soluzione ottima.
3. Computare il valore di una soluzione ottima in maniera bottom-up.
4. Costruire una soluzione ottima a partire dalle informazioni computate.
I primi tre passi costituiscono la base della soluzione ad un problema con la
programmazione dinamica. L’ultimo passo può essere omesso solo se è richiesto
il valore di una soluzione ottima. Quando si esegue il passo 4, a volte si mantengono in memoria informazioni aggiuntive durante la computazione nel passo
3 per facilitare la costruzione di una soluzione ottima.

3.2

Elementi della programmazione dinamica

Quand’è che dobbiamo cercare una soluzione di programmazione dinamica per
un problema? Gli elementi chiave che un problema di ottimizzazione deve
possedere affinché sia possibile cercare una soluzione di programmazione dinamica sono due: sotto-struttura ottimale e sovrapposizione dei sotto-problemi.
Vedremo anche una variante chiamata memoization, in modo da trarre vantaggio
dalla proprietà di sovrapposizione dei problemi.

3.2.1

Sotto-struttura ottimale

Il primo passo per risolvere un problema di ottimizzazione con la programmazione dinamica è quello di caratterizzare la struttura di una soluzione ottimale. Infatti, un problema presenta una sotto-struttura ottimale se una soluzione
ottimale al problema contiene al suo interno la soluzione ottima dei suoi sottoproblemi. Ogni volta che si presenta un problema di ottimizzazione che presenta

i

i
i

i