Vai al contenuto

Principi della programmazione dinamica

Parte 3 · Programmazione dinamica · Capitolo 16 · Dispensa, volume 3 (PDF) · Slide · Esercizi: Principi

Prerequisiti

Obiettivi

Alla fine di questo capitolo saremo in grado di:

  • spiegare perché l'enumerazione di tutte le soluzioni ammissibili non funziona, e che cosa fa invece un algoritmo di PD;

  • enunciare i principi di divisione, conquista e combinazione, e la differenza fra sottoproblemi indipendenti e sottoproblemi sovrapposti;

  • verificare su un problema la sottostruttura ottima e i sottoproblemi sovrapposti;

  • elencare i passi di un algoritmo di PD: ricorrenza, casi base, tabella di memorizzazione e ricostruzione di una soluzione ottima.

16.1 Dividere, conquistare, combinare

Definizione 16.1: Algoritmo di PD

Un algoritmo di programmazione dinamica (PD) è un algoritmo esatto per trovare una soluzione ottima di una classe di problemi di ottimizzazione con proprietà specifiche (Sezione 16.2). Decompone il problema originale in sottoproblemi più piccoli dello stesso tipo e riusa l'informazione calcolata risolvendoli.

  • Un algoritmo a forza bruta elenca tutte le soluzioni ammissibili, e il loro numero cresce in modo esponenziale (\(2^n\) sottoinsiemi di oggetti per il KP). Un algoritmo di PD evita questa enumerazione riusando i valori ottimi dei sottoproblemi.

  • Un algoritmo di PD sfrutta il paradigma divide et impera (dividere, conquistare e combinare), i cui principi sono:

    1. Principio di divisione \(\rightsquigarrow\) decomporre il problema in un certo numero di sottoproblemi, che sono problemi più piccoli dello stesso tipo;

    2. Principio di conquista \(\rightsquigarrow\) risolvere i sottoproblemi in modo ricorsivo. Se le dimensioni dei sottoproblemi sono abbastanza piccole, risolverli direttamente;

    3. Principio di combinazione \(\rightsquigarrow\) combinare soluzioni ottime dei sottoproblemi per ottenere una soluzione ottima del problema originale.

  • Gli algoritmi di PD dividono il problema in sottoproblemi indipendenti, li risolvono ricorsivamente e poi ne combinano le soluzioni per risolvere il problema originale. Qui indipendenti significa che ogni sottoproblema generato dalla divisione si può risolvere senza influire sugli altri.

  • In un algoritmo di PD lo stesso sottoproblema può essere generato più volte durante il processo ricorsivo di soluzione. Per evitare calcoli ridondanti, il valore ottimo di ogni sottoproblema si memorizza in una tabella di memorizzazione.

  • Ogni volta che lo stesso sottoproblema viene generato di nuovo, il suo valore ottimo si legge dalla tabella di memorizzazione invece di essere ricalcolato.

16.2 Proprietà del problema richieste dagli algoritmi di PD

  • Gli algoritmi di PD funzionano solo per problemi di ottimizzazione combinatoria che ammettono un processo di decomposizione ricorsiva con le seguenti proprietà:

    1. Sottostruttura ottima \(\rightsquigarrow\) l'idea è che, quando un problema è decomposto in sottoproblemi più piccoli, una soluzione ottima del problema si può costruire a partire da soluzioni ottime dei sottoproblemi.

      In pratica, per verificare questa proprietà si controllano di solito i seguenti punti:

      • il problema si può decomporre in sottoproblemi più piccoli dello stesso tipo;

      • i sottoproblemi si possono risolvere in modo indipendente;

      • le soluzioni ottime dei sottoproblemi si possono combinare per ottenere una soluzione ottima del problema originale;

      • si può stabilire una relazione di ricorrenza per calcolare il valore ottimo del problema.

    2. Sottoproblemi sovrapposti \(\rightsquigarrow\) l'idea è che, quando un problema è decomposto ricorsivamente in sottoproblemi più piccoli, gli stessi sottoproblemi possono essere generati più volte.

      In pratica, per verificare questa proprietà si controllano di solito i seguenti punti:

      • il processo di decomposizione ricorsiva genera lo stesso sottoproblema più di una volta;

      • è possibile memorizzare i valori ottimi dei sottoproblemi in una tabella di memorizzazione; allora, ogni volta che lo stesso sottoproblema serve di nuovo, il suo valore ottimo si legge dalla tabella invece di essere ricalcolato.

Gli algoritmi di PD si possono usare quando un problema ha sia la sottostruttura ottima sia i sottoproblemi sovrapposti.

