Resúmenes

La programmazione dinamica è una tecnica di realizzazione di algoritmi che risolto un problema utilizzando le soluzioni di sotto-problemi. Il termine "programmazione" fa riferimento all'uso di tabelle per appuntare le soluzioni dei sotto-problemi durante l'applicazione manuale della tecnica e non alla scrittura di codice.

Anche la tecnica Divide et Impera partiziona un problema in sotto-problemi e risolve il problema attraverso un'opportuna combinazione delle sotto-soluzioni. La differenza tra le due tecniche è che Divide et Impera intende individuare solo quei sotto-problemi che sono rilevanti per la soluzione del problema originario (metodo top-down, dall'alto verso il basso) mentre la programmazione dinamica parte direttamente da tutti i sotto-problemi più piccoli per poi arrivare alla soluzione del problema originario (metodo bottom-up, dal basso verso l'alto). Il diverso metodo adoperato comporta un diverso schema di algoritmo: l'algoritmo tipico Divide et Impera è ricorsivo mentre l'algoritmo tipico della programmazione dinamica è iterativo. Ma la differenza sostanziale non è tanto nell'uso della ricorsione o meno - sappiamo che la ricorsione può sempre essere sostituita dalla iterazione; la differenza è il diverso numero di sotto-problemi risolti dalle due tecniche.

Nel caso di un problema in cui solo un numero limitato di sotto-problemi è rilevante per determinare la soluzione finale, la tecnica Divide et Impera risulta più conveniente in quanto l'extra-lavoro per individuare i sotto-problemi è ripagato dal minor numero di sotto-problemi da risolvere. D'altra parte, se tutti o quasi tutti i sotto-problemi devono essere comunque risolti e, addirittura, accade che la soluzione di uno stesso sotto-problema debba essere usata più volte, allora la programmazione dinamica risulta essere la tecnica più conveniente poiché essa parte direttamente dalla soluzione di tutti i problemi di dimensione atomica per ricomporre via via le soluzioni di tutti i sotto-problemi di dimensioni maggiori.

Possiamo affermare che la tecnica della programmazione dinamica va adoperata allorquando la soluzione di un problema è ottenibile dalla combinazione di tutti o quasi tutti i suoi sotto-problemi e/o quando la soluzione di uno stesso sotto-problema debba essere utilizzata più volta. Cioè la programmazione dinamica va utilizzata per quei problemi per i quali la risoluzione attraverso i sotto-problemi non è semplice dal punto di vista computazionale.

Per concludere la descrizione generale della tecnica di programmazione dinamica, dobbiamo stabilire sotto quali condizioni essa risolve correttamente un problema. Precisiamo che la programmazione dinamica è sostanzialmente usata per risolvere problemi di ottimizzazione senza esplorare tutte le soluzioni possibili. Tuttavia non c'è garanzia che sia possibile costruire l'ottimo sulla base degli ottimi dei sotto-problemi. Affinché ciò avvenga deve valere il principio di ottimalità, cioè la soluzione ottima del problema dipende dalla soluzione ottima dei vari suoi sotto-problemi e non da eventuali soluzioni sub-ottime.