Algoritmi Paralleli e Distribuiti a.a. 2008/09 Lezione del 28/04/2009 Prof. ssa ROSSELLA PETRESCHI a...

Algoritmi Paralleli e Distribuitia.a. 2008/09

Lezione del 28/04/2009

Prof.ssa ROSSELLA PETRESCHI

a cura del Dott. SAVERIO CAMINITI

Algoritmi Paralleli e Distribuiti a.a. 2008/09 2

Minimo Albero Ricoprente

Sia G=(V,E) un grafo connesso non orientato e w:ER una funzione costo degli archi di G. Definiamo inoltre m:VV nel seguente modo: m(u)=v sse (u,v) è l’arco di costo minimo incidente su u.

Un albero ricoprente (ST) di G=(V,E) è un albero T=(V,E') tale che E'E.

Un minimo albero ricoprente (MST) di G=(V,E) è un albero ricoprente T=(V,E') di costo minimo.

Il costo di un albero è la somma dei costi degli archi che lo compongono: w(T)=eT w(e).


Unicità del MST

Il MST è unico sse ogni arco ha un costo distinto. Tale condizione può essere forzata disambiguando eventuali costi uguali: si aggiunge al costo l’indice dell’arco cui appartiene:

w'(e) = <w(e),e>a

bd

c

e

<1,e1> <6,e2>

<2,e3>

<5,e6><2,e7>

<5,e4>

<2,e5>

<3,e8>

<1,e9>

Si noti che tra <2,e5> e <2,e7> viene scelto <2,e5>

a

bd

c

e

<1,e1>

<2,e3>

<2,e5>

<1,e9>

Nel seguito i costi verranno sempre disambiguati considerando gli archi indicizzati in base al loro ordine lessicografico.


Proprietà 1

Lemma1. Tutti gli archi (u,m(u))MST.

Dimostrazione. Sia G=(V,E) un grafo, w una funzione di costo su G e T il MST di G. Assumiamo per assurdo che esista un vV tale che (v,m(v))T.

Consideriamo il cammino da v a m(v) in T sia (v,x) il primo arco in tale cammino. Il costo di tale arco è sicuramente maggiore di quello dell’arco (v,m(v)), per definizione di m(v).Sia T' = T - (v,x) (v,m(v)). T' è un albero ricoprente per G e il suo costo w(T')=w(T)-w(v,x)+(v,m(v)) è minore di quello di T, il che contrasta con il fatto che T è il MST di G, quindi v non può esistere.


Stelle ed alberi radicati

Albero Radicato

Stella Radicata


Pseudoforesta

Si definisce pseudoforesta un grafo orientato in cui ogni vertice ha grado uscente minore od uguale ad uno. In altre parole, pseudoforesta è un insieme di alberi (e stelle) orientati radicati, ciascuno contenente un ciclo.

Una pseudoforesta può essere vista come una funzione d:VV.

vV, (v,d(v)) è l’unico arco uscente da v in G.

18

14

1

12

4

13

8 2

11 17 7 15 21

6

20

3 10

19 5

16

9

v d(v)1 142 133 204 215 106 67 28 139 10

10 2011 812 113 414 1815 216 2017 818 119 320 621 2


Proprietà 2

La funzione m:VV definisce una pseudoforesta t.c. ogni albero orientato ha un ciclo contenente esattamente due archi. Non ci sono cappi perché m(u)u uV. Se per assurdo ci fosse un ciclo di 3 (o più archi) tra i nodi u, v=m(u) e x=m(v) con u=m(x) allora considerando i costi di tali archi w1, w2 e w3 si avrebbe w1 < w3 < w2 < w1. Il che è assurdo.

v

u x

w1 w2w3


Strategie per MST

Prim: si parte da T = un singolo vertice e si costruisce incrementalmente il MST aggiungendo l’arco di costo minimo tra T e G-T.

Kruskal: si parte da una foresta di nodi isolati e, considerando tutti gli archi in ordine di costo crescente, si aggiunge ciascun arco solo se non induce un ciclo.

Sollin: si parte da una foresta di nodi isolati, si aggiungono tutti gli archi (u,m(u)) e si itera fino ad ottenere un grafo connesso.

Esempio 1

A partire dal grafo

Prim inizia con T=({a},). Poi inserisce, passo dopo passo, gli archi (a,g), (g,e), (a,b), (b,d), (b,f) e (d,c). L’albero ricoprente generato è:


d

c b

1

1

2a

f

e

g

2

2

1

11

3

4

1

d

c b

1

a

f

e

g

1

11

1

2

Esempio 2

Kruskal genera il medesimo MST analizzando gli archi nel seguente ordine (quelli che inducono cicli vengono scartati):


d

c b

1

a

f

e

g

1

11

1

2

e w(e) induce un ciclo?(a,g) 1 no(b,d) 1 no(b,f) 1 no(c,d) 1 no(d,f) 1 si(e,g) 1 no(a,b) 2 no(a,c) 2 si(f,g) 2 si(e,f) 3 si(b,g) 4 si

Esempio 3

Sollin inizialmente considera i seguenti archi:

ed ottiene:

In seguito considera gli archi tra le due componenti connesse:


d

c b

1

a

f

e

g

1

11

1

v m(v) costoa g 1b d 1c d 1d b 1e g 1f b 1g a 1

V m(V) costo arco originaleC1 C2 2 (a,b)C2 C1 2 (a,b)

d

c b

1

a

f

e

g

1

11

1

2

Algoritmi Paralleli e Distribuiti a.a.2007/08 12

Strategia per il concorrente

Sia Prim che Kruskal sono inerentemente sequenziali in quanto la scelta fatta ad ogni passo dipende strettamente da tutto ciò che si è fatto nei passi precedenti.

L’idea di Sollin invece (ad ogni iterazione) lavora su tutti i vertici senza richiedere un ordine specifico, quindi si presta meglio ad essere utilizzata in un contesto di calcolo concorrente (sia parallelo che distribuito).

Si noti però che se i costi non fossero distinti con Sollin si potrebbero introdurre cicli di lunghezza ≥ 3:

u m(u)a bb cc a

b

a c

1 1

1

b

a c


MST nel concorrente

Input: G grafo non orientato connesso pesato, con pesi distinti

Output: l’unico MST

Idea: partendo da frammenti costituiti da singoli nodi, ad ogni passo ogni frammento cerca di unirsi con un altro frammento attraverso lo spigolo di costo minimo ad esso incidente. Si ripete finché la foresta non si riduce ad un albero.


Come fare

• Identificare l’adiacente di costo minimo

• Rappresentare e identificare opportunamente i frammenti

• Fondere i frammenti avendo presente le limitazioni sul costo (tempo, processori, complessità dei messaggi) che si vuole ottenere

Algoritmi Paralleli e Distribuiti a.a. 2008/09 Lezione del 28/04/2009 Prof. ssa ROSSELLA PETRESCHI a...

Documents

Transcript of Algoritmi Paralleli e Distribuiti a.a. 2008/09 Lezione del 28/04/2009 Prof. ssa ROSSELLA PETRESCHI a...