Tecniche algoritmiche per la risoluzione di problemi di ottimizzazione

Premessa:

La seguente tesina è il risultato concreto della mia esperienza alle Olimpiadi Italiane di Informatica, e vuole essere non solo un approfondimento per l’esame di maturità, ma soprattutto uno stimolo per quei ragazzi volenterosi che volessero cimentarsi in questa competizione, che personalmente mi ha dato tante soddisfazioni e molto più ha aperto i miei orizzonti conoscitivi, anche in vista degli studi universitari.

Sicuramente non basterà una semplice lettura di questo scritto per acquisire le abilità necessarie per essere in grado di risolvere tutti i problemi delle Olimpiadi, ma senz’altro a lavoro finito il lettore avrà posto le basi per l’approccio a questo genere di problematiche, e se la lettura avrà raggiunto lo scopo - da me fortemente voluto – di interessarlo, sono certo che egli proverà a misurarsi con tali problemi, con la speranza che arrivi a scoprire la stessa passione che ha scoperto me: ritengo perciò opportuno augurare ai ragazzi che leggeranno questo documento di scoprirsi portati ed interessati, ed invogliarli a mettere in campo tutto il loro impegno e la loro passione.

Vincenzo Maffione 5°H

Introduzione

L’informatica oggi permette di dare una risposta ai molteplici problemi che possono presentarsi nel mondo del lavoro, come nella vita di tutti i giorni: grazie ad essa, ad esempio, le aziende possono immagazzinare grandi quantità di dati e gestirli con relativa facilità, controllare facilmente grandezze fisiche nei processi industriali, come anche rendere possibile il funzionamento di dispositivi come il Navigatore Satellitare, o fornire supporti di memorizzazione digitale.

L’elenco di ciò che lo sviluppo delle tecnologie informatiche ha reso possibile (o ha facilitato) è certamente molto più lungo, e non si esaurisce qui. L’informatica, quindi, deve dare una risposta ai problemi concreti, reali, con cui siamo tenuti a confrontarci, e per far ciò deve fornire delle metodologie che permettono di effettuare il passaggio fondamentale dal problema astratto al procedimento che permette di automatizzare la risoluzione dello stesso nel caso generale: questo passaggio è molto importante per una particolare categoria di problemi, ovvero i problemi di ottimizzazione.

Un problema di ottimizzazione è un problema concreto (nel senso che non implica di per sé un collegamento con l’informatica), che una volta trasformato in modello matematico, richiede di ricercare una precisa conformazione dei suoi dati (istanza in ingresso) che ottimizzi uno o più suoi parametri.

Esprimendo il concetto in un modo un po’ più formale, possiamo dire che un problema di ottimizzazione richiede di cercare, nello spazio delle soluzioni ammissibili, la soluzione migliore, che chiameremo soluzione ottima (tenendo conto che ce ne potrebbero essere più di una): per fare un esempio banale, la semplice ricerca del massimo in un insieme di N numeri è un problema di ottimizzazione; in questo caso lo spazio delle soluzioni ammissibili coincide con l’insieme stesso, e il procedimento più evidente ed immediato che porta alla soluzione ottima consiste nello scandire tutti gli elementi e restituire il massimo.

Ma diamo una definizione più formale del termine “spazio delle soluzioni ammissibili”, dato che intorno a questo spazio ruoterà tutta la trattazione di questa tesi. Lo spazio delle soluzioni ammissibili è un insieme di oggetti, detti “certificati”, che rappresentano ognuno una soluzione ammissibile per un determinato problema; a sua volta un certificato può essere definito come un insieme di numeri e/o stringhe, tale che sia possibile verificare, in tempo polinomiale (cioè con un numero di operazioni proporzionale ad una funzione esprimibile con un polinomio definito sulla dimensione N dell’istanza, ad esempio P(N)=N²-3N+2), la sua proprietà di essere una soluzione (anche non ottima) per il problema.

Riprendendo l’esempio di prima, tutti gli N numeri dell’insieme, sono certificati (semplici, perché consistono di un solo numero), e non è neanche necessario effettuare alcun controllo, perché il numero, in quanto tale, risponde già al requisito di essere potenzialmente una soluzione per il problema, e quindi fa parte automaticamente dello spazio delle soluzioni ammissibili.

