Tecniche algoritmiche per la risoluzione di problemi di ottimizzazione

navigare in S non considerando tutte le soluzioni ammissibili, ma solo una parte di esse (o

addirittura solo una, in qualche caso), ovvero un sottoinsieme di S di cardinalità polinomiale

(cioè il cui numero degli elementi sia esprimibile nei termini di un polinomio definito in funzione di

N, e non di una funzione esponenziale in N).

Fatte queste premesse, possiamo elencare le tecniche algoritmiche di programmazione:

- Programmazione dinamica;

- Greedy;

- Ricerca esaustiva.

Sull’ultima tecnica, di cui abbiamo appena parlato, e su cui ritorneremo in seguito, è bene precisare

un aspetto fondamentale: per mezzo di essa qualunque problema di ottimo può essere risolto,

perché è il metodo più generale, che permette di visitare tutto lo spazio delle soluzioni ammissibili,

eliminando il dubbio (che invece ci porremo nella scelta delle altre tecniche) che il sottoinsieme di

S in cui si effettua la ricerca contenga effettivamente la soluzione ottima. Come è stato già detto,

infatti, la tecnica della ricerca esaustiva è utilizzata solo quando non è possibile utilizzare le altre

due, che sono molto più efficienti in termini di tempo.

Programmazione dinamica

Passiamo quindi ad esaminare la tecnica della programmazione dinamica, che risolve il problema

con una filosofia di tipo bottom-up: infatti, vengono risolti prima i problemi di dimensione più

piccola, per poi, a partire da questi, risolvere quelli di dimensione via via maggiore, fino a che non

si arriva alla soluzione del problema iniziale (quello di dimensione N).

Prima di utilizzare la programmazione dinamica per risolvere il problema del ristorante (vedi

sopra), presentiamo un esempio più semplice e immediato, che permetta di capire meglio i

meccanismi di questa tecnica, che è piuttosto complessa. Il problema è definito nel modo seguente:

data una stringa X di lunghezza N, trovare il minimo numero di caratteri da inserire in tale stringa

perché essa diventi palindroma (ovvero si possa leggere indistintamente in un verso, o nell’altro).

Verranno ora descritti tutti i passi per arrivare alla soluzione del problema, e contemporaneamente

verrà presentato il paradigma della programmazione dinamica:

1) Come primo punto dobbiamo scomporre il problema, cioè individuare i sottoproblemi del

problema originario: nel nostro esempio, i sottoproblemi da risolvere corrispondono alle

sottostringhe , cioè tutte le possibili parti di stringa di dimensione che va da 1 a N

X[i..j]

(dove N è la lunghezza della stringa X) che si possono formare con la stringa X. Ad

esempio, posto N=5, e X=MARAS, i sottoproblemi sono le stringhe

“M”,”A”,”R”,”A”,”S”,”MA”,”AR”,”RA” ,”AS”,”MAR”,”ARA”,”RAS”,”MARA” e infine

”ARAS”; bisogna, generalizzando, ridurre uno o più parametri del problema: in questo caso

abbiamo ridotto il parametro N ovvero la lunghezza della stringa, riferendoci alle

sottostringhe , con 1<=i<=j<=N;

X[i..j]

2) Come seconda cosa dobbiamo individuare i problemi base, cioè quelli che possiamo

risolvere immediatamente: nel nostro caso, possiamo notare che se la stringa è costituita da

una solo carattere, è già palindroma, quindi, la soluzione ottima per questo sottoproblema è

0, dato che non dobbiamo aggiungere nessun carattere;

3) Come terzo e più importante punto, dobbiamo assicurarci che questa tecnica sia idonea a

risolvere il problema, e per fare questo dobbiamo capire se, a partire da una o più soluzioni

ottime già trovate per i sottoproblemi di dimensione minore, sia possibile trovare la

soluzione per i sottoproblemi di dimensione maggiore. Nel nostro esempio, possiamo notare

che se una sottostringa ha gli estremi uguali, ad esempio come “ARA”, la soluzione ottima

sarà data dalla soluzione relativa alla stringa privata degli estremi: siamo riusciti quindi a

costruire una soluzione ottima (quella per la stringa “ARA”), partendo dalla soluzione

3

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.