Tecniche algoritmiche per la risoluzione di problemi di ottimizzazione

ottima per una stringa di dimensione minore (“A”, che tra l’altro ha come soluzione ottima

0). Se invece i due estremi sono diversi, per rendere la stringa palindroma, possiamo

aggiungere l’estremo sinistro della stringa all’estremità destra, o viceversa l’estremo destro

all’estremità sinistra: la scelta dipende dalla convenienza, e cioè dobbiamo andare a vedere

qual è la soluzione ottima per la stringa privata dell’estremità sinistra e per la stessa privata

dell’estremità destra, prendendo il minor valore. Per esempio, data la stringa “MARA”, e

supponendo di aver già risolto tutti i sottoproblemi di dimensione minore, (cioè quelli

relativi alle sottostringhe “MAR”,”ARA”,”MA”,”AR”,”RA”,“M”,”A”,”R”,”A”) visto che

gli estremi non sono uguali possiamo scegliere tra aggiungere M in fondo, con un costo pari

a 1+costo della soluzione ottima per la stringa “ARA”, oppure aggiungere A all’inizio, con

un costo pari a 1+ costo della soluzione ottima per la stringa “MAR”; il costo di 1 è

imputabile proprio all’aggiunta di un carattere. Ancora una volta, siamo riusciti a costruire la

soluzione di un sottoproblema di dimensione maggiore (“MARA”) utilizzando le soluzioni

ottime di due problemi di dimensione minore (“ARA” e “MAR”). Abbiamo così definito il

generico passo, da applicare per risolvere un sottoproblema di dimensione maggiore a

partire da uno o più sottoproblemi di dimensione minore.

4) A questo punto manca solo un pizzico di organizzazione ed il gioco è fatto: dobbiamo capire

come immagazzinare le soluzioni ottime che via via vengono trovate, per fare in modo che

ogni volta che dobbiamo risolvere un problema di dimensione L (L=j-i+1, 1<=L<N), siano

sempre a nostra disposizione le soluzioni relative ai problemi di dimensione L-1, perché,

come si evince dal punto 3, esse ci serviranno per risolvere il problema di dimensione L. In

pratica, nel nostro caso, dovremo prima risolvere tutti i sottoproblemi di dimensione 1, poi

quelli di dimensione 2, e così via fino ad arrivare a quello di dimensione N. Dato che

abbiamo bisogno di calcolare tutti i sottoproblemi P(i,j), con 1<=i<=j<=N, possiamo

utilizzare un matrice D, di dimensione NxN, che contiene nella cella la soluzione

D[i][j]

ottima per il sottoproblema P(i,j). In base al punto 2, è facile intuire come la diagonale

principale della matrice sia costituita da zeri, dato che tale diagonale memorizza le soluzioni

ottime per il problema ridotto ad ogni singolo carattere della stringa. Ed è proprio a partire

da questi zeri che, procedendo per diagonali (dato che gli elementi di una diagonale

individuano tutti i sottoproblemi di una stessa lunghezza L), e applicando il generico passo

definito al punto 3, costruiamo tutte le soluzioni.

5) Riempita tutta la tabella per diagonali, basterà restituire il valore della cella , che

D[1][N]

sarà la soluzione al problema originario (cioè relativo alla stringa intera, che va dal primo

all’ennesimo carattere).

Formalizzando il problema e definendo f(i,j) il minimo numero di caratteri da inserire nella

sottostringa per renderla palindroma (quindi f(i,j) è la soluzione ottima del

X[i..j]

sottoproblema P(i,j)) possiamo individuare la seguente relazione di ricorrenza:

f ( i , j ) = { 0 se i = j

f( i+1 , j-1 ) se( i<j) e (X[i]=X[j])

1 + min [ f( i , j-1 ) , f( i+1 , j )] se ( i < j ) e (X[i]!=X[j])

}

E’ questo il modello matematico con cui si traduce il problema, ed è a partire da questo modello

astratto che va ideato l’algoritmo. A primo impatto, sembrerebbe logico utilizzare una funzione

ricorsiva basata su questo modello, ma implementandola in questo modo, il tempo di esecuzione

sarebbe esponenziale rispetto ad N (più precisamente il numero di operazioni che dobbiamo

N

aspettarci dall’algoritmo sarà pari a 2 nel caso peggiore), e il che significherebbe che stiamo

utilizzando un metodo di ricerca esaustiva. E’ per ovviare a questo inconveniente che si utilizza la

4

programmazione dinamica: infatti, dal modello matematico, più che dal problema concreto, è facile

rendersi conto che utilizzando una funzione ricorsiva, inevitabilmente calcoleremmo più volte gli

stessi sottoproblemi, mentre utilizzando la programmazione dinamica calcoliamo i sottoproblemi in

un certo ordine (quello specificato al punto 4), e memorizziamo i risultati trovati, cosicché possiamo

riutilizzare i risultati trovati in precedenza, senza che sia necessario ricalcolarli (come fa invece una

procedura ricorsiva). A conti fatti, l’algoritmo di programmazione dinamica che risolve il problema

2

della stringa palindroma richiede un numero di operazioni proporzionale a N (perché ci sono due

cicli di dimensione proporzionale ad N, uno annidato dentro l’altro), che è un tempo immensamente

N

inferiore rispetto al tempo necessario per la ricerca esaustiva. (2 ).

Presentiamo quindi l’algoritmo scritto in linguaggio C, omettendo le operazioni di input per il

prelievo dei dati:

palindroma.c

{ char S[n+1]; /* array contenente la stringa S */

int D[n+1][n+1]; /* tabella di programmazione dinamica */

int i,d,j;

for (i=1;i<=n;i++) D[i][i]=0;

for (d=1;d<n;d++)

for (i=1;i<=n-d;i++)

{ j=d+i; /*calcola l’indice di colonna della cella*/

if (S[i]==S[j])

D[i][j]=D[i+1][j-1];

else

D[i][j]=1 + min(D[i+1][j],D[i][j+1]);

}

printf(“Il costo minimo di inserimenti per rendere ‘%s’ palindroma e’ %d”,S,D[n+1][n+1]);

}

Proviamo ora ad utilizzare la programmazione dinamica per risolvere il problema del ristorante,

seguendo sempre i 5 punti già elencati:

1) Al primo punto, è richiesto di individuare i sottoproblemi, quindi di ridurre il problema per

uno o più suoi parametri. Potremmo ridurre il parametro N, cioè il numero di pietanze, ma

questo non avrebbe molto senso, in quanto non è possibile costruire una soluzione per un

numero L di pietanze (con L<=N) utilizzando la soluzione relativa alle prime L-1 pietanze,

perché per ogni piatto disponiamo di una quantità illimitata. E’ invece possibile ridurre il

problema per il parametro K: infatti, possiamo pensare al sottoproblema P(j), con 0<=j<=K,

come il massimo gradimento realizzabile utilizzando solo j euro, e possiamo costruire delle

soluzioni ottime per sottoproblemi di dimensione maggiore a partire da soluzioni ottime per

sottoproblemi di dimensione minore.

2) Il problema base da risolvere, anche in questo caso, è banale: per j=0, la soluzione ottima al

problema è 0; infatti, senza soldi non possiamo ordinare nulla (supponendo che non ci siano

pietanze gratis, naturalmente), quindi P(0)=0.

3) Il terzo punto, come già visto nel precedente problema, consiste nel verificare se sia

possibile calcolare un sottoproblema di dimensione maggiore utilizzando un sottoproblema

di dimensione minore: nella fattispecie, se sappiamo che la soluzione ottima per j euro è

uguale a P(j), e che tale soluzione è costituita da una certa lista di pietanze, possiamo

provare ad aggiungere a tale lista ogni pietanza (dato che ne disponiamo in quantità

illimitata), e verificare se la soluzione relativa al sottoproblema P(j + costo della nuova

pietanza) è migliore rispetto alle soluzioni precedentemente trovate per tale sottoproblema.

Questo tipo di problema, pur utilizzando sempre la programmazione dinamica, è diverso dal

precedente, in quanto quello calcolava la soluzione corrente, P(i,j), utilizzando una o più

soluzioni precedentemente calcolate (diremo programmazione dinamica all’indietro),

mentre questo si basa sulla propagazione della soluzione (programmazione dinamica in

avanti), perché nel momento in cui esaminiamo un sottoproblema P(j), questo è stato già

5

calcolato, mediante la propagazione della soluzione a partire da sottoproblemi precedenti.

Inoltre è necessario precisare che se P(j) è la soluzione ottima per il problema ridotto a j

euro, P(j) è anche una soluzione ammissibile per il problema P(j+1), anche se non

necessariamente ottima. E’ tuttavia necessario propagare la soluzione anche in questa

direzione perché potrebbe non esserci una combinazione di pietanze la cui sommatoria dei

costi sia pari esattamente a j+1.

4) Per quanto riguarda il modo di immagazzinare la soluzione, dato che dobbiamo ridurre il

problema per il parametro K, possiamo utilizzare un vettore D di dimensione K, che

contiene in posizione j, con 0<=j<=K, la soluzione del problema ridotto ai primi j Euro,

(quindi il valore di P(j)), risolvendo prima i sottoproblemi più piccoli, e poi i più grandi

(quindi scandendo il vettore in ordine crescente di posizione). Prima di tutto, dato che

stiamo trattando un problema di massimo, dovremo impostare tutte le celle del vettore D a 0,

compresa la cella , che in conseguenza a quanto detto nel punto 2, contiene appunto 0.

D[0]

Per riempire il vettore, quindi, partiremo proprio dalla posizione 0, che contiene la soluzione

relativa a 0 euro, l’unica che abbiamo a disposizione. Partendo da questa soluzione (che è

comunque ottima, come da definizione), creiamo altre soluzioni, provando ad aggiungere

tutte le pietanze ad una lista vuota. Ad esempio, dobbiamo controllare se P(0+6)<P(0)+5,

cioè se aggiungendo l’antipasto alla soluzione vuota, otteniamo una soluzione ottima per il

sottoproblema P(6); se tale disuguaglianza è verificata (e lo è per forza quando esaminiamo

P(0)), assegniamo a P(0+6) il valore di P(0) sommato a 5, cioè il gradimento dell’antipasto.

Allo stesso modo, controlleremo se P(0+10)<P(0)+9, e così via. Questo modo di riempire la

tabella di programmazione dinamica è completamente diverso da quello visto nel precedente

(indipendentemente dal fatto che lì la tabella era una matrice, mentre qui è un vettore), ed

infatti procedendo in questo modo non possiamo garantire che per ogni 0<=j<=K venga

trovata una soluzione (anche non ottima): ad esempio, per j=4, non esiste una combinazione

di pietanze che dia un costo totale a 4; per questo motivo ricorriamo a quanto detto alla fine

del punto 3, e propaghiamo anche la soluzione ottima attuale nella cella successiva, e quindi

assegneremo a P(1) il valore di P(0), a P(2) il valore di P(1), e così via, naturalmente sempre

se non esiste una soluzione migliore già memorizzata.

5) Riempita la tabella da 0 a K, restituiamo come soluzione del problema il valore contenuto in

(che è appunto la soluzione relativa al problema originale).

D[K]

Diversamente dal precedente, non è possibile esprimere questo problema con una relazione

di ricorrenza, perché, come abbiamo detto, il tipo di programmazione dinamica utilizzata è

diverso, si basa sulla propagazione in avanti. Infatti, utilizzando la stessa terminologia

dell’esempio precedente, posto f(j)=P(j) (dove P(j) è il sottoproblema corrente, quello che

stiamo esaminando), non possiamo definire esplicitamente f(j) a partire da f(i), con 0<=i<j, ma

viceversa possiamo solo espandere il problema e definire f(g) a partire da f(j), con j<g<=N.

Diremo quindi che i problemi di programmazione dinamica all’indietro si basano sulla

ricorsione (ovvero su una definizione ricorsiva), mentre i problemi di programmazione

dinamica in avanti si basano sulla costruzione, espansione, propagazione.

Presentiamo quindi l’algoritmo risolutivo del problema, sempre in linguaggio C,e omettendo

l’acquisizione dei dati:

ristorante.c

{

int C[n], /* vettore dei costi */

G[n], /* vettore dei gradimenti */

D[k+1]; /* tabella di programmazione dinamica */

int i,j;

for (j=0;j<=k;j++) D[j]=0;

for (j=0;j<K;j++) 6

{ if (D[j]<D[j-1]) D[j]=D[j-1];

for (i=0;i<n;i++) if (D[j+C[i]]<D[j]+G[i]) D[j+C[i]]=D[j]+G[i];

}

printf(“Il massimo gradimento è ottenibile con %d euro e’ %d“,k,D[k]);

}

Come ulteriore esempio nella trattazione della tecnica di programmazione dinamica (che è

certamente la meno intuitiva, e la più difficile da applicare), proviamo a risolvere un problema

proposto nell’edizione delle Olimpiadi Italiane di Informatica tenutesi a Bari nel Marzo 2007.

Supponiamo di dover eseguire la somma algebrica di N interi, avendo a disposizione un robot che