Come è facile intuire, la difficoltà nella risoluzione di problemi di ottimizzazione, non sta nel controllo del certificato, ma nella costruzione della soluzione ammissibile (quindi il controllo è implicito), e ancor di più nell’arrivare alla soluzione ottima ammissibile: è proprio questo il compito che viene affidato alle tecniche algoritmiche. Ma passiamo ad un esempio più significativo, che permetta di individuare meglio il problema della costruzione, e il concetto di soluzione ottima.

Esempio del ristorante

Immaginiamo che Tizio debba andare in un ristorante, e quindi ordinare al cameriere una certa lista di pietanze, scegliendole da un menù contenente N voci: supponiamo che ad ogni pietanza sia associato un costo (espresso in euro), ed una valutazione personale fatta da Tizio, che esprime, con un intero positivo, il suo gradimento per quella pietanza, ed infine supponiamo per semplicità che una stessa pietanza possa essere ordinata un numero illimitato di volte.

Se Tizio ha K euro in tasca, qual è la lista di pietanze che egli deve ordinare, perché venga massimizzato il suo gradimento, rimanendo ovviamente nel limite di K euro?

Consideriamo quest’istanza del problema di dimensione:

Pietanza Costo Gradimento

• Antipasto 6 € 5
• Primo 10 € 9
• Insalata 3 € 2
• Secondo di pesce 19 € 14
• Secondo di carne 16 € 9
• Frutta 5 € 10

Se Tizio dispone di 24 € (quindi se K=24), allora la lista di pietanze che garantisce il maggior gradimento è formata da 4 porzioni di frutta e 1 di insalata, con un costo di 23 €, e gradimento totale pari a 42.

Come supposto, abbiamo rispettato il limite di spesa, e siamo sicuri che nessun’altra combinazione di pietanze possa dare un gradimento più alto di questa.

La domanda che nasce spontanea, a questo punto, è: come si fa ad arrivare a questa soluzione? Il modo più facile (ma anche il meno elegante, e soprattutto improponibile in termini di numero di operazioni necessarie), consiste nel creare materialmente lo spazio delle soluzioni ammissibili, ed all’interno di questo effettuare una semplice massimizzazione: in qualche modo, il problema così trasformato sarebbe così uguale ad un problema di ricerca del massimo in un insieme di numeri interi, dove ogni intero è il gradimento totale (sommatoria dei gradimenti delle singole pietanze) di una determinata lista di pietanze.

In base a quanto detto in precedenza, ogni elemento dell’insieme (un elemento è una lista finita di pietanze con costo totale che non supera K) è un certificato per il problema, e quindi rappresenta una soluzione ammissibile.

Quanto costa in termini di tempo creare lo spazio delle soluzioni? La risposta a questa domanda è il motivo per cui questa tecnica, chiamata ricerca esaustiva è utilizzata nella pratica solo per problemi molto particolari, di cui si parlerà in seguito, e cioè quando non è possibile utilizzare tutte le altre tecniche: la costruzione dello spazio delle soluzioni (di qui brevemente indicato con S) ha un costo strettamente legato al calcolo combinatorio, quindi si tratta di combinazioni, disposizioni, permutazioni, il più delle volte con ripetizione (come in questo caso); dobbiamo quindi aspettarci che il numero di elementi di S sia esponenziale nella dimensione del problema, quindi sarà proporzionale a C^N (dove N è il numero delle pietanze, nel nostro caso, e C>0 è una costante).

Queste considerazioni ci portano ovviamente ad escludere assolutamente tale tecnica, perché già con N=1000 e K=1000 (un numero relativamente piccolo), possiamo aspettarci i risultati dall’elaboratore fra qualche anno, o anche di più, il che renderebbe ovviamente inutile il nostro lavoro (oltre al fatto che probabilmente lo stack in memoria centrale non sarebbe abbastanza grande).

Sorge quindi la necessità di utilizzare tecniche più evolute, che permettano di muoversi, di 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 X[i..j], con 1<=i<=j<=N;

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 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 D[i][j] la soluzione 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 D[1][N], che 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 X[i..j] per renderla palindroma (quindi f(i,j) è la soluzione ottima del 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])

}

È 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 aspettarci dall’algoritmo sarà pari a 2^N nel caso peggiore), e il che significherebbe che stiamo utilizzando un metodo di ricerca esaustiva.

È per ovviare a questo inconveniente che si utilizza la 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 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 inferiore rispetto al tempo necessario per la ricerca esaustiva. (2^N).

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]