Algoritmi e Strutture Dati
Capitolo 10
Tecniche algoritmiche
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Sommario
• Una tecnica algoritmica può essere vista come
un meta-algoritmo che permette di risolvere
un’ampia classe di problemi, i quali, per loro
natura, si prestano ad essere risolti appunto in
modo analogo
• In particolare, abbiamo già visto
dettagliatamente la tecnica divide et impera
• Oggi vedremo la Programmazione Dinamica e
il Metodo Goloso, che troveranno ampia
applicazione nei problemi su grafi
2
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Richiamo: la tecnica divide et impera
Tecnica top-down:
1. Dividi l’istanza del problema in due o più
sottoistanze
2. Risolvi ricorsivamente il problema sulle
sottoistanze
3. Ricombina la soluzione dei sottoproblemi
allo scopo di ottenere la soluzione globale
Esempi: mergesort, quicksort
3
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Programmazione dinamica
•
Tecnica bottom-up:
1. Identifica dei sottoproblemi del problema originario,
procedendo logicamente dai problemi più piccoli
verso quelli più grandi
2. Utilizza una tabella per memorizzare le soluzioni dei
sottoproblemi incontrati: quando si incontra lo stesso
sottoproblema, sarà sufficiente esaminare la tabella
3. Si usa quando i sottoproblemi non sono indipendenti,
e lo stesso sottoproblema può apparire più volte
4
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Un esempio banale: Fibonacci3
algoritmo fibonacci3(intero n)  intero
sia Fib un array di n interi
Fib[1]  Fib[2]  1
for i = 3 to n do
Fib[i]  Fib[i-1] + Fib[i-2]
return Fib[n]
5
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Distanza tra stringhe
Siano X e Y due stringhe di lunghezza m ed n:
Vogliamo calcolare la distanza tra X e Y, ovvero il minimo
numero delle seguenti operazioni elementari da
eseguire su X che permetta di trasformare X in Y
6
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Esempio
• Parto dalla stringa X=“RISOTTO”, e voglio trasformarla in Y=“PRESTO”
• La soluzione banale consiste nel fare 7 cancellazioni e 6 inserimenti, cioè 13
operazioni
• Un’altra soluzione semplice: sostituisco uno dopo l’altro i caratteri di
RISOTTO, ove necessario, e cancello i caratteri in eccesso; nel nostro
esempio, saranno 5 sostituzione e 1 cancellazione (cioè, 6 operazioni).
• Posso fare meglio? Vediamo una sequenza di operazioni controintuitiva:
 Abbiamo fatto solo 4 operazioni! Posso fare meglio??
7
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Approccio
•
Denotiamo con d(X,Y) la distanza tra X e Y
•
Definiamo Xi il prefisso di X fino all’i-esimo
carattere, per 0≤ i ≤m (X0 denota la stringa vuota):
•
Risolveremo il problema di calcolare d(X,Y)
calcolando d(Xi,Yj) per ogni i, j tali che 0 ≤i ≤m e
0 ≤j ≤n
Manterremo le informazioni in una tabella D di
dimensione (m+1)  (n+1)
•
8
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Inizializzazione della tabella
•
Alcuni sottoproblemi sono molto semplici:
d(X0,Yj)=j per trasformare la stringa vuota
X0 nella stringa Yj, basta inserire uno ad uno
gli j caratteri di Yj
• d(Xi,Y0)=i per trasformare la stringa Xi nella
stringa vuota Y0, basta rimuovere uno ad uno
gli i caratteri di Xi
• Queste soluzioni sono memorizzate
rispettivamente nella prima riga e nella prima
colonna della tabella D
•
9
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Esempio
La tabella D
inizializzata
dall’algoritmo
10
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Avanzamento nella tabella (1/3)
•
Se xi=yj, il minimo costo per trasformare Xi in Yj è
uguale al minimo costo per trasformare Xi-1 in Yj-1
(infatti, non dovrò fare alcuna operazione su xi, visto
che esso coincide con yj)
D [ i,j] = D [ i-1, j-1 ]
•
Se xiyj, allora per trasformare Xi in Yj devo fare una
qualche operazione sull’i-esima posizione di Xi;
distinguiamo quindi in base all’ultima operazione che
dovremmo usare per trasformare Xi in Yj in una
sequenza ottima di operazioni
11
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Avanzamento nella tabella (2/3)
(in realtà questa operazione viene fatta
sulla posizione (i+1)-esima di Xi) il
minimo costo per trasformare Xi in Yj è
uguale al minimo costo per trasformare
Xi in Yj-1 più 1 per inserire il carattere yj
D [i,j] = 1 + D [i, j-1]
il minimo costo per trasformare Xi in Yj è
uguale al minimo costo per trasformare
Xi-1 in Yj più 1 per la cancellazione del
carattere xi
D [i,j] = 1 + D [i-1, j]
12
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Avanzamento nella tabella (3/3)
il minimo costo per trasformare
Xi in Yj è uguale al minimo costo
per trasformare Xi-1 in Yj-1 più 1
per sostituire il carattere xi con yj
D [i,j] = 1 + D [i-1, j-1]
In conclusione:
13
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Pseudocodice
Tempo di esecuzione ed occupazione di memoria: Θ(m n)
NOTA: Se tengo traccia della casella della tabella che utilizzo
per decidere il valore di D[i,j], ho un metodo costruttivo per
ricostruire la sequenza di operazioni di editing ottima.
14
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Esempio
La tabella D costruita
dall’algoritmo.
In grassetto è indicata la
sequenza di operazioni
che permette di ottenere
la distanza tra le stringhe
(verificate che coincide
con quella data prima!)
mantenimento
15
sostituzione
inserimento
cancellazione
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
La tecnica golosa (o greedy)
• La tecnica golosa (greedy) si applica principalmente
a problemi di ottimizzazione in cui, dato un certo
numero di elementi come input, bisogna scegliere un
sottoinsieme di essi che ottimizzi una funzione
obbiettivo rispettando un certo numero di vincoli.
• Richiede che l’algoritmo esegua il processo di
costruzione della soluzione in fasi successive, in cui
ad ogni fase viene aggiunto un elemento alla
soluzione.
16
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Tecnica golosa (2)
• Un algoritmo greedy ordina dapprima gli oggetti in
base ad un criterio di appetibilità (da cui il termine
goloso), e poi ripete le seguenti operazioni:
1. Ad ogni fase i, la soluzione viene accresciuta selezionando
l’ i-esima componente, la quale, tra tutte quelle
ammissibili, risulta la migliore in questo momento rispetto
al criterio di appetibilità
2. Una volta fatta la scelta per la i-esima componente, si
aggiornano (eventualmente) le appetibilità, e si passa a
considerare le scelte successive, senza più tornare sulla
decisione presa.
• Questa strategia euristica non garantisce sempre la
determinazione di una soluzione ottima
17
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Paradigma di tecnica golosa
18
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Un problema di sequenziamento
• Un server (e.g., una CPU, o un impiegato dell’ufficio
postale) deve servire n clienti, stabilendo un ordine sapendo
che il servizio richiesto dal cliente i richiede ti secondi
• Chiamiamo T(i) il tempo di attesa del cliente i (pari al suo
tempo di processamento sommato ai tempi di processamento
dei clienti che lo hanno preceduto) e sia
il tempo di attesa totale di tutti i clienti
• Vogliamo stabilire un ordine che minimizzi il tempo di
attesa medio:
 Devo minimizzare il
tempo di attesa totale!
19
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Esempio
Dei sei possibili ordinamenti, il migliore è evidenziato in
arancione
20
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Un algoritmo goloso ottimo
•
Il seguente algoritmo genera l’ordine di servizio in
maniera incrementale secondo una strategia greedy:
– Il primo cliente ad essere servito è quello con tempo di
processamento minimo.
– Al generico passo l’algoritmo serve la richiesta più corta tra
quelle rimanenti.
•
La sequenza generata è ottima: infatti, è facile osservare
che il tempo di attesa totale può essere riscritto come
segue:
T=n·t1+(n-1)·t2+…+1·tn
e quindi è minimo quando t1≤t2 ≤ … ≤ tn
Tempo di esecuzione: Θ(n log n) (ordinamento ottimo)
•
21
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Un algoritmo goloso non ottimo
• Gli algoritmi greedy non sempre funzionano!
• Esempio:
Input: lista di interi che rappresentano il valore di monete
disponibili e un intero che rappresenta un resto.
Output: una collezione di cardinalità minima di monete
la cui somma sia uguale al resto.
Appetibilità: Taglio della moneta
Ma supponendo di dover formare un resto di 9, avendo a
disposizione monete da 1, 4 e 6…
 l’algoritmo darebbe 6 + 1 + 1 + 1 mentre la soluzione
ottima è 4 + 4 + 1!
22
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Applicazioni future su grafi
– Programmazione dinamica: cammini minimi tra
tutte le coppie di nodi (algoritmo di Floyd e
Warshall)
– Tecnica greedy: minimo albero ricoprente
(algoritmi di Prim, Kruskal, Boruvka) e cammini
minimi a sorgente singola (algoritmo di Dijkstra)
23
Copyright © 2004 - The McGraw - Hill Companies, srl