Strutture dati per insiemi disgiunti

Servono a mantenere una collezione C = {S1, S2, ... , Sk}

di insiemi disgiunti.

Ogni insieme della collezione è individuato da un rappresentante che è uno degli elementi dell’insieme.

Operazioni sugli insiemi disgiunti:

MakeSet(x) : aggiunge alla struttura dati un nuovo insieme contenente solo l’elemento x.Si richiede che x non compaia in nessun altro insieme della struttura.

FindSet(x) : ritorna il rappresentante dell’insieme che contiene x.

Union(x, y) : riunisce i due insiemi contenenti x ed y in un unico insieme.

Esercizio 29Sia data una rete con n nodi x1, x2, … , xn ed m canali di trasmissione c1, c2, … , cm e per ogni canale ci siano dati i due nodi xi ed yi che tale canale connette direttamente.

Descrivere un algoritmo che utilizza una struttura dati per insiemi disgiunti per determinare se la rete è connessa, ossia se è sempre possibile mandare un messaggio da un qualsiasi nodo ad un qualsiasi altro nodo.

Rappresentazione con liste

Il modo più semplice per rappresentare una collezione di insiemi disgiunti è usare una lista circolare per ciascun insieme.

c h e b

I nodi hanno i seguenti campi:info : l’informazione contenuta nel nodor : il puntatore al rappresentantesucc : il puntatore al nodo successivoLe operazioni sono:

MakeSet(x) x.r = x x.succ = x

FindSet(x) return x.r c h e

x

fx

c h e b

f g d

x

y

c h e b

f g d

x

y

Union(x,y)

Union(x, y) // cambia i puntatori r nella lista di y y.r = x.r, z = y.succ while z ≠ y z.r = x.r, z = z.succ // concatena le due liste z = x.succ, x.succ = y.succ, y.succ = z

La complessità di Union dipende dal numero di iterazioni richieste dal ciclo che cambia i puntatori al rappresentante dei nodi della lista contenente y.

Quindi Union ha complessità O(n2) dove n2 è la lunghezza della seconda lista.

Consideriamo la sequenza di 2n-1 operazioni:

MakeSet(x1)// costo 1MakeSet(x2)// costo 1.......MakeSet(xn)// costo 1

Union(x2, x1) // costo 1Union(x3, x1) // costo 2Union(x4, x1) // costo 3.......Union(xn, x1) // costo n-1

Il costo totale è proporzionale ad n+n(n-1)/2 ed è (n2)e le operazione hanno costo ammortizzato O(n).

Euristica dell’unione pesata

La complessità (n2) dell’esempio è dovuta al fatto che, in ogni Union, la seconda lista, quella che viene percorsa per aggiornare i puntatori al rappresentante, è la più lunga delle due.

L’euristica dell’unione pesata sceglie sempre la lista più corta per aggiornare i puntatori al rappresentante.

Per poter fare ciò basta memorizzare la lunghezza della lista in un nuovo campo L del rappresentante.

c h e b4 # # #L L L L

4c h e b1 0 0 0L b b b b

Si può risparmiare memoria usando un campo booleano b per distinguere il rappresentante.

Naturalmente occorre modificare le funzioni:

MakeSet(x) x.b = true x.L = 1 x.succ = x

FindSet(x) if x.b return x else return x.r

Union(x, y) x = FindSet(x) y = FindSet(y) // se la lista di x è più corta scambia x con y if x.L < y.L z = x, x = y, y = z x.L = x.L + y.L // cambia rappresentante alla lista di y y.b = false, y.r = x, z = y.succ while z ≠ y z.r = x, z = z.succ // concatena le due liste z = x.succ, x.succ = y.succ, y.succ = z

Dimostreremo che con l’euristica dell’unione pesata una sequenza di m operazioni delle quali n sono MakeSet richiede tempo O(m + n log n)

La complessità ammortizzata delle operazioni è quindi:

)(log)log

1()log

( nOm

nnO

m

nnmO

Se il numero n di MakeSet è molto minore di m per cui n log n = O(m)

)1()log

1( Om

nnO

DimostrazioneTutte le operazioni richiedono un tempo costante eccetto Union che richiede un tempo costante più un tempo proporzionale al numero di puntatori al rappresentante che vengono modificati.

Il tempo richiesto dalla sequenza di m operazioni è quindi O(m + N) dove N è il numero totale di aggiornamenti dei puntatori al rappresentante eseguiti durante tutta la sequenza di operazioni.

Il numero massimo di oggetti contenuti nella struttura è n: il numero di MakeSet.

MakeSet(x) crea un insieme con un solo elemento.

x.r viene aggiornato quando l’insieme viene unito ad un insieme di cardinalità maggiore o uguale per cui la cardinalità diventa almeno il doppio.

Siccome un insieme non può avere più di n elementi x.r può essere aggiornato al più log2 n volte.

Quindi N ≤ n log2 n.

Rappresentazione con foreste

Una rappresentazione più efficiente si ottiene usando foreste di insiemi disgiunti.

Ogni insieme è rappresentato da un albero i cui nodi, oltre al campo info che contiene l’informazione, hanno soltanto un campo p che punta al padre.

b

eh

c

g

d

f

MakeSet(x) x.p = x

FindSet(x) while x.p ≠ x x = x.p return x

Union(x, y) x = FindSet(x) y = FindSet(y) x.p = y // serve controllare se x ≠ y ?

Implementazione semplice:

b

eh

c

g

d

f

b

eh

c

g

d

f

x y

x

y

Osservazione. Sia nella rappresentazione con liste circolari che in quella con alberi non abbiamo indicato nessun puntatore esterno alla lista o all’albero.

In realtà una struttura dati per insiemi disgiunti non è pensata per memorizzare dei dati ma soltanto per raggruppare in insiemi disgiunti dei dati che sono già memorizzati in qualche altra struttura: array, pila, lista, albero, tavola hash, ecc.

Complessità dell’implementazione semplice

La complessità di FindSet(x) è pari alla lunghezza del cammino che congiunge il nodo x alla radice dell’albero.

La complessità di Union è essenzialmente quella delle due chiamate FindSet(x) e FindSet(y).

Un esempio analogo a quello usato con le liste mostra che una sequenza di n operazioni può richiedere tempo O(n2).

Possiamo migliorare notevolmente l’efficienza usando due euristiche:

L’euristica dell’unione per rango: E’ simile a quella dell’unione pesata per le liste.

In ogni nodo x manteniamo un campo rank che è un limite superiore all’altezza del sottoalbero di radice x ed è anche una approssimazione del logaritmo del numero di nodi del sottoalbero.

L’operazione Union mette la radice con rango minore come figlia di quella di rango maggiore.

L’euristica della compressione dei cammini:

Quando effettuiamo una FindSet(x) attraversiamo il cammino da x alla radice.

Possiamo approfittarne per far puntare alla radice dell’albero i puntatori al padre di tutti i nodi incontrati lungo il cammino.

Le successive operazioni FindSet sui nodi di tale cammino risulteranno molto meno onerose.

L’implementazione con entrambe le euristiche è la seguente:

MakeSet(x) x.p = x x.rank = 0

b

eh

c

g

d

f

x

b

e

h c

g

d

f

x

FindSet(x) if x.p ≠ x x.p = FindSet(x.p) return x.p

Link(x, y) if x.rank > y.rank y.p = x else x.p = y if x.rank == y.rank y.rank = y.rank + 1

Union(x, y) x = FindSet(x) y = FindSet(y) Link(x, y)

Considerazioni generali sulla complessità:

Usate separatamente entrambe le euristiche (unione per rango e compressione dei cammini) migliorano le prestazioni.

Con la sola euristica dell’unione per rango una sequenza di m operazioni delle quali n sono MakeSet richiede tempo O(m log n)

Con la sola euristica della compressione dei cammini una sequenza di m operazioni delle quali n sono MakeSet e k sono FindSet richiede tempo

nknk nk se )log( )1(

Esempio: m ≥ 1000, n = 100 e k = 900 1800100log900log 10)1( nk nk

nknkn se )log(Esempio: m ≥ 1000, n = 512 e k = 100

1412512log001512 log 2 nkn

Le migliori prestazioni in assoluto si ottengono usando entrambe le euristiche.

Una sequenza di m operazioni delle quali n sono MakeSet richiede tempo O(m α(n)) dove α(n) è una funzione che cresce estremamente lentamente: α(n) ≤ 4 in ogni concepibile uso della struttura dati.

La complessità ammortizzata di una singola operazione risulta quindi O(α(n)): praticamente costante.

La funzione α(n)

Iterazione di una funzione:

0 se))((

0 se)( )1(

)(

inff

innf i

i

Funzione di Ackermann:

0 se)(

0 se1)( )1(

1 kjA

kjjA j

kk

k è detto livello della funzione.

Possiamo calcolare Ak(x) ricorsivamente nel modo seguente:

Ackerman(k, j) if k = 0 return j+1 else a = j for i = 1 to j+1 a = Ackerman(k-1, a) return a

Se il livello k è fissato possiamo calcolare Ak(x) iterativamente con k cicli for annidati:

Ak(j) a = j, nk-1 = a+1 for ik-1 = 1 to nk-1 // calcola Ak-1

(a+1) (j)

nk-2 = a+1 for ik-2 = 1 to nk-2 // calcola Ak-2

(a+1) (j)

………… n1 = a+1 for i1 = 1 to n1 // calcola A1

(a+1) (j)

n0 = a+1 for i0 = 1 to n0 // calcola A0

(a+1) (j)

a = a+1 return a

Come cresce la funzione di Ackermann?Calcoliamo A1(j) sapendo che A0( j) = j+1

ijjAAjA

jjAAjA

jjAjA

jjA

ii

))(()(

2))(()(

1)()(

)(

)1(00

)(0

00)2(

0

0)1(

0

)0(0

1)1(21)()( )1(01 jjjjAjA j

Quindi

Calcoliamo A2( j)

1)1(2))(()(

1)1(41)1)1(2(2))(()(

1)1(2)()(

)(

)1(11

)(1

11)2(

1

1)1(

1

)0(1

jjAAjA

jjjAAjA

jjAjA

jjA

iii

1)1(2)()( 1)1(12 jjAjA jj

Quindi

Calcoliamo A3(1) e A4(1)

2047

12

182

)7(

))1((

)1()1(

11

8

2

22

)2(23

A

AA

AA

6202059

2048

20482

3

33

)2(34

1012

120482

)2047(

)2047(

))1((

)1()1(

A

A

AA

AA

La funzione inversa è

6204

3

2

1

0

10)1(2048per 4

2047)1(8per 3

7)1(4per 2

3)1(3per 1

2)1(0per 0

)(

An

An

An

An

An

n

nAkn k )1(| min)(

In ogni applicazione pratica α(n) ≤ 4.

hAh ))1((

Il numero stimato di atomi dell’universo è 1080 !!!