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

i

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

i

3.3. VARIANTE: MEMOIZATION

3.2.2

i

44

Sovrapposizione dei problemi

Il secondo requisito che un problema di ottimizzazione deve possedere affinché
sia utilizzabile la programmazione dinamica è che lo spazio dei sotto-problemi
deve essere “piccolo” nel senso che un algoritmo ricorsivo per la risoluzione del
problema risolve lo stesso sotto-problema più volte, anziché generare ogni volta nuovi sotto-problemi. Tipicamente, il numero complessivo di sotto-problemi
distinti è polinomiale rispetto alla taglia dell’input. Quando un algoritmo ricorsivo rivisita lo stesso problema diverse volte, diciamo che il problema di
ottimizzazione presenta una sovrapposizione di sotto-problemi. Invece, in un
problema per il quale è conveniente usare l’approccio divide-et-impera vengono
generati dei nuovi sotto-problemi ad ogni passo della ricorsione. Gli algoritmi di
programmazione dinamica tipicamente sfruttano la sovrapposizione dei sottoproblemi risolvendo ogni sotto-problema solo una volta e poi memorizzando la
soluzione in una tabella dalla quale può essere successivamente ripreso quando
necessario, utilizzando un tempo costante per l’accesso in memoria.

3.3

Variante: Memoization

Esiste una variante che offre gli stessi vantaggi della programmazione dinamica
mantenendo, però, una struttura top-down. L’idea di base è quella di memorizzare l’inefficiente algoritmo ricorsivo. Così come in un classico algoritmo
di programmazione dinamica, manteniamo una tabella contenente le soluzioni
di sotto-problemi, dove però la struttura di controllo per il riempimento della
tabella è molto più simile a quello dell’algoritmo ricorsivo.
Un algoritmo ricorsivo memorizzato mantiene una entry in una tabella per la
soluzione ad ogni sotto problema. Ogni entry inizialmente contiene un valore
speciale che indica che non è stata ancora inserita l’entry. Quando il sottoproblema è incontrato per la prima volta durante l’esecuzione dell’algoritmo
ricorsivo, la sua soluzione viene computata e memorizzata nella tabella. Ogni
volta che il sotto-problema viene nuovamente incontrato, viene semplicemente
restituito il valore contenuto nella tabella, anziché ricomputare la risposta al
sotto-problema.
In generale, se tutti i sotto-problemi devono essere risolti almeno una volta,
un algoritmo di programmazione dinamica bottom-up di solito è più efficiente
di un algoritmo ricorsivo top-down memorizzato, dato che bisogna aggiungere

i

i
i

i