Algoritmi e Strutture Dati
Capitolo 14 - Greedy
Alberto Montresor
Università di Trento
This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License. To view a
copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/2.5/ or send a letter to Creative
Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.
© Alberto Montresor
1
Introduzione
Gli algoritmi per problemi di ottimizzazione
✦
Eseguono una sequenza di decisioni
✦
La programmazione dinamica
✦
In maniera bottom-up, valuta tutte le decisioni possibili
✦
Evitando però di ripetere sotto-problemi (decisioni) già percorse
✦
Un algoritmo greedy (ingordo, goloso)
✦
Seleziona una sola delle possibili decisioni...
✦
... quella che sembra ottima (ovvero, è localmente ottima)
✦
Sperabilmente, si ottiene così un ottimo globale
✦
© Alberto Montresor
2
Introduzione
Quando applicare la tecnica greedy?
✦
Quando è possibile dimostrare che esiste una scelta ingorda
✦
“Fra le molte scelte possibili, ne può essere facilmente individuata una che
porta sicuramente alla soluzione ottima”
✦
Quando il problema ha sottostruttura ottima
✦
“Fatta tale scelta, resta un sottoproblema con la stessa
struttura del problema principale”
✦
Non tutti i problemi hanno una scelta ingorda
✦
Nota:
✦
in alcuni casi, soluzioni non ottime possono essere comunque interessanti
✦
© Alberto Montresor
3
Insieme indipendente di intervalli
Problema:
✦
Siano dati n intervalli distinti [ai, bi[ della retta reale
✦
✦
trovare un insieme indipendente massimo
un sottoinsieme di massima cardinalità formato da
intervalli tutti disgiunti tra loro
✦
Definizioni:
✦
i
ai bi
1 1 4
2 3 5
3 0 6
4 5 7
5 3 8
S={ 1, 2,…, n } un insieme di intervalli
6 5 9
Ad ogni intervallo i in S sono associati:
7 6 10
✦
✦
ai → tempo di inizio
8 8 11
bi → tempo di fine
9 8 12
✦
✦
Che relazione c’è con “Insieme indipendente di intervalli pesati”?
✦
© Alberto Montresor
10 12 14
4
Attività
1
2
3
4
5
6
7
8
9
10
11
Tempo
0
© Alberto Montresor
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
5
Attività
1
2
3
4
5
6
7
8
9
10
11
Tempo
0
© Alberto Montresor
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
6
Come affrontare il problema


Cerchiamo innanzitutto di risolverlo tramite
programmazione dinamica (PD):

Individuiamo una sottostruttura ottima

Scriviamo una definizione ricorsiva per la dimensione della soluzione ottima

Scriviamo una versione iterativa bottom-up dell'algoritmo
Passiamo poi alla tecnica greedy

Cerchiamo una possibile scelta ingorda

Dimostriamo che la scelta ingorda porta alla soluzione ottima

Scriviamo un algoritmo ricorsivo o iterativo che effettua sempre
la scelta ingorda
© Alberto Montresor
7
Sottostruttura ottima
Si assuma che le attività siano ordinate per tempo di fine:
✦
b1 ≤ b2 ≤ … ≤ bn
✦
Sottoproblema S[i,j]
✦
S[i,j] = { k | bi ≤ ak < bk ≤ aj }
✦
Il sottoinsieme di attività che
✦
iniziano dopo che i ha finito
✦
finiscono prima che j abbia iniziato
✦
Aggiungiamo due attività
“fittizie”:
✦
0 → b0 = 0
bi ak
bk aj
✦n+1
→ an+1 = +∞
✦
Così S[0, n+1] corrisponde al problema completo S
✦
© Alberto Montresor
8
Sottostruttura ottima: caratterizzazione
Se A[i,j] è una soluzione ottimale di S[i,j], e l'attività k è inclusa in A[i,j], allora
✦
✦
Il problema S[i,j] viene suddiviso in due sottoproblemi:
S[i,k]: le attività di S[i,j] che finiscono prima di k
✦
S[k,j]: le attività di S[i,j] che iniziano dopo di k
✦
✦
A[i,j] contiene le soluzioni ottimali di S[i,k] e S[k,j]
A[i,j] ∩ S[i,k] è la soluzione ottimale di S[i,k]
✦
A[i,j] ∩ S[k,j] è la soluzione ottimale di S[k,j]
✦
Dimostrazione:
✦
Utilizzando il metodo cut-and-paste
✦
© Alberto Montresor
9
Definizione ricorsiva
Descrizione ricorsiva della soluzione:
✦
A[i,j] = A[i,k] ∪ { k } ∪ A[k, j]
✦
Come determinare k ? Analizzando tutte le possibilità...
✦
Definizione: D[i, j]
✦
La dimensione del più grande sottoinsieme A[i,j] ⊆ S[i,j]
di attività mutualmente compatibili
✦
Come si calcola?
✦
© Alberto Montresor
10
Verso una soluzione “greedy”
La definizione precedente:
✦
Ci permette di scrivere un algoritmo basato su programmazione dinamica o su
memoization
✦
Complessità: θ(n3)
✦
Devo risolvere tutti i sottoproblemi con i ≠ j, nel caso peggiore tempo O(n)
per un sottoproblema
✦
Posso fare di meglio?
✦
Avevamo visto una soluzione O(n log n)
✦
Richiedeva pre-elaborazione
✦
Questa soluzione è peggiore, ma...
✦
Siamo sicuri che sia necessario analizzare tutti i possibili valori per k?
✦
© Alberto Montresor
11
Teorema: “Greedy choice”
Sia S[i,j] un sottoproblema non vuoto, e m l'attività di S[i,j] con il minor tempo di
fine; allora
✦
m è compresa in qualche soluzione ottima di S[i,j]
✦
Il sottoproblema S[i,m] è vuoto
✦
Dimostrazione
✦
Conseguenze:
✦
Non è più necessario analizzare tutti i possibili valori di k
✦
Faccio una scelta “ingorda”, ma sicura:
seleziono l'attività m con il minor tempo di fine
✦
Non è più necessario analizzare due sottoproblemi:
✦
Elimino tutte le attività che non sono compatibili con la scelta ingorda
✦
Mi resta solo un sottoproblema da risolvere: S[m,j]
✦
© Alberto Montresor
12
Realizzazione iterativa
✦
Complessità
✦
Inserisce la prima attività: è sempre compatibile
✦
Se l'input è già ordinato: θ(n)
✦
Altrimenti, è necessario un passo di ordinamento: θ(n log n)
© Alberto Montresor
13
i=0
1
2
3
4
5
6
7 Attività
8
9
10
11
Tempo
0
© Alberto Montresor
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
14
i=1
2
3
4
5
6
7 Attività
8
9
10
11
Tempo
0
© Alberto Montresor
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
15
i=1
2
3
4
5
6
7 Attività
8
9
10
11
Tempo
0
© Alberto Montresor
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
16
i=1
2
3
4
5
6
7 Attività
8
9
10
11
Tempo
0
© Alberto Montresor
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
17
1
2
3
i=4
5
6
7 Attività
8
9
10
11
Tempo
0
© Alberto Montresor
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
18
1
2
3
i=4
5
6
7 Attività
8
9
10
11
Tempo
0
© Alberto Montresor
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
19
1
2
3
i=4
5
6
7 Attività
8
9
10
11
Tempo
0
© Alberto Montresor
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
20
1
2
3
i=4
5
6
7 Attività
8
9
10
11
Tempo
0
© Alberto Montresor
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
21
1
2
3
4
5
6
7 Attività
i=8
9
10
11
Tempo
0
© Alberto Montresor
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
22
1
2
3
4
5
6
7 Attività
i=8
9
10
11
Tempo
0
© Alberto Montresor
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
23
1
2
3
4
5
6
7 Attività
i=8
9
10
11
Tempo
0
© Alberto Montresor
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
24
1
2
3
4
5
6
7 Attività
8
9
10
i=11
0
© Alberto Montresor
Tempo
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
25
Tecnica greedy – approccio a partire da PD
Abbiamo cercato di risolvere il problema della selezione delle attività tramite
programmazione dinamica:
✦
Abbiamo individuato una sottostruttura ottima
✦
Abbiamo scritto una definizione ricorsiva per la dimensione della soluzione ottima
✦
Abbiamo dimostrato la proprietà della scelta greedy:
✦
Per ogni sottoproblema, esiste almeno una soluzione ottima che inizia con la scelta
greedy
✦
Abbiamo scritto un algoritmo iterativo che effettua sempre la scelta ingorda
✦
© Alberto Montresor
26
Problema del resto
Input
✦
Un numero intero positivo n
✦
Output
✦
Il più piccolo numero intero di pezzi per dare un resto di n centesimi utilizzando
monete da 50c, 10c, 5c e 1c.
✦
Esempi
✦
n = 78,
7 pezzi: 50+10+10+5+1+1+1
n = 18,
5 pezzi: 10+5+1+1+1
✦
✦
Seguiamo la stessa procedura
precedente:
✦
Programmazione dinamica → approccio greedy
✦
© Alberto Montresor
27
Problema del resto
Domanda
✦
Descrivere un alg. goloso per dare il resto con le monete specificate
✦
Sottostruttura ottima
✦
Scelta ingorda
✦
Provare che tale algoritmo fornisce sempre una soluzione ottima
✦
Domanda
✦
Supponete di avere un insieme di monete i cui valori siano potenze di c:
c0, c1, c2, ..., ck
✦
L'algoritmo visto in precedenza funziona ancora?
✦
Domanda
✦
Trovare un insieme di “pezzature” per cui la scelta golosa non è applicabile
✦
© Alberto Montresor
28
Tecnica greedy – approccio senza passare per PD
Evidenziare i “passi di decisione”
✦
Trasformare il problema di ottimizzazione in un problema di “scelte” successive
✦
Evidenziare una possibile scelta ingorda
✦
Dimostrare che tale scelta rispetto il “principio della scelta ingorda”
✦
Evidenziare la sottostruttura ottima
✦
Dimostrare che la soluzione ottima del problema “residuo” dopo la scelta ingorda
può essere unito a tale scelta
✦
Scrittura codice: top-down, anche in maniera iterativa
✦
Nota: può essere necessario pre-processare l'input
✦
© Alberto Montresor
29
Algoritmo di scheduling
Definizione:
4
✦
1 processore, n job p1, p2, ..., pn
✦
1
Ogni job pi ha un tempo di esecuzione t[i]
✦
6
Minimizzare il tempo di completamento medio
✦
3
Domanda: Risolvere il problema tramite la tecnica greedy
✦
Shortest job first
4
1
0
4
1
0 1
© Alberto Montresor
3
6
5
11
4
4
(4+5+11+14)/4 = 34/4
3
14
(1+4+8+14)/4 = 27/4
6
8
14
30
Zaino
Input
✦
Un intero positivo C - la capacità dello zaino
✦
n oggetti, tali che l’oggetto i-esimo è caratterizzato da:
✦
un profitto pi e
✦
un volume vi , entrambi interi positivi
✦
Zaino (o Zaino 0/1)
✦
trovare un sottoinsieme S di {1, . . . , n} di oggetti tale che il volume totale non
superi la capacità massima e il profitto totale sia massimo
✦
Zaino reale (o Zaino frazionario)
✦
E' possibile prendere frazioni di oggetti
✦
© Alberto Montresor
31
p[]
€60
v[]
10
€125
25
€120
C
30
55
Scegli per primo l’oggetto che ha profitto più alto
25
© Alberto Montresor
30
€125 + €120 = €245
32
p[]
€60
v[]
10
€125
25
€120
C
30
55
Scegli per primo l’oggetto che ha profitto più alto
25
30
€125 + €120 = €245
Scegli per primo l’oggetto che ha volume più alto
30
© Alberto Montresor
25
€120 + €125 = €245
33
p[]
v[]
€60
€125
€5 per litro
25
€120
C
€6 per litro
10
€4 per litro
30
55
Scegli per primo l’oggetto che ha profitto più alto
25
€125 + €120 = €245
30
Scegli per primo l’oggetto che ha volume più alto
30
25
€120 + €125 = €245
Scegli per primo l’oggetto che ha il più alto “profitto specifico”
10
25
20/30
€60 + €120 + €80 = €260
© Alberto Montresor
34
Problema dello zaino
Domanda:
✦
Dimostrare che il problema dello Zaino Reale gode della scelta greedy
✦
Dimostrare che il problema dello Zaino 0-1 non gode di scelta greedy
✦
In altre parole:
✦
Risolvere il problema dello Zaino Reale con programmazione dinamica è inutile e
costoso
✦
Risolvere il problema dello Zaino 0-1 con tecnica greedy è scorretto
✦
© Alberto Montresor
35
Zaino reale
Complessità
✦
O(n log n) per l’ordinamento
✦
O(n) per la scelta dei valori
✦
© Alberto Montresor
36
Problema della compressione
Rappresentare i dati in modo efficiente
✦
Impiegare il numero minore di bit per la rappresentazione
✦
Goal: risparmio spazio su disco e tempo di trasferimento
✦
Una possibile tecnica di compressione: codifica di caratteri
✦
Tramite funzione di codifica f: f(c) = x
✦
c
è un possibile carattere preso da un alfabeto Σ
x
è una rappresentazione binaria
✦
✦
“c è rappresentato da x”
✦
© Alberto Montresor
37
Codici di Huffman
Supponiamo di avere un file di n caratteri
✦
Composto dai caratteri:
d
e
a
f
Con le seguenti frequenze: 45%
13%
✦
✦
b
12%
16%
c
9%
5%
Codifica tramite ASCII (8 bit per carattere)
✦
Dimensione totale: 8n bit
✦
Codifica basata sull'alfabeto (3 bit per carattere)
✦
Codifica:
011
100
000
✦
001
010
101
Dimensione totale: 3n bit
✦
Possiamo fare di meglio?
✦
© Alberto Montresor
38
Codici di Huffman
Codifica a lunghezza variabile
✦
Caratteri: a
f
b
✦
c
0
Costo totale:
(0.45⋅1+0.13⋅3+0.12⋅3+0.16⋅3+0.09⋅4+0.05⋅4)⋅n=2.24n
✦
100
e
Codifica:
1101 1100
✦
101
d
111
Codice “a prefisso” (meglio, “senza prefissi”):
✦
Nessun codice è prefisso di un altro codice
✦
Condizione necessaria per permettere la decodifica Considerate questo codice:
f(a) = 1, f(b)=10, f(c)=11
✦Esempio: ADDAABCA
✦
0·111·111·0·0·101·100·0
✦
© Alberto Montresor
39
Codici di Huffman

Alcune domande

E' possibile che il testo codificato sia più lungo della rappresentazione con 3 bit?

Esistono testi “difficili” per una rappresentazione di questo tipo?

Come organizzare un algoritmo per la decodifica?

Come organizzare un algoritmo per la codifica è il tema dei lucidi seguenti

Cenni storici

David Huffman, 1952

Algoritmo ottimo per costruire codici prefissi

Utilizzato in PKZIP
© Alberto Montresor
40
Rappresentazione ad albero per la decodifica
Algoritmo di decodifica:
Rappresentazione come alberi binari
✦
Figlio sinistro: 0
✦
Figlio destro: 1
1. parti dalla radice
2. leggi un bit alla volta
percorrendo l'albero:
0: sinistra
1: destra
3. stampa il carattere
della foglia
4. torna a 1
Caratteri dell'alfabeto sulle foglie
✦
1
0
0
1
0
a
© Alberto Montresor
0
1
0
1
b
c
d
e
a: 00
b: 010
c: 011
d: 100
e: 101
41
Rappresentazione ad albero per la decodifica
Non c'è motivo di avere un nodo interno con un solo figlio
✦
Il “figlio unico” può essere sostituito al proprio genitore
✦
Sia che sia una foglia che un nodo interno
✦
1
0
0
1
0
Spazio sprecato
a
© Alberto Montresor
0
1
0
1
b
c
d
e
a: 00
b: 010
c: 011
d: 100
e: 101
42
Rappresentazione ad albero per la decodifica

a: 00
b: 010
c: 011
d: 100
e: 101
Non c'è motivo di avere un nodo interno con un solo figlio
Il “figlio unico” può essere sostituito al proprio genitore


Sia che sia una foglia che un nodo interno
1
0
0
1
a
© Alberto Montresor
0
1
b
c
0
1
d
e
In questo albero
interno ha due figli
ogni
nodo
a: 00
b: 010
c: 011
d: 10
e: 11
43
Definizione formale del problema
Definizione: codice ottimo
✦
Dato un file F, un codice C è ottimo per F se non esiste un altro codice tramite il
quale F possa essere compresso impiegando un numero inferiore di bit.
✦
Nota:
✦
Il codice ottimo dipende dal particolare file
✦
Possono esistere più soluzioni ottime
✦
Nota:
✦
I codici a prefisso ottimi sono rappresentati da un albero in cui tutti i nodi interni
hanno due figli
✦
© Alberto Montresor
44
Definizione formale del problema
Supponiamo di avere:
✦
un file F composto da caratteri nell’alfabeto Σ
✦
un albero T che rappresenta la codifica
✦
Quanti bit sono richiesti per codificare il file?
✦
Per ogni c ∈ Σ, sia dT(c) la profondità della foglia che rappresenta c
✦
Il codice per c richiederà allora dT(c) bit
✦
Se f [c] è il numero di occorrenze di c in F, allora la dimensione della codifica è
✦
© Alberto Montresor
45
Algoritmo di Huffman
Principio del codice di Huffman
✦
Minimizzare la lunghezza dei caratteri che compaiono più frequentemente
✦
Assegnare ai caratteri con la frequenza minore i codici corrispondenti ai percorsi
più lunghi all’interno dell’albero
✦
Un codice è progettato per un file specifico
✦
Si ottiene la frequenza di tutti i caratteri
✦
Si costruisce il codice
✦
Si rappresenta il file tramite il codice
✦
Si aggiunge al file una rappresentazione del codice
✦
© Alberto Montresor
46
Costruzione del codice
Passo 1: Costruire una lista ordinata di nodi foglia per
ogni carattere, etichettato con la propria frequenza
f : 5 e : 9 c : 12 b : 13 d : 16 a : 45
© Alberto Montresor
47
Costruzione del codice
Passo 2: Rimuovere i due nodi “più piccoli”
(con frequenze minori)
Passo 3: Collegarli ad un nodo padre etichettato
con la frequenza combinata (sommata)
c : 12 b : 13 d : 16 a : 45
14
f: 5 e: 9
© Alberto Montresor
48
Costruzione del codice
Passo 4: Aggiungere il nodo combinato alla lista.
c : 12 b : 13 14 d : 16 a : 45
f: 5 e: 9
© Alberto Montresor
49
Costruzione del codice
Ripetere i passi 2-4 fino a quando non resta un solo nodo
nella lista
14
f: 5 e: 9
© Alberto Montresor
d : 16
25
a : 45
c : 12 b : 13
50
Costruzione del codice
Ripetere i passi 2-4 fino a quando non resta un solo nodo
nella lista
25
c : 12
30
b : 13
14
a : 45
d : 16
f: 5 e: 9
© Alberto Montresor
51
Costruzione del codice
Ripetere i passi 2-4 fino a quando non resta un solo nodo
nella lista
55
a : 45
30
25
c : 12
b : 13
14
d : 16
f: 5 e: 9
© Alberto Montresor
52
Costruzione del codice
Al termine, si etichettano gli archi dell'albero con bit 0-1
0
100
a
1
0
0
c
25
55
1
0
b
14
0
f
© Alberto Montresor
1
30
1
1
d
e
53
Algoritmo in pseudo-codice
Tree:
f
c
left
right
// frequenza (key)
// carattere
// figlio sinistro
// figlio destro
Complessità
θ(n log n)
© Alberto Montresor
54
Dimostrazione di correttezza
Teorema: L'output dell'algoritmo Huffman per un dato file è un codice a prefisso
ottimo
✦
Schema della dimostrazione:
✦
Proprietà della scelta greedy
✦Scegliere i due elementi con la frequenza più bassa conduce sempre ad una
soluzione ottimale
✦
Sottostruttura ottima
✦
Dato un problema sull'alfabeto Σ, è possibile costruire un sottoproblema con un
alfabeto più piccolo
✦
© Alberto Montresor
55
Scelta greedy
Sia
✦
Σ un alfabeto, f un vettore di frequenze
✦
x, y i due caratteri che hanno frequenza più bassa
✦
Allora
✦
Esiste un codice prefisso ottimo per Σ in cui x,y hanno la stessa profondità massima
e i loro codici differiscono solo per l'ultimo bit (sono foglie sorelle)
✦
Dimostrazione
✦
Al solito, basata sulla trasformazione di una soluzione ottima
✦
Supponiamo che esistano due caratteri a,b con profondità massima e questi siano
diversi da x,y
✦
© Alberto Montresor
56
Scelta greedy
Assumiamo (senza perdere in generalità):
f[x] ≤ f[y]
f[a] ≤ f[b]
Poiché le frequenze di x e y sono minime:
f[x] ≤ f[a]
f[y] ≤ f[b]
✦
✦
Scambiamo x con a: otteniamo T'
✦
Scambiamo y con b: otteniamo T"
✦
T
x
T'
a
a
...
...
...
y
a
© Alberto Montresor
b
T"
y
x
b
b
x
y
57
Scelta greedy
Dimostriamo che:
✦
C(f,T '') ≤ C(f, T ') ≤ C(f,T)
✦
Ma poiché T è ottimo, sappiamo anche che:
✦
C(f,T) ≤ C(f,T '')
✦
Quindi T” è anch'esso ottimo
✦
© Alberto Montresor
58
Sottostruttura ottima
Sia
✦
Σ un alfabeto, f un array di frequenze
✦
x, y i due caratteri che hanno frequenza più bassa
✦
Σ' = Σ - { x, y } ∪ { z }
✦
f[z] = f[x] + f[y]
✦
O un albero che rappresenta un codice a prefisso ottimo per Σ'
✦
Allora:
✦
L'albero T ottenuto da O sostituendo il nodo foglia z con un nodo interno con due
figli x, y rappresenta un codice a prefisso ottimo per Σ
✦
© Alberto Montresor
59
Sottostruttura ottima
Esprimiamo la relazione fra il costo di T e O
✦
Per ogni c ∈ Σ - { x, y } → f[c]·dT(c) = f[c]·dO(c)
Quindi tutte queste componenti sono uguali
✦
dT(x) = dT(y) = dO(z)+1
✦
da cui concludiamo
✦
f[x]·dT(x) + f[y]·dT(y) =
(f[x] + f[y])( dO(z)+1 ) =
f[z]·dO(z) + f[x] + f[y]
✦
da cui concludiamo
✦
C(f, T) = C(f, O) + f[x] + f[y]
C(f, O) = C(f, T) - f[x] - f[y]
✦
© Alberto Montresor
60
Sottostruttura ottima
Per assurdo: supponiamo T non sia ottimo
✦
Allora esiste un albero T' tale che C(f, T') < C(f, T)
✦
Senza perdere in generalità, sappiamo che T' ha x e y come foglie sorelle
(proprietà della scelta greedy)
✦
Sia T'' l'albero ottenuto da T' sostituendo il padre di x, y con un nodo z tale
che f[z] = f[x] + f[y]
✦
Allora
✦
C(f, T'')
✦
= C(f, T') – f[x] – f[y]
< C(f, T) – f[x] – f[y]
= C(f, O)
Il che è assurdo, visto che O è ottimo
✦
© Alberto Montresor
61
Albero di copertura di peso minimo
Un problema di notevole importanza:
✦
determinare come interconnettere diversi elementi fra loro minimizzando certi
vincoli sulle connessioni
✦
Esempio classico:
✦
progettazione dei circuiti elettronici dove si vuole minimizzare la quantità di filo
elettrico per collegare fra loro i diversi componenti
✦
Questo problema prende il nome di:
✦
albero di copertura (di peso) minimo
✦
albero di connessione (di peso) minimo
✦
minimum spanning tree
✦
© Alberto Montresor
62
Definizione del problema
Input:
✦
G=(V,E) un grafo non orientato e connesso
✦
w: V×V → R una funzione di peso (costo di connessione)
✦
se [u,v] ∈ E, allora
w(u,v) è il peso dell'arco [u,v]
se [u,v] ∉ E, allora
w(u,v) = ∞
✦
✦
Poiché G non è orientato, w(u,v) = w(v,u)
✦
© Alberto Montresor
63
Definizione del problema
Albero di copertura (spanning tree)
✦
Dato un grafo G=(V,E) non orientato e connesso, un albero di copertura di G è un
sottografo T=(V, ET) tale che
✦T è un albero
T
✦E ⊆ E
✦T contiene tutti i vertici di G
✦
8
7
b
c
4
2
a 11 7
i
8
h
9
14
4
g
1
© Alberto Montresor
6
d
f
e
10
2
64
Definizione del problema
Output: albero di copertura minimo (minimum spanning tree)
✦
L'albero di copertura il cui peso totale
✦
sia minimo
Nota: L’albero di copertura di peso minimo non è unico
✦
8
7
b
c
4
d
i
7
6
8
h
g
1
© Alberto Montresor
f
2
10
8
d
9
2
11
a
7
c
4
e
14
4
b
9
2
11
a
8
i
7
h
6
g
1
14
4
f
e
10
2
65
Differenze con cammini minimi
Calcolare
✦
un albero dei cammini minimi da singola sorgente a
✦
un albero di copertura minima
✦
coincidono?
✦
a
2
b
2
1
d
c
1
© Alberto Montresor
66
Algoritmo generico
Vediamo
✦
Un algoritmo di tipo “goloso” generico
✦
Due “istanze” di questo algoritmo: Kruskal e Prim
✦
L'idea è di accrescere un sottoinsieme A di archi in modo tale
che venga rispettata la seguente condizione:
✦
A è un sottoinsieme di qualche albero di connessione minimo
✦
Un arco [u,v] è detto sicuro per A se A ∪ {[u,v]} è ancora un
sottoinsieme di qualche albero di connessione minimo.
✦
© Alberto Montresor
67
Algoritmo generico
© Alberto Montresor
68
Definizioni
Per caratterizzare gli archi sicuri dobbiamo introdurre alcune definizioni:
✦
Un taglio (S,V-S) di un grafo non orientato G=(V,E) è una partizione di V in due
sottoinsiemi disgiunti
✦
Un arco [u,v] attraversa il taglio se u ∈S e v ∈V-S
✦
Un taglio rispetta un insieme di archi A se nessun arco di A attraversa il taglio
✦
Un arco che attraversa un taglio è leggero nel taglio se il suo peso è minimo fra i
pesi degli archi che attraversano un taglio
✦
© Alberto Montresor
69
Esempio
Arco leggero che
attraversa il taglio
8
7
b
c
4
9
2
11
a
d
i
7
6
14
4
8
h
g
1
f
2
10
e
V
Taglio
V-S
Insieme A: archi in grigio
Il taglio rispetta A
© Alberto Montresor
70
Archi sicuri
La regola per riconoscere gli archi sicuri è data dal seguente
✦
Teorema:
✦
Sia G=(V,E) un grafo non orientato e connesso
✦
Sia w una funzione peso a valori reali definita su E
✦
Sia A ⊆ E contenuto in un qualche albero di copertura minimo per G
✦
Sia (S,V-S) un qualunque taglio che rispetta A
✦
Sia [u,v] un arco leggero che attraversa il taglio.
✦
Allora
✦
l’arco [u,v] è sicuro per A
✦
© Alberto Montresor
71
Esempio: arco non sicuro perché il taglio non rispetta A
4
8
4
b
11
a
8
8
2
i
7
h
1
7
c
6
g
d
14
4
2
9
f
10
b
11
a
8
2
i
7
h
6
d
9
e
14
4
f
2
10
Arco sicuro
e
4
8
b
11
a
8
h
2
7
i
1
Arco non sicuro
© Alberto Montresor
c
g
1
7
7
c
6
g
d
14
4
2
9
f
e
10
72
Esempio: arco non sicuro perché non leggero
8
b
c
4
8
8
b
c
4
8
i
7
h
6
d
g
1
6
10
9
e
14
4
g
f
10
2
Arco sicuro
e
8
b
f
2
h
9
14
4
i
7
1
2
11
a
7
d
2
11
a
7
c
4
8
d
9
2
11
a
7
i
7
h
6
4
g
1
14
f
e
10
2
Arco non sicuro
© Alberto Montresor
73
Archi sicuri
Corollario:
✦
Sia G=(V,E) un grafo non orientato e connesso
✦
Sia w una funzione peso a valori reali definita su E
✦
Sia A ⊆ E contenuto in un qualche albero di copertura minimo per G
✦
Sia C una componente connessa (un albero) nella foresta GA=(V,A)
✦
Sia [u,v] un arco leggero che connette C a qualche altra componente in GA
✦
Allora
✦
l’arco [u,v] è sicuro per A
✦
© Alberto Montresor
74
Algoritmo di Kruskal
Idea
✦
Ingrandire sottoinsiemi disgiunti di un albero di copertura minimo connettendoli fra
di loro fino ad avere l’albero complessivo
✦
Si individua un arco sicuro scegliendo un arco [u,v] di peso minimo tra tutti gli
archi che connettono due distinti alberi (componenti connesse) della foresta
✦
L’algoritmo è greedy perché ad ogni passo si aggiunge alla foresta un arco con il
peso minore
✦
Implementazione
✦
Utilizziamo una struttura dati Merge-Find
✦
© Alberto Montresor
75
Algoritmo di Kruskal
© Alberto Montresor
76
Visualizzazione
8
7
b
c
4
8
d
i
7
h
6
4
g
1
f
b
8
i
h
h
g
f
e
14
f
10
8
d
9
2
11
a
10
7
c
4
e
2
b
9
9
14
4
8
4
2
6
1
d
g
1
© Alberto Montresor
6
i
7
7
c
7
8
10
2
11
a
11
a
d
2
2
8
4
c
4
e
14
7
b
9
2
11
a
8
i
7
h
6
g
1
e
14
4
f
10
2
77
Visualizzazione
8
7
b
c
4
8
d
i
7
h
6
4
g
1
f
b
8
i
7
h
f
10
8
10
f
7
c
d
9
2
11
a
e
2
4
e
14
4
2
4
g
b
9
9
14
8
d
g
1
© Alberto Montresor
6
6
h
7
c
i
7
1
2
11
a
11
a
8
10
d
2
2
8
4
c
4
e
14
7
b
9
2
11
a
8
i
7
h
6
g
1
e
14
4
f
10
2
78
Visualizzazione
8
b
c
4
2
a 11 7
i
8
h
6
d
g
f
b
4
2
a 11 7
i
8
10
2
a 11 7
i
h
6
g
1
f
b
e
14
4
2
f
10
2
a 11 7
i
8
h
6
d
9
e
14
4
g
1
10
7
c
4
e
2
8
9
9
14
4
1
d
g
d
6
h
7
c
4
© Alberto Montresor
e
c
2
8
7
b
9
14
4
1
8
8
7
f
10
2
79
Analisi
Il tempo di esecuzione per l’algoritmo di Kruskal dipende dalla realizzazione della
struttura dati per insiemi disgiunti
✦
Utilizziamo la versione con euristica sul rango + compressione
✦
L’inizializzazione richiede O(n)
✦
L'ordinamento richiede O(m log m) = O(m log n2) = O(m log n)
✦
Vengono eseguite O(m) operazioni sulla foresta di insiemi disgiunti, il che richiede
un tempo O(m)
✦
Totale:
✦
O(n+m log n + m) = O(m log n)
✦
© Alberto Montresor
80
Algoritmo di Prim
L’algoritmo di Prim procede mantenendo in A un singolo albero
✦
L’albero parte da un vertice arbitrario r (la radice) e cresce fino a quando non
ricopre tutti i vertici
✦
Ad ogni passo viene aggiunto un arco leggero che collega un vertice in VA con un
vertice in V-VA
✦
dove VA è l'insieme di nodi raggiunti da archi in A
✦
Correttezza
✦
(VA,V-VA) è un taglio che rispetta A (per definizione)
✦
Per il corollario, gli archi leggeri che attraversano il taglio sono sicuri
✦
© Alberto Montresor
81
Implementazione
Una struttura dati per i nodi non ancora nell'albero
✦
Durante l'esecuzione, i vertici non ancora nell'albero si trovano in una coda con
priorità Q ordinata in base alla seguente definizione di priorità:
✦
“La priorità del nodo v è il peso minimo di un arco che collega v ad un vertice
nell'albero, o +∞ se tale arco non esiste”
✦
Come mantenere l'albero
✦
Ogni nodo v mantiene un puntatore al padre p[v]
✦
A è mantenuto implicitamente: A = { [v, v.p] | v ∈V-Q-{r} }
✦
Terminazione: Quando la coda Q è vuota
✦
Tutti i nodi tranne la radice conoscono il proprio padre
✦
© Alberto Montresor
82
Algoritmo di Prim
© Alberto Montresor
83
Algoritmo di Prim: Esempio
4
b
8
c
4
8
d
i
7
h
8
6
g
1
f
b
8
7
h
8
© Alberto Montresor
i
6
7
d
h
8
2
f
4
9
6
4
f
1
2
8
7
c
8
i
7
h
7
6
7
d
1
9
2
e
10
f
6
10
14
4
g
e
14
2
11
a
d
g
4
e
10
i
7
b
9
14
4
g
1
8
10
2
11
a
7
c
2
11
a
7
2
2
8
4
4
e
14
4
b
9
2
11
a
8
c
8
7
4
84
Algoritmo di Prim: Esempio
8
7
b
c
4
2
a 11 7
i
8
h
7
d
6
1
7
h
7
d
i
f
2
h
6
e
10
2
a 11 7
i
h
1
10
f
7
c
4
8
10
e
2
b
9
9
14
4
g
1
7
d
8
14
4
g
1
© Alberto Montresor
6
a 11 7
8
10
i
2
1
2
a 11 7
8
10
7
c
4
2
c
4
e
10
f
8
b
b
9
14
4
g
2
8
7
6
g6
d
9
e
14
4
f
9
10
2
85
Algoritmo di Prim: Esempio
8
b
c
4
2
a 11 7
i
8
h
6
d
9
e
14
4
g
1
© Alberto Montresor
7
f
10
2
86
Algoritmo di Prim: Analisi
L’efficienza dell’algoritmo di Prim dipende dalla coda Q
✦
Se Q viene realizzata tramite uno heap binario:
✦
Inizializzazione: O(n log n)
✦
Il ciclo principale viene eseguito n volte ed ogni operazione extractMin() è
O(log n)
✦
Il ciclo interno viene eseguito O(m) volte
✦
L'operazione decreaseKey() sullo heap che costa O(log n)
✦
Tempo totale:
✦
O(n+n log n + m log n)=O(m log n)
✦
asintoticamente uguale a quello di Kruskal
✦
Cosa succede se la coda con priorità è implementata tramite vettore non ordinato?
✦
© Alberto Montresor
87
Esercizi
Vero o falso
✦
L’arco con peso minimo è sicuro
✦
L’arco con il secondo peso minimo è sicuro
✦
L’arco con il terzo peso minimo è sicuro
✦
Albero di copertura minima in un piano
✦
Dati n punti nel piano
✦
La distanza euclidea fra due punti è il peso di una connessione fra di essi
✦
Trovare un insieme di connessioni di peso minimo
✦
© Alberto Montresor
88
Conclusioni
Prospettiva storica
✦
Primo algoritmo: Boruvka 1926
✦
Kruskal 1956
✦
Prim 1957 (ma anche Jarnik nel 1930)
✦
Utilizzando gli heap di Fibonacci
✦
Prim viene eseguito in tempo O(m + n log n)
✦
Sviluppi recenti
✦
Karger, Klein, Tarjan (algoritmo randomizzato): O(n+m)
✦
Fredman, Willard (algoritmo non basato su confronti): O(n+m)
✦
© Alberto Montresor
89
Algoritmi greedy
Vantaggi
✦
Semplici da programmare
✦
Molto efficienti
✦
Quando è possibile dimostrare la proprietà di scelta ingorda,
danno la soluzione ottima
✦
La soluzione sub-ottima può essere accettabile
✦
Svantaggi
✦
Non sempre applicabili se si vuole la soluzione ottima
✦
© Alberto Montresor
90