Universita' di Ferrara
Facolta' di Scienze Matematiche, Fisiche e Naturali
Laurea Specialistica in Informatica
Algoritmi Avanzati
Strategie per la progettazione di algoritmi:
greedy method, union-find
• problema dello knapsack
• algoritmo di Kruskal per la determinazione del minimum cost
spanning tree di un grafo non orientato
• disjoint set union, e union-find di Tarjan
• algoritmo di Dijkstra per la risoluzione del problema "single
source shortest paths"
Copyright © 2006-2007 by Claudio Salati.
Lez. 10b
1
GREEDY METHOD
•
ABBIAMO UN PROBLEMA SU UN INSIEME DI n ELEMENTI
•
OGNI ELEMENTO E’ DOTATO DI UN INSIEME DI
PROPRIETA' CHE NE DEFINISCONO COSTO, QUANTITA',
UTILITA’, ...
•
LA SOLUZIONE DEL PROBLEMA RICHIEDE DI
IDENTIFICARE UN SOTTOINSIEME (o comunque una
strutturazione) DI QUESTO INSIEME CHE
•
SODDISFI CERTI VINCOLI
(LEGATI ALLE PROPRIETA' DEGLI ELEMENTI)
•
MASSIMIZZI (O MINIMIZZI) UNA CERTA FUNZIONE
OBBIETTIVO
(LEGATA ALLE PROPRIETA' DEGLI ELEMENTI)
2
GREEDY METHOD
IL METODO GREEDY (avido, avaro) SUGGERISCE DI
1. Ordinare gli elementi dell'insieme secodo una funzione
ottimizzante legata alle loro proprieta' e valutabile
indipendentemente per ciascun elemento.
2. Partire da una soluzione parziale data dall'insieme vuoto.
3. Scandire uno per uno gli elementi dell'insieme ordinato
(nel passo 1) decidendo per ciascuno di essi se inserirlo
nella soluzione o scartarlo, in base al fatto che la
soluzione parziale ottenuta aggiungendolo sia o no
legittima.
•
Perche' la soluzione cosi' ottenuta sia effettivamente ottima bisogna
che la funzione ottimizzante di ordinamento sia adeguata,
• adeguata rispetto al problema
• adeguata rispetto alle proprieta' degli elementi.
3
GREEDY METHOD
struct item {
string
nome;
struct
{ … } attributes; };
void greedy(int sizData, struct item data[],
struct item res[], int *sizRes) {
*sizRes = 0;
sort(data, sizData);
int i = 0;
while (i < sizData) {
if (feasible(res, sizRes, data[i])) {
res[*sizRes] = data[i];
*sizRes += 1;
}
i += 1;
}
}
4
GREEDY METHOD
•
feasible() DETERMINA SE (all'i-esima iterazione) LA
SOLUZIONE OTTENUTA AGGIUNGENDO data[i] ALLA
SOLUZIONE PARZIALE OTTENUTA FINO AD ALLORA
(cioe' res[0..sizRes-1]) E' ANCORA LEGITTIMA
5
GREEDY METHOD: esempio KNAPSACK
Problema Knapsack
•
SONO DATI n OGGETTI E UNO ZAINO
•
L'OGGETTO i HA
• PESO (“specifico”) w[i] (>0)
• UTILITA' (“specifica”) p[i] (>0)
•
LO ZAINO HA CAPACITA' m LIMITATA
•
OGNI OGGETTO i PUO' ESSERE PRESO IN QUANTITA' x[i]
CON 0  x  1
•
BISOGNA METTERE OGGETTI NELLO ZAINO IN MODO DA
MASSIMIZZARE L'UTILITA' DEL SUO CONTENUTO:
n-1

massimizzare
 p[i]*x[i]
i=0
•
n-1
con il vincolo
 w[i]*x[i]  m
i=0
OGNI SOLUZIONE PER ESSERE ACCETTABILE DEVE
SODDISFARE IL VINCOLO
6
GREEDY METHOD: esempio KNAPSACK
• E' OVVIO CHE LA SOLUZIONE OTTIMA RIEMPIE
COMPLETAMENTE LO ZAINO
n-1
(il problema esiste ovviamente solo quando
 w[i] > m)
i=0
• SI POSSONO CONSIDERARE DIVERSE FUNZIONI
OTTIMIZZANTI DI ORDINAMENTO DI data:
1. Ordinare gli elementi secondo l’utilita’ (decrescente)
2. Ordinare gli elementi secondo il peso (crescente)
3.
Ordinare gli elementi secondo il rapporto utile/peso (p/w)
(decrescente)
• E' FACILE VEDERE CHE NE' IL CRITERIO 1 NE' IL CRITERIO
2 PORTANO (SEMPRE) ALLA SOLUZIONE OTTIMA
• IL CRITERIO 3 INVECE RISOLVE SEMPRE IN MODO
OTTIMO IL PROBLEMA DEL KNAPSACK
7
GREEDY METHOD: esempio KNAPSACK
struct item {
int
nome;
float p;
float w;};
struct itemInSack {
int
nome;
float x;};
// nome >= 0
// 0 <= x <= 1
void greedyKnapack
(int n, struct item data[],
float capacity, // m
struct itemInSack result[])
{
int i;
// continua alla prossima pagina
8
GREEDY METHOD: esempio KNAPSACK
sort(n, data); // rapporto p/w non crescente
for (i=0; i<n; i+=1) {
result[i].nome = data[i].nome;
result[i].x = 0.0;
}
for (i=0; i<n && capacity>0.0; i+=1) {
if (capacity >= data[i].w) {
capacity -= data[i].w;
result[i].x = 1.0;
} else {
result[i].x = capacity / data[i].w;
capacity = 0.0;
}
}
}
9
GREEDY METHOD: esempio KNAPSACK
• L'algoritmo di per se stesso non cambia al cambiare della funzione
ottimizzante di ordinamento:
 cambia solo la procedura sort() che esegue l'ordinamento.
• Ovviamente cambia anche il risultato finale!
• Quale e' la complessita' di greedy?
•
Di per se stesso greedy e' lineare: O(n)
(almeno nell'ipotesi che il calcolo della nuova soluzione parziale
avvenga in tempo costante)
•
Ma comprende una procedura di ordinamento!
Se questa e' O(n*log(n)), greedy diventa anch'esso O(n*log(n))
•
In realta' a noi basterebbe meno dell'ordinamento: basterebbe
uno heap come in heapsort, pero' poi bisogna comunque
mantenerlo, il che ci riporta a O(n*log(n)).
10
GREEDY METHOD: esempio KNAPSACK
Teorema: la soluzione trovata con il criterio di ordinamento basato
sulla massimizzazione del rapporto p[i]/w[i] e' ottima
Dimostrazione:
•
Sia x = [x0, …, xn-1] la soluzione fornita da
greedyKnapsack().
•
Per come funziona l'algoritmo c'e' un valore j per il quale:
(k| 0k<j: x[k]=1.0)  (0.0 x[j]1.0)  (k| j<k n-1: x[k]=0.0)
•
Se x non e' ottima allora c'e' una soluzione ottima y migliore
n-1
di x, cioe' tale per cui
•
 p[i]*y[i]
i=0
n-1
>
 p[i]*x[i]
(in realta’ )
i=0
in ogni caso posso assumere che lo zaino debba essere
pieno:
n-1
 w[i]*x[i] = m
i=0
n-1

 w[i]*y[i] = m
i=0
11
GREEDY METHOD: esempio KNAPSACK
Dimostrazione (continua):
•
Consideriamo l'indice minimo k per cui e’ y[k]x[k]
•
Di necessita' sara' y[k]<x[k], infatti
• se k<j, allora x[k]=1 e y[k] deve essere minore (essendo
diverso)
• se k=j lo zaino e' gia' pieno per il valore x[k], e quindi y[k]
deve essere minore
• il caso k>j e' impossibile, perche' lo zaino e' gia' pieno con i
primi j+1 elementi, dato che k | 0kj : y[k]=x[k], e i primi
j+1 elementi di x riempiono lo zaino
•
Allora pensiamo di modificare y facendo diventare y[k]=x[k]: per
fare cio' diminuiremo in modo arbitrario i valori y[l] per l>k in
modo da rispettare il vincolo di non overflow pur continuando a
riempire lo zaino.
•
In questo modo otteniamo una nuova soluzione z che e' uguale
a x fino all'indice k (e uguale a y fino all'indice k-1).
12
GREEDY METHOD: esempio KNAPSACK
Dimostrazione (continua):
•
Per soddisfare il vincolo di riempimento dovra' essere:
n-1
w[k]*(z[k]-y[k]) =
•

w[i]*(y[i]-z[i])
i=k+1
Allora:
n-1
n-1
n-1

p[i]*z[i] =  p[i]*y[i] + p[k]*(z[k]-y[k]) -  p[i]*(y[i]-z[i])
i=0
i=0
i=k+1
=
n-1
 p[i]*y[i] + (p[k]/w[k])*(z[k]-y[k])*w[k] i=0
n-1

n-1
i=k+1
(p[i]/w[i])*(y[i]-z[i])*w[i] 
n-1
 p[i]*y[i] + (p[k]/w[k])* ((z[k]-y[k])*w[k] - 
i=0
n-1
w[i]*(y[i]-z[i])) =
i=k+1
 p[i]*y[i]
i=0
13
GREEDY METHOD: esempio KNAPSACK
Dimostrazione (continua):
•
La maggiorazione deriva dal fatto che, per il criterio ottimizzante
di ordinamento utilizzato, risulta:
 i | k<in-1 : p[k]/w[k]  p[i]/w[i]
•
In caso di non uguaglianza y non e' ottima, il che e' in
contraddizione rispetto all'ipotesi.
•
In caso di uguaglianza,
•
o z=x, e allora greedyKnapsack() ha dato la (una)
soluzione ottima;
•
o zx, e allora posso ripetere con z (che e' ottima quanto y)
il procedimento precedente, fino a costruire una soluzione
ottima e uguale a x.
(a differenza di y, z e' uguale a x anche per l'indice j)
•
pertanto x e' anche lei ottima.
QED
14
GREEDY METHOD:
esempio Minimum Cost Spanning Tree
•
Consideriamo un grafo G = (V, E) non diretto e connesso, dove ad
ogni lato e' associato un costo
•
Un suo spanning tree S = (V, T) e' un albero non diretto che
connette tutti i nodi del grafo, e che ha come lati dei lati del grafo
(cioe' T E)
•
N.B.: di quanti lati e’ composto T?
#V - 1
15
GREEDY METHOD:
esempio Minimum Cost Spanning Tree
•
 v1V,  v2V : ! percorso in T che li congiunge.
Dim: Tra due nodi di un albero non diretto un percorso c'e' per
forza (per definizione dalla radice dell'albero c'e' un percorso sia
per raggiungere v1 che per raggiungere v2). Ce ne e' uno solo,
altrimenti ci sarebbe un ciclo, e un albero non ha cicli. 
•
Come e’ fatto il percorso?
1. risalgo da v1 al primo antenato comune
2. scendo fino a v2
•
Se a T aggiungo un altro lato di E (cioe' un lato l  E-T) si ottiene
un grafo con uno e un solo ciclo.
Dim: dato che c'era gia' un percorso tra i due nodi agli estremi del
lato, aggiungendo questo lato si crea un ciclo.
Il ciclo e' unico perche' il percorso stesso era unico. 
16
Esempio Minimum Cost Spanning Tree:
strategia di soluzione greedy
•
V e’definito.
•
Costruisco T a partire da un insieme di lati vuoto, e aggiungendo
man mano un lato per volta.
•
Aggiungendo lati a T lo mantengo a costo minimo, dato il numero
corrente dei suoi lati.
•
N.B.: per come lo (ri-)costruisco, durante l’esecuzione della
procedura T non si presentera’ come un grafo connesso (un
albero) ma piuttosto come una foresta, che solo alla fine sara’
riunificata in un albero.
•
Quindi, i lati da aggiungere li ordino per costo crescente.
•
Constraint:
aggiungendo un lato a T, T deve rimanere una foresta, cioe’ non
devo creare dei cicli.
17
GREEDY METHOD:
esempio Minimum Cost Spanning Tree
•
Una spanning forest su G e' un insieme di alberi non diretti
{ (V1, T1), (V2, T2), …, (Vk, Tk) } in cui
•
•
V1  V2  ...,  Vk = V
•
ij  Vi  Vj = 
•
i | 1ik : Ti  E
consideriamo una foresta di almeno 2 alberi e sia
T = T1  T2  ...  Tk
•
sia e = (v, w) un lato di costo minimo in E-T tale che se vVm
allora wVm (per un qualche m1..k).
•
allora:
Teorema: c'e' uno spanning tree che include T  {e} che e' di
costo non maggiore di qualsiasi spanning tree che includa T
•
Dimostrazione: vedi prossima pagina.
18
GREEDY METHOD:
esempio Minimum Cost Spanning Tree
Dimostrazione: per assurdo.
•
Sia S' = (V, T') uno spanning tree tale che TT' ed eT'.
•
Supponiamo (per assurdo) che il costo di T' sia minore del costo di
tutti gli spanning tree che includono anche e.
•
Se aggiungo e a T' ottengo un ciclo: nel ciclo sono compresi sia
nodi di Vm che nodi non di Vm, e quindi un altro lato e' con un
estremo in Vm e uno non in Vm (N.B.: quindi e'T).
•
Per ipotesi e' costa non meno di e.
•
Consideriamo il grafo S = ( V, T' - { e' }  { e } ):
• questo grafo non ha cicli, perche' l'unico ciclo che aveva e'
stato interrotto dalla rimozione di e'
• tutti i suoi nodi sono connessi, dato che abbiamo creato un
percorso alternativo a e' passando per e
•
Percio' S e' uno spanning tree di costo minore o uguale ad S' e
contiene sia T che e. 
19
GREEDY METHOD:
esempio Minimum Cost Spanning Tree
set<edge> kruskal(set<node> V, set<edge> E) {
set<edge> T = ;
set<set<node>> VS = {{v} : vV};
// VS rappresenta la spanning forest
// ogni suo elemento e' un albero della
// foresta
edge heapOfEdges[?];
// questo non e' proprio legale in C ma lo
// abbiamo gia' fatto e spiegato in radixSort()
node v, w;
set<node> V1, V2;
buildPriorityList(E, heapOfEdges);
// uno heap come in heapsort, in cui la
// radice e' l'elemento minimo
20
GREEDY METHOD:
esempio Minimum Cost Spanning Tree
// set<edge> kruskal(...); continua
while (#VS > 1) {
(v, w) = extractRootFrom(heapOfEdges);
// estrae e ricostruisce anche lo heap
V1 = treeVS | vtree;
V2 = treeVS | wtree;
if (V1!=V2) { // cioe', if feasible()
T = T  {(v, w)};
VS = VS - {V1} - {V2}  {V1  V2};
}
}
return(T);
}
21
Minimum cost spanning tree - Esempio

Da E. Horowitz, S. Sahni: Fundamentals of Computer Algorithms
1
10
2
3
50
45
30
25
35
40
15
4
6
20
5
55
1-2 (10)
3-5 (35)
3-6 (15)
4-6 (20)
2-6 (25)
1-4 (30)
2-5 (40)
1-5 (45)
2-3 (50)
5-6 (55)
22
Minimum cost spanning tree - Esempio

1
Da E. Horowitz, S. Sahni: Fundamentals of Computer Algorithms
10
2
3
50
45
30
25
35
40
15
4
6
20
5
55
1-2 (10)
3-5 (35)
3-6 (15)
4-6 (20)
2-6 (25)
1-4 (30)
2-5 (40)
1-5 (45)
2-3 (50)
5-6 (55)
23
Minimum cost spanning tree - Esempio

1
Da E. Horowitz, S. Sahni: Fundamentals of Computer Algorithms
10
2
3
50
45
30
25
35
40
15
4
6
20
5
55
1-2 (10)
3-5 (35)
3-6 (15)
4-6 (20)
2-6 (25)
1-4 (30)
2-5 (40)
1-5 (45)
2-3 (50)
5-6 (55)
24
Minimum cost spanning tree - Esempio

1
Da E. Horowitz, S. Sahni: Fundamentals of Computer Algorithms
10
2
3
50
45
30
25
35
40
15
4
6
20
5
55
1-2 (10)
3-5 (35)
3-6 (15)
4-6 (20)
2-6 (25)
1-4 (30)
2-5 (40)
1-5 (45)
2-3 (50)
5-6 (55)
25
Minimum cost spanning tree - Esempio

1
Da E. Horowitz, S. Sahni: Fundamentals of Computer Algorithms
10
2
3
50
45
30
25
35
40
15
4
6
20
5
55
1-2 (10)
3-5 (35)
3-6 (15)
4-6 (20)
2-6 (25)
1-4 (30)
2-5 (40)
1-5 (45)
2-3 (50)
5-6 (55)
26
Minimum cost spanning tree - Esempio

1
Da E. Horowitz, S. Sahni: Fundamentals of Computer Algorithms
10
2
3
50
45
30
25
35
40
15
4
6
20
5
55
1-2 (10)
3-5 (35)
3-6 (15)
4-6 (20)
2-6 (25)
1-4 (30)
2-5 (40)
1-5 (45)
2-3 (50)
5-6 (55)
27
Minimum cost spanning tree - Esempio

1
Da E. Horowitz, S. Sahni: Fundamentals of Computer Algorithms
10
2
3
50
45
30
25
35
40
15
4
6
20
5
55
1-2 (10)
3-5 (35)
3-6 (15)
4-6 (20)
2-6 (25)
1-4 (30)
2-5 (40)
1-5 (45)
2-3 (50)
5-6 (55)
28
GREEDY METHOD:
esempio Minimum Cost Spanning Tree
•
La correttezza dell'algoritmo discende da quanto detto prima, e per
induzione matematica sul numero dei lati in T.
•
Per la complessita':
• Dipende da come espandiamo le strutture dati e gli statement del
Pidgin C
• buildPriorityList() puo' essere la costruzione di uno heap e
quindi essere O(#E)
• extractRootFrom() puo' essere l'estrazione della radice dello
heap, con ricostruzione dello heap stesso, e quindi avere complessita'
O(log(#E)), pero' e' eseguita fino a #E volte per cui il ciclo ha
complessita' almeno O(#E*log(#E)).
In realta' si spera di non dovere guardare tutti i lati del grafo prima di
finire la costruzione dello spanning tree, in modo da risparmiare
rispetto ad un ordinamento completo per costo di E
• Ma trovare i due set V1 e V2 quanto costa?
E quanto costa fare la loro unione?
E quanto costa sottrarre V1 e V2 da VS?
• Con lo union-find di Tarjan queste tre operazioni sono O(log(#V)) con
#V#E+1, per cui tutto l'algoritmo risulta O(#E*log(#E))
29
GREEDY METHOD:
esempio Minimum Cost Spanning Tree
•
L'algoritmo di Kruskal non e' stato completamente specificato, e
nemmeno le strutture dati che esso utilizza
•
abbiamo proceduto per raffinamenti successivi: possiamo
anche costruirne diverse versioni nelle quali si cambia
l'implementazione di singole parti:
•
•
si puo' utilizzare uno heap o un vettore completamente
ordinato
•
si puo' utilizzare un algoritmo elementare per il disjoint
union-find
e' possibile realizzare un fast-prototyping utilizzando procedure
gia' a disposizione ma non ottimizzate
e nel frattempo sviluppare gli algoritmi ottimizzati per la
versione finale
30
UNION-FIND (R.E. Tarjan)
•
Ipotesi: LA SPANNING FOREST RAPPRESENTA UN
PARTIZIONAMENTO DELL'INSIEME DEI NODI DEL GRAFO.
PERTANTO:
• UN NODO APPARTIENE AD UNO ED UN SOLO INSIEME
• L'UNIONE DI DUE INSIEMI E' L'UNIONE DI INSIEMI
DISGIUNTI
•
L'UNIONE DI INSIEMI SI POTREBBE FARE IN MODO
EFFICIENTE RAPPRESENTANDO OGNI INSIEME CON UNA
SEMPLICE LISTA, PERO'
• COME SI FA A TROVARE IN MODO EFFICIENTE A QUALE
INSIEME APPARTIENE UN NODO?
• CIOE' A QUALE ALBERO DELLA SPANNING FOREST E'
ATTACCATO? (e.g. per poter calcolare if (V1==V2))
• SE SI AGGIUNGE AD OGNI NODO UN RIFERIMENTO
ALL'INSIEME (ALLA LISTA) CUI APPARTIENE BISOGNA
POI TENERLO AGGIORNATO, PER CUI NON E' PIU'
31
POSSIBILE REALIZZARE L'UNIONE IN TEMPO COSTANTE!
UNION-FIND (R.E. Tarjan)
•
ALL'INIZIO COME SI E' GIA' VISTO OGNI NODO E' UN ALBERO
PER PROPRIO CONTO.
•
POICHE' OGNI NODO APPARTIENE AD UNO E UN SOLO
INSIEME CIASCUN INSIEME PUO' ESSERE INDIVIDUATO DA
UNO QUALUNQUE DEI NODI CHE GLI APPARTENGONO.
 AD ESEMPIO DAL NODO RADICE DELL'ALBERO
•
TUTTI GLI ALTRI NODI DELL'INSIEME DOVRANNO RIFERIRE,
DIRETTAMENTE O INDIRETTAMENTE, IL NODO
RAPPRESENTANTE DELL'INSIEME STESSO.
•
OGNI INSIEME E' COSI' RAPPRESENTATO DA UN
ALBERO, NON BINARIO E NON ORDINATO, LA CUI RADICE E'
IL NODO RAPPRESENTANTE DELL'INSIEME, E IN CUI OGNI
NODO RIFERISCE IL NODO PADRE.
•
N.B.: quest'albero non c'entra niente con lo spanning tree
dell'insieme
32
UNION-FIND
•
PER FARE L'UNIONE DI 2 INSIEMI, CANCELLANDO AL TEMPO
STESSO I DUE INSIEMI ADDENDI, BASTA FARE SI' CHE LA
RADICE DI UNO DEI DUE DIVENTI FIGLIA DELLA RADICE
DELL'ALTRO
•
IL TEMPO PER L'OPERAZIONE union E' COSTANTE,
COME PERALTRO SI SAREBBE AVUTO NEL CASO DI
RAPPRESENTAZIONE CON SEMPLICE LISTA
 warning: E IN EFFETTI LA RAPPRESENTAZIONE AD
ALBERO PUO' ESSA STESSA DEGENERARE IN UNA
RAPPRESENTAZIONE A LISTA SE UNO DEI DUE INSIEMI
DA SOMMARE E' SEMPRE DI CARDINALITA' 1 ED E'
QUESTO CHE DIVENTA RADICE DELL'ALBERO UNIONE
•
LA OPERAZIONE find HA COMPLESSITA' DELL'ORDINE
DELL'ALTEZZA DELL'ALBERO CHE RAPPRESENTA
L'INSIEME
33
UNION-FIND
• IL PROBLEMA E' DI MANTENERE L'ALTEZZA DELL'ALBERO
AL PIU' LOGARITMICA NEL NUMERO DEI NODI IN ESSO
CONTENUTI
• PER OTTENERE CIO' FACCIAMO DUE COSE:
•
DIAMO AD OGNI ALBERO UN PESO, PARI AL NUMERO
DI NODI IN ESSO CONTENUTI
•
NEL FARE L'UNIONE DI 2 INSIEMI FACCIAMO SI' CHE
SIA L'ALBERO DI PESO MINORE A DIVENTARE UN
SOTTOALBERO DELLA RADICE DELL'ALBERO DI
PESO MAGGIORE
• NOTA CHE CIO' RENDE AD ESEMPIO IMPOSSIBILE IL
FORMARSI DI UN ALBERO CHE DEGENERI IN UNA LISTA
34
UNION-FIND
struct node { char
*ident;
struct node *parent;
int
weight;};
// ogni node e' inizializzato con
//
parent = NULL;
//
weight = 1;
// per indicare che e' la radice di un albero
// che contiene un solo nodo
typedef struct node *refNode;
refNode find (refNode nodo) {
while (nodo->parent!=NULL)
nodo = nodo->parent;
return (nodo);
}
35
UNION-FIND
refNode union (refNode node1, refNode node2) {
// node1 e node2 sono i nodi rappresentanti
// del proprio set
if (node2->weight > node1->weight) {
node1->parent = node2;
node2->weight += node1->weight;
return node2;
} else {
node2->parent = node1;
node1->weight += node2->weight;
return node1;
}
}
36
UNION-FIND
• L'OPERAZIONE DI union HA SEMPRE COSTO COSTANTE
• L'OPERAZIONE DI find ADESSO HA COSTO O(log(n)) DOVE
n E' IL NUMERO DI NODI DELL'ALBERO.
• INFATTI LA COMPLESSITA' DI find E' PROPORZIONALE
ALL'ALTEZZA DELL'ALBERO CHE RAPPRESENTA
L'INSIEME, E
• Teorema: UN ALBERO DI n ELEMENTI COSTRUITO
TRAMITE UNA SEQUENZA DI OPERAZIONI union HA
ALTEZZA  log(n)
Dimostrazione: vedi pagina seguente
37
UNION-FIND
Dimostrazione: per induzione matematica
• BASE: OVVIO PER n=1 PERCHE' log(n)=0
• STEP INDUTTIVO:
• si assume vero per alberi di dimensione <n (e si prova per
alberi di dimensione n)
• si considera l'ultima union
• W.L.G. (without loss of generality) si assume: #node1  n/2
(infatti: #node1  #node2, e #node1 + #node2 = n)
node1 DIVENTA FIGLIO DI node2: LA PROFONDITA' DEI NODI
PRECEDENTEMENTE IN node2 NON CAMBIA E QUINDI PER
INDUZIONE IL LORO CONTRIBUTO ALL'ALTEZZA
COMPLESSIVA RIENTRA NEI LIMITI.
LA PROFONDITA' DEI NODI DI node1 AUMENTA DI 1, MA PER
HP INDUTTIVA E'  log(n/2)+1 = log(n), PER CUI ANCHE IL LORO
CONTRIBUTO ALL'ALTEZZA RIENTRA NEI LIMITI. 
38
UNION-FIND
• DURANTE L'OPERAZIONE DI find SI POTREBBE COLLASSARE
L'ALBERO RENDENDO TUTTI I NODI ATTRAVERSATI FIGLI
DIRETTI DEL NODO RADICE
• IN QUESTO MODO, ASINTOTICAMENTE OGNI ALBERO-INSIEME
VIENE AD AVERE ALTEZZA 1 ED ANCHE L'OPERAZIONE find
DIVENTA DI COMPLESSITA' COSTANTE
• COSTA DI PIU' LA SINGOLA find, MA SI RISPARMIA SU QUELLE
SUCCESSIVE
• Esercizio:
Scrivere una versione dell'algoritmo di find che operi il collassamento
verso la radice dei nodi attraversati.
Notare che il campo weight e' significativo solo per il nodo radice, e
che non sarebbe quindi necessario aggiornarlo: nell'esercizio e'
comunque richiesto di aggiornare anche questo campo per tutti i nodi
per i quali il valore cambia a causa del collassamento.
39
GREEDY METHOD:
esempio Minimum Cost Spanning Tree
•
Quanto tempo occorre per valutare #VS, cioe’ il numero di insiemi
che compongono la partizione?
(Cioe' il numero degli alberi della spanning forest)
•
•
Basta (N.B.: un altro esempio di differenziazione formale!):
•
aggiungere una variabile countVS inizializzata al numero dei
nodi del grafo,
•
sostituire #VS>1 con countVS>1 e
•
Ad ogni esecuzione del corpo dello statement if,
decrementare di 1 countVS
Quanto costa l’ultima istruzione dell’if?
Cioe': VS = VS - {V1} - {V2}  {V1  V2};
•
N.B.: si e’ detto che costruire V1+V2 porta contestualmente
alla scomparsa di V1 e V2
40
GREEDY METHOD
• GREEDY METHOD SI APPLICA:
1. QUANDO UN PROBLEMA PUO' ESSERE VISTO COME UNA
SEQUENZA DI DECISIONI
2. QUANDO LA SEQUENZA GLOBALMENTE OTTIMA DI
DECISIONI PUO' ESSERE OTTENUTA ATTRAVERSO
SINGOLE DECISIONI, OTTIME LOCALMENTE, SENZA
SBAGLIARSI MAI
• SE VIENE A MANCARE LA SECONDA IPOTESI ALLORA BISOGNA
IN QUALCHE MANIERA ENUMERARE TUTTE LE SEQUENZE DI
DECISIONI POSSIBILI PER TROVARE QUELLA GLOBALMENTE
OTTIMA:
•
CIO' COMPORTEREBBE UN TEMPO ESPONENZIALE,
RENDENDO INTRATTABILE IL PROBLEMA.
•
ESISTONO DIVERSE TECNICHE PER LIMITARE A
COMPLESSITA' POLINIMIALI L'ESAME DELLE SOLUZIONI
POSSIBILI, PUR GARANTENDO CHE LA SOLUZIONE
41
TROVATA SIA OTTIMA (e.g. programmazione dinamica).
GREEDY METHOD
•
SE GREEDY METHOD NON E' APPLICABILE, OCCORRE
COMUNQUE RIUSCIRE A LIMITARE LA COMPLESSITA'
DELL'ANALISI DI TUTTE LE SOLUZIONI POSSIBILI:
•
CIO' OVVIAMENTE SIGNIFICA CHE NON TUTTE LE
POSSIBILI SOLUZIONI VENGONO GENERATE E CHE
QUINDI ESISTE UN CRITERIO CHE PERMETTE DI
SCARTARNE A PRIORI ALCUNE
•
AD ES. PERCHE' SI VEDE GIA' CHE UNA SEQUENZA
PARZIALE DI DECISIONI NON PUO' PORTARE AD UNA
SOLUZIONE GLOBALMENTE OTTIMA
42
GREEDY METHOD: esercizio
 Thanks to D. Boneh, CS161, Stanford U., Fall 2001
•
Tasks defined by (duration, deadline), e.g. homeworks.
•
Goal: find a schedule, if one exists
•
Esercizio: individuare la funzione ottimizzante e scrivere una
funzione C che implementa l'algoritmo greedy per risolvere
questo problema
•
Suggerimento (di D. Boneh):
•
assume that there exists a schedule
•
claim: then there exists a schedule with first job = job with
smallest deadline
•
(exchange in schedule first job and job with smallest
deadline)
43
GREEDY METHOD: single source - shortest paths
•
Un grafo puo' essere utilizzato per rappresentare:
• la rete stradale che collega le citta' di uno stato, con i vertici
che rappresentano le citta' e i lati che rappresentano tratti di
strade
• una (inter-)rete di calcolatori, con i vertici che rappresentano
i calcolatori e i lati che rappresentano le sottoreti
(schematizzabili comunque come punto-punto) che li
connettono
•
A ogni lato puo' essere associato un costo
• e.g. inversamente proporzionale alla banda della sottorete.
• si assume che il costo di un lato sia sempre positivo.
•
Il grafo si assume essere orientato
• per poter modellare strade a senso unico, o comunque le
due carreggiate di una autostrada.
• per potere modellare sottoreti uni-direzionali o con le due
direzioni realizzate tramite livelli fisici separati/eterogenei.
44
GREEDY METHOD: single source - shortest paths
•
Problemi che ci si puo' porre:
•
C'e' un percorso (path) dal nodo A al nodo B?
•
Se dal nodo A al nodo B ci sono piu' percorsi, quale e'
quello piu' corto, cioe' quello di costo minimo?
•
Il costo di un path e' definito come la somma dei costi di tutti i
lati che lo compongono.
•
Il nodo di partenza di un path sara' indicato come la sua
sorgente (source).
•
Il nodo di arrivo di un path sara' indicato come la sua
destinazione.
•
Problema: sono dati un grafo diretto G=(V, E) e una funzione
peso costo(e) per i lati di G.
Dato un vertice v0V, determinare i path minimi (shortest
paths) da v0 a tutti gli altri vertici di G.
45
GREEDY METHOD: single source - shortest paths
 Da E. Horowitz, S. Sahni: Fundamentals of Computer Algorithms
• In order to formulate a greedy based algorithm to generate the
shortest paths, we must conceive of a multistage solution to the
problem and also conceive of an optimization measure.
• One possibility is to build the shortest paths one by one.
• As an optimization measure we can use the sum of the lengths
of all paths so far generated.
• In order for this measure to be minimized, each individual path
must be of minimal length.
• Using this optimization measure, if we have already constructed i
shortest paths then the next path to be constructed should be the
next shortest minimum length path.
46
GREEDY METHOD: single source - shortest paths
 Da E. Horowitz, S. Sahni: Fundamentals of Computer Algorithms
• The greedy way to generate the shortest paths from v0 to the
remaining vertices would be to generate these paths in
nondecreasing order of path length.
•
First, a shortest path to the nearest vertex is generated.
•
Then a shortest path to the second nearest vertex is
generated and so on.
• In order to generate the shortest paths in this order, we need to
be able to determine:
1. the next vertex to which a shortest path must be generated
and
2. a shortest path to this vertex.
47
Single source - shortest paths - Esempio

Da E. Horowitz, S. Sahni: Fundamentals of Computer Algorithms
45
v0
v1
50
10
10
20
v4
20
35
30
15
v2
v3
15






path 0: v0,
path 1: v0-v2,
path 2: v0-v2-v3,
path 3: v0-v2-v3-v1,
path 4: v0-v4,
path 5: v0-v5,
v5
3
costo = 0
costo =10
costo = 10+15 = 25
costo = 10+15+20 = 45
costo = 45
costo = 
48
GREEDY METHOD: single source - shortest paths
 Da E. Horowitz, S. Sahni: Fundamentals of Computer Algorithms
• Let S denote the set of vertices (including v0) to which the shortest
paths have already been generated.
• For wS, let dist(w) be the length of the shortest path starting from
v0 going through only those vertices which are in S and ending at w.
• Allora (vedi seguito):
• dist(w) e’ il path minimo in assoluto da v0 a w
• w e’ il prossimo nodo del grafo per il quale abbiamo individuato il
path minimo da v0
• Il seguente algoritmo (algoritmo di Dijkstra) in effetti determina solo le
lunghezze degli shortest paths da v0 a tutti gli altri vertici di G.
• La effettiva generazione dei path richiede una semplice estensione che
e' lasciata per esercizio (vedi esercizi).
49
GREEDY METHOD: single source - shortest paths
void shortestPaths(set<node> V, set<edge> E,
node v0, double costo[edge],
/*out*/ double dist[node]) {
// costo[(v, w)]== se (v, w)E
set<node> S = {v0};
dist[v0] = 0;
for (v(V-{v0})) { dist[v] = costo[(v0, v)]; }
while (S!=V) {
w = (n(V-S) | m(V-S) dist[n]<=dist[m]);
S = S  {w};
for (v(V-S)) {
dist[v] = min(dist[v],
dist[w] + costo[(w, v)]);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
50
Algoritmo di Dijkstra: correttezza
.1
• Per induzione.
• La base e' ovvia:
– Il primo percorso individuato (da v0 a se stesso) e' quello
minimo in assoluto,
quindi e' per forza parte della soluzione ottima che e' composta
dai percorsi minimi che raggiungono tutti i nodi.
– La distanza minima da v0 ai nodi in V-S, considerando tutti e
soli i percorsi che attraversano solo nodi di S, e’ il costo del lato
da v0 a ciascuno dei nodi vS
(i percorsi da considerare sono costituiti di un unico lato, da v0
a vS).
• Continua 
51
Algoritmo di Dijkstra: correttezza
.2
• Supponiamo di avere gia' individuato una soluzione parziale S.
• Se il prossimo path minimo e' verso il vertice w, esso, partendo da
v0, attraversa solo nodi che appartengono a S.
Infatti, se nel path ci fosse un vertice intermedio uS, il path da v0 a
u sarebbe piu' corto di quello da v0 a w
(tutti i lati hanno costo >0).
• Quindi, il prossimo vertice w da selezionare e' quello per cui
dist[v] e' minimo tra i vertici vS, con dist[v] che e' calcolato
considerando solo path i cui nodi intermedi appartengono ad S.
• Continua 
52
Algoritmo di Dijkstra: correttezza
.3
• L'introduzione di w in S puo' alterare il valore di dist[], che viene
ricalcolato correttamente nell'ultimo ciclo for per tenere conto di
questo fatto. Infatti:
• supponendo che dist[] sia corretto all'inizio del ciclo while, se
dist[u] cambia per l'introduzione del vertice w in S, esso deve
cambiare a causa di un nuovo path da v0 a u comprendente il
nodo w (e con tutti i vertici intermedi appartenenti ad S).
• questo nuovo path deve essere di costo minimo (minore di
quello individuato precedentemente), e quindi deve essere di
costo minimo per la sua parte v0w, che quindi deve coincidere
con il path minimo appena individuato da v0 a w.
• tra w e u non ci puo' essere alcun nodo intermedio vS, perche'
il costo del path minimo gia' individuato da v0 a v sarebbe'
minore di quello di qualsiasi path da v0 passante per w (il path
v0w e' stato individuato dopo).
• Continua 
53
Algoritmo di Dijkstra: correttezza
.4
• Pertanto l'eventuale nuovo path minimo da v0 a u passante per w
dovra' essere costituito
• dal path minimo da v0 a w appena individuato
• seguito dal lato (w, u).
54
Algoritmo di Dijkstra: complessita'
.1
Per come e' scritto l'algoritmo e' difficilmente analizzabile, e
comunque sembra essere pieno di ridondanze:
• quanto costa confrontare due insiemi per vedere se sono
uguali?
• e' davvero necessario calcolare ad ogni iterazione la differenza
di insiemi V-S?
• non sarebbe conveniente tenere memorizzata piuttosto questa
differenza (e.g. in V, e magari chiedersi come condizione di
controllo del ciclo while se V=)?
• per quanto detto e' ovviamente necessario potere estrarre il
vertice w da V in tempo costante, una volta noto w.
• come si puo' realizzare la funzione costo[]?
• Continua 
55
Algoritmo di Dijkstra: complessita'
.2
• Nell'ultimo ciclo for, in realta', mi basterebbe scandire solo i lati
uscenti da w.
 Se non esiste un lato (w, u) un percorso da v0 a u passante
per w e avente ultimo lato uguale a (w, u) avrebbe
comunque costo .
• Alla peggio questo mi portera' a calcolare inutilmente (perche' di
costo sicuramente maggiore di quello gia' individuato) un nuovo
path per i vertici gia' inseriti in S che sono teste di lati uscenti da
w.
• In effetti anche il ciclo for di riga 6 puo' essere visto come una
scansione di tutti i lati uscenti da v0, una volta che dist[v] sia
prima stato inizializzato a  per ogni vertice v.
56
Algoritmo di Dijkstra: raffinamento
• Per potere calcolare la complessita' dell'algoritmo, lo
riscriveremo precisando le strutture dati su cui si appoggia.
• Il grafo puo' essere descritto come una lista di nodi doppiamente
linkata.
 Per consentire l'eliminazione di un nodo di cui sia nota
l'identita'.
• La lista dei nodi, per comodita', sara' circolare e con nodo di
testa dummy.
• Ogni nodo ospitera' un campo per mantenere l'informazione del
costo del path minimo per raggiungerlo da v0 che e' stato
individuato fino a quel momento (implementazione di dist[]).
• A ogni nodo sara' associata la lista dei lati uscenti dal nodo: e'
sufficiente una lista non circolare semplicemente linkata.
• Ogni lato riferira' il suo nodo di testa e manterra' l'informazione
del proprio costo (implementazione di costo[]).
57
Single source - shortest paths .1
struct node {
char
*nome;
struct node *lLink;
struct node *rLink;
struct edge *fromOf;
double
// lista dei lati uscenti
dist;
};
struct edge {
struct edge *next;
// lista dei lati
struct node *to;
// nodo di testa del lato
double costo;
};
typedef struct node *graph;
58
Single source - shortest paths .2
graph shortestPaths(graph g, struct node *v0) {
// S = {}
graph S = malloc(sizeof(struct node));
S->lLink = S->rLink = S;
S->nome = NULL; S->fromOf = NULL; S->dist = ;
delink(v0);
// V = V – {v0}
link(v0, S);
// S = S + {v0}
v0->dist = 0.0;
// forall n in V dist[n] = 
struct node *nScan = g->lLink;
while (nScan != g) {
nScan->dist = ; nScan = nScan-> lLink;
}
// forall n in V dist[n] = costo[(v0, n)]
struct edge *eScan = v0->fromOf;
while (eScan != NULL) {
eScan->to->dist = eScan->costo;
eScan = eScan->next;
}
59
Single source - shortest paths .3
while (g->lLink != g /*V!={}*/) {
w = g->lLink;
nScan = w->lLink;
while (nScan != g) {
if (nScan->dist < w->dist) w = nScan;
nScan = nScan->lLink;
}
delink(w);
link(w, S);
// V = V – {w}
//S = S + {w}
eScan = w->fromOf;
while (escan != NULL) {
if (eScan->to->dist > w->dist+eScan->costo)
eScan->to->dist = w->dist+eScan->costo;
// end if
eScan = eScan->next;
}
}
60
Single source - shortest paths .4
free(g);
return(S);
}
• Quale e' la complessita' dell'algoritmo?
• Il suo calcolo e' lasciato per esercizio (vedi esercizi).
• N.B.: il fatto che la distanza minima da v0 al vertice v risulti 
indica che non esiste alcun percorso da v0 a v
• Come dovremmo modificare l’algoritmo per ottenere il percorso
minimo da v0 ad un particolare nodo del grafo?
61
Single source - shortest paths - Esempio
45
v0
v1
50
10
10
20
v4
20
35
30
15
v2
v3
15
v5
3
g = { v1, v2, v3, v4, v5 }
S = { v0 }
dist
v00
v150
v210
v3
v445
v5
via
v0v0
v1v0
v2v0
v3v0
v4v0
v5v0
62
Single source - shortest paths - Esempio
45
v0
v1
50
10
10
20
20
v4
35
30
15
v2
v3
15
v5
3
g = { v1, v3, v4, v5 }
S = { v0, v2 }
dist
v00
v150
v210
v325
v445
v5
via
v0v0
v1v0
v2v0
v3v2
v4v0
v5v0
63
Single source - shortest paths - Esempio
45
v0
v1
50
10
10
20
v4
20
35
30
15
v2
v3
15
v5
3
g = { v1, v4, v5 }
S = { v0, v2, v3 }
dist
v00
v145
v210
v325
v445
v5
via
v0v0
v1v3
v2v0
v3v2
v4v0
v5v0
64
Single source - shortest paths - Esempio
45
v0
v1
50
10
10
20
20
v4
35
30
15
v2
v3
15
v5
3
g = { v4, v5 }
S = { v0, v2, v3, v1 }
dist
v00
v145
v210
v325
v445
v5
via
v0v0
v1v3
v2v0
v3v2
v4v0
v5v0
65
Single source - shortest paths - Esempio
45
v0
v1
50
10
10
20
v4
20
35
30
15
v2
v3
15
v5
3
g = { v5 }
S = { v0, v2, v3, v1, v4 }
dist
v00
v145
v210
v325
v445
v5
via
v0v0
v1v3
v2v0
v3v2
v4v0
v5v0
66
Single source - shortest paths - Esempio
45
v0
v1
50
10
10
20
v4
20
35
30
15
v2
v3
15
v5
3
g={}
S = { v0, v2, v3, v1, v4, v5 }
dist
v00
v145
v210
v325
v445
v5
via
v0v0
v1v3
v2v0
v3v2
v4v0
v5v0
67
Algoritmo di Dijkstra: considerazioni
• I path minimi da v0 a tutti i nodi del grafo sono individuati in ordine
di costo crescente.
• Supponiamo che ci interessi solo la distanza minima da v0 di un
particolare nodo v del grafo:
se questo e’ il nodo per il quale la distanza minima e’ massima,
prima di calcolare la sua distanza minima dovremo avere calcolato
quella di tutti gli altri nodi del grafo.
 Pertanto, la complessita’ di individuare il percorso minimo da v0
ad un nodo del grafo e’ identica a quella di individuare i percorsi
minimi da v0 a tutti i nodi del grafo.
68
Algoritmo di Dijkstra: considerazioni
• Scopo dell’algoritmo (della strategia greedy):
– Limitare il numero dei percorsi per i quali devo effettivamente
valutare il costo.
• Come avviene questa limitazione?
– Dimostrando che gli unici percorsi che devo considerare sono
quelli che hanno una ben precisa struttura: gli altri sono
irrilevanti.
• Consideriamo ad esempio un grafo completamente connesso con n
nodi:
– Quanti sarebbero i diversi path da un nodo ad un altro? (n-2)!
– Quanti sono i path per i quali viene effettivamente valutato il
costo secondo l’algoritmo di Dijkstra? n
69