Algoritmi e Strutture Dati - Università degli Studi di ... · 3! Algoritmi e strutture dati Luigi...
14
1 Minimo albero ricoprente Algoritmi e Strutture Dati Luigi Laura Luigi Laura Algoritmi e strutture dati da Demetrescu et al. McGraw Hill 2004 2 Definizioni Sia G = (V, E) un grafo connesso non orientato. Un albero ricoprente di G è un sottografo T ⊆ G tale che: – T è un albero; – T contiene tutti i vertici di G. Sia w(x,y) il costo (o peso) di un arco (x,y) ∈ E. Il costo di un albero è la somma dei costi dei suoi archi. Un minimo albero ricoprente di G è un albero ricoprente di costo minimo.
Transcript of Algoritmi e Strutture Dati - Università degli Studi di ... · 3! Algoritmi e strutture dati Luigi...
1
Minimo albero ricoprente
Algoritmi e Strutture Dati
Luigi Laura
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 2
Definizioni
Sia G = (V, E) un grafo connesso non orientato. Un albero ricoprente di G è un sottografo T ⊆ G tale che:
– T è un albero; – T contiene tutti i vertici di G.
Sia w(x,y) il costo (o peso) di un arco (x,y) ∈ E. Il costo di un albero è la somma dei costi dei suoi archi. Un minimo albero ricoprente di G è un albero ricoprente di costo minimo.
2
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 3
Esempi
Il minimo albero ricoprente non è necessariamente unico
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 4
Proprietà di minimi alberi ricoprenti
3
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 5
Tagli e cicli
Dato un grafo non orientato G = (V,E), un taglio in G è una partizione dei vertici V in due insiemi: X e V-X. Un arco e = (u,v) attraversa il taglio (X,X) se u ∈ X e v ∈ X
Un ciclo è un cammino in cui il primo e l’ultimo vertice coincidono
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 6
Un approccio “goloso” • Costruiremo un minimo albero ricoprente un arco
alla volta, effettuando scelte localmente “golose”. Ad esempio: – includere nella soluzione archi di costo piccolo – escludere dalla soluzione archi di costo elevato
• Formalizzeremo il processo come un processo di colorazione: – archi blu: inclusi nella soluzione – archi rossi: esclusi dalla soluzione
4
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 7
Regola del taglio (Regola blu)
Scegli un taglio che non contiene archi blu. Tra tutti gli archi non colorati del taglio, scegline uno di costo minimo e coloralo blu.
• Ogni albero ricoprente deve infatti contenere almeno un arco del taglio • E’ naturale includere quello di costo minimo
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 8
Regola del ciclo (Regola rossa)
Scegli un ciclo che non contiene archi rossi. Tra tutti gli archi non colorati del ciclo, scegline uno di costo massimo e coloralo rosso.
• Ogni albero ricoprente deve infatti escludere almeno un arco del ciclo • E’ naturale escludere quello di costo massimo
5
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 9
L’ approccio “goloso”
• L’approccio goloso applica una delle due regole ad ogni passo, finché tutti gli archi sono colorati
• Si può dimostrare che esiste sempre un minimo albero ricoprente che contiene tutti gli archi blu e non contiene nessun arco rosso.
• Si può inoltre dimostrare che il metodo goloso colora tutti gli archi.
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 10
Tempi di esecuzione
A seconda della scelta della regola da applicare e del taglio/ciclo usato ad ogni passo, si ottengono dal metodo goloso diversi algoritmi con diversi tempi di esecuzione
6
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 11
Algoritmo di Kruskal
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 12
Strategia • Mantieni foresta di alberi blu, all’inizio tutti
disgiunti • Per ogni arco, in ordine non decrescente di costo,
applica il passo seguente : “se l’arco ha entrambi gli estremi nello stesso albero blu, applica regola del ciclo e coloralo rosso, altrimenti applica regola del taglio e coloralo blu”
• I vertici nello stesso albero blu sono mantenuti tramite una struttura dati union/find
7
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 13
Pseudocodice
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 14
Esempio (1/2)
8
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 15
Esempio (2/2)
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 16
Analisi
Il tempo di esecuzione dell’algoritmo di Kruskal è O(m log n) nel caso peggiore
(Utilizzando un algoritmo di ordinamento ottimo e la struttura dati union-find)
9
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 17
Algoritmo di Prim
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 18
Strategia • Mantiene un unico albero blu T, che all’inizio consiste
di un vertice arbitrario • Applica per (n-1) volte il seguente passo:
scegli un arco di costo minimo incidente su T e coloralo blu (regola del taglio)
• Definiamo arco azzurro un arco (u,v) tale che u∈T, v∉T, e (u,v) ha il costo minimo tra tutti gli archi che connettono v ad un vertice in T: l’algoritmo mantiene archi azzurri in una coda con priorità da cui viene estratto il minimo ad ogni passo
10
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 19
Pseudocodice
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 20
Esempio (1/2)
11
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 21
Esempio (2/2)
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 22
Analisi
Il tempo di esecuzione dell’algoritmo di Prim è O(m + n log n) nel caso peggiore
(Realizzando la coda con priorità tramite heap di Fibonacci)
12
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 23
Algoritmo di Boruvka °
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 24
Strategia • Mantiene una foresta di alberi blu, all’inizio tutti
disgiunti • Ad ogni passo, applica la regola seguente:
per ogni albero blu T nella foresta, scegli un arco di costo minimo incidente su T e coloralo blu (regola del taglio)
• Per non rischiare di introdurre cicli, assumiamo che i costi degli archi siano tutti distinti
• Non è necessario usare strutture dati sofisticate
13
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 25
Esempio
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 26
Analisi
Il tempo di esecuzione dell’algoritmo di Boruvka è O(m log n) nel caso peggiore
(Senza usare strutture dati sofisticate)
°
14
Luigi Laura Algoritmi e strutture dati
da Demetrescu et al. McGraw Hill 2004 27
Riepilogo
• Paradigma generale per il calcolo di minimi alberi ricoprenti
• Applicazione della tecnica golosa • Tre algoritmi specifici ottenuti dal paradigma
generale: Prim, Kruskal e Boruvka • L’uso di strutture dati sofisticate ci ha permesso
di implementare tali algoritmi in modo efficiente
°