16.3 Passi per progettare un algoritmo di PD

  • Identificare il processo di decomposizione ricorsiva che, a partire da un problema dato, genera i suoi sottoproblemi, che sono problemi più piccoli dello stesso tipo, e verificare le due proprietà seguenti:

    1. la proprietà di sottostruttura ottima, controllando che una soluzione ottima del problema si possa ottenere combinando le soluzioni ottime dei suoi sottoproblemi;

    2. la proprietà dei sottoproblemi sovrapposti, controllando se il processo di decomposizione ricorsiva genera più volte gli stessi sottoproblemi;

  • La costruzione di un algoritmo di PD segue di solito due passi principali:

    1. calcolo del valore ottimo

      • definire una relazione di ricorrenza che esprime il valore ottimo di un problema in funzione dei valori ottimi dei suoi sottoproblemi;

      • specificare i casi base, ossia i sottoproblemi la cui soluzione ottima è immediata (il valore ottimo ne segue direttamente);

      • determinare un algoritmo di PD che calcoli i valori ottimi di tutti i sottoproblemi rilevanti, di solito dal basso verso l'alto (bottom-up), memorizzando ogni valore in una tabella di memorizzazione, in modo che sia calcolato una sola volta e letto ogni volta che serve di nuovo;

    2. costruzione di una soluzione ottima

      • specificare l'informazione aggiuntiva da memorizzare per ricostruire una soluzione ottima del problema.

      • identificare il modo di costruire una soluzione ottima dall'informazione memorizzata.

16.4 Gli algoritmi di PD di questo modulo

  • Ogni algoritmo di PD di questo modulo segue i due passi precedenti: una ricorrenza con i suoi casi base dà il valore ottimo, una tabella aggiuntiva dà una soluzione ottima.
Problema Stato Ricorrenza su Passi
KP \(v(j,k)\) oggetti e capacità \(\Theta(nc)\)
UKP \(v(k)\) capacità \(\Theta(nc)\)
BKP \(v(j,k)\) oggetti e capacità \(\Theta(nc\,b_{\max})\)
SSP \(r(j,k)\) oggetti e valori da raggiungere \(\Theta(nc)\)
MCKP \(v(h,k)\) classi e capacità \(\Theta(nc)\)
MDKP \(v(j,k_1,\dots,k_m)\) oggetti e vettori di capacità \(\Theta(m\,n\prod_{d}(c_d+1))\)
KPS \(v(h,k)\), \(u(h,i,k)\) classi, oggetti e capacità \(\Theta(nc)\)
MKP \(v(j,k_1,\dots,k_m)\) oggetti e capacità residue \(\Theta(m\,n\prod_{i}(c_i+1))\)
RCP \(v(\ell)\) lunghezze dell'asta \(\Theta(n^2)\)
CCP \(v(k)\) importi del resto \(\Theta(nc)\)
ULS \(v(t)\) periodi \(\Theta(m^2)\)
CLS \(v(t,k)\) periodi e scorte \(O(mDC)\)

  • In tutti gli esempi numerici i dati sono interi: il numero di stati è finito, e ogni stato è una cella della tabella. I tempi di esecuzione \(\Theta(nc)\), \(\Theta(nc\,b_{\max})\) e \(O(mDC)\) contengono numeri dell'input (una capacità, un bound, una domanda), non solo la sua dimensione: sono pseudo-polinomiali.

  • Con un vettore di capacità (MDKP, MKP) la tabella ha una dimensione per ogni capacità: il numero di passi è pseudo-polinomiale solo per un numero fissato \(m\) di dimensioni o di zaini.

16.5 Errori tipici

Attenzione

  • Usare la PD senza la sottostruttura ottima. Se una soluzione ottima del problema non si può costruire da soluzioni ottime dei sottoproblemi, la ricorrenza è sbagliata.

  • Usare la PD senza sottoproblemi sovrapposti. Se ogni sottoproblema compare una sola volta, memorizzare i valori in una tabella non porta alcun vantaggio: l'algoritmo di PD è una semplice ricorsione.

  • Dimenticare i casi base. La ricorrenza ha bisogno dei sottoproblemi il cui valore ottimo è immediato, altrimenti la ricorsione non termina.

  • Confondere il valore ottimo con una soluzione ottima. La tabella dei valori ottimi non dà la soluzione: serve una tabella aggiuntiva delle decisioni.

16.6 In sintesi

In sintesi

  • Un algoritmo di PD è un algoritmo esatto che divide un problema in sottoproblemi dello stesso tipo, li risolve ricorsivamente e combina le soluzioni ottime.

  • Funziona quando il problema ha la sottostruttura ottima e sottoproblemi sovrapposti; i valori ottimi si memorizzano in una tabella di memorizzazione.

  • La progettazione ha due passi: il valore ottimo (ricorrenza, casi base, tabella bottom-up) e una soluzione ottima (decisioni memorizzate e lette a ritroso).

  • La forza bruta richiede tempo esponenziale; la PD richiede un tempo polinomiale nel numero di stati, e pseudo-polinomiale quando un numero dell'input è una dimensione della tabella.

Esercizi su questo capitolo: Principi