Master Bioinformatica 2002: Grafi Problema: cammini minimi da tutti i vertici a tutti i vertici Dato...

Master Bioinformatica 2002: Grafi

Problema: cammini minimi da tutti i vertici a tutti i vertici

Dato un grafo pesato G =(V,E,w), trovare un cammino minimo tra ogni coppia di vertici.

Applicazione dei metodi di programmazione dinamica.


Sviluppo di un algoritmo di programmazione dinamica

• Caratterizzazione della struttura di una soluzione ottima

• definizione ricorsiva del valore di una soluzione ottima.

• Calcolo iterativo del valore di una soluzione ottima mediante una strategia bottom-up

• Costruzione di una soluzione ottima a partire dal valore calcolato


Cammino minimo

Peso di un cammino p = <v1,…,vk>

w(p) = k-1i=1 w(vi, vi+1)

Il peso di un cammino minimo da u a v è definito come

d(u,v) = min{w(p) | p: u v } se v è raggiungibile da u

= 0 se v = u

= se v non è raggiungibile da u


I pesi w degli archi sono valori interi, possono essere anche valori negativi. Assumiamo che il grafo non contenga cicli con pesi negativi, perchè in questo caso la nozione di cammino minimo non è ben definita

ab

c

3

-5

2

Percorrendo il ciclo svariate volte otteniamo un cammino con un peso sempre piu’ basso


Rappresentazione con matrice di adiacenza

Assumiamo che un grafo (orientato) pesato G = (V,E,w) con |V| = n sia rappresentato con una matrice di adiacenza n n W[i,j] definita come

W[i,j] = 0 se i = j

= w(i,j) se i j e (i,j) E

= se (i,j) E


Struttura dei cammini minimi

Proprietà della sottostruttura ottima: sia p un cammino ottimo: ogni sottocammino di p e’ ottimo.

v0 vivj

vk

p

pij

qij

Il sottocammino pij di p deve essere un cammino ottimo da vi a vj


Vertici intermedi

Sia p = <v1,v2…,vl> un cammino semplice da v1a,vl

i vertici intermedi sono v2,…,vl-1.

Siano V = {1,…,n} i vertici di un grafo G, considera per un vertice k arbitrario il sottoinsieme

{1,…,k}

siano i,j V.


Algoritmo di Floyd-Warshall

Considera tutti i cammini da i a j in cui vertici intermedi sono nell’insieme {1,…,k} e sia p un cammino minimo tra di essi.

E’ possibile definire una relazione tra p e i cammini minimi tra i vertici i e j i cui vertici intermedi sono nell’insieme

{1,…,k-1}


• Se k non e’ un vertice intermedio di p, allora tutti i vertici intermedi di p sono nell’insieme

{1,…,k-1}.

Questo significa che il peso di un cammino minimo da i a j in cui tutti i vertici intermedi sono in {1,…,k} è dato dal peso di un cammino minimo da i a j in cui tutti i vertci intermedi sono in {1,…,k-1}.


• Se k è un vertice intermedio di p allora possiamo spezzare p così:

i j

kp1 p2

• p1 e’ un cammino minimo da i a k in cui tutti i vertici intermedi sono nell’insieme {1,…,k-1}. • p2 e’ un cammino minimo da i a k in cui tutti i vertici intermedi sono nell’insieme {1,…,k-1}.


Questo significa che il peso di un cammino minimo da i a j in cui tutti i vertici intermedi sono in {1,…,k} è dato dal peso di un cammino minimo da i a k in cui tutti i vertci intermedi sono in {1,…,k-1} + il peso di un cammino minimo da k a j in cui tutti i vertci intermedi sono in {1,…,k-1}.


Relazione di ricorrenza

Definiamo

D(k) [i,j] = peso di un cammino minimo da i a j in

cui tutti i vertici intermedi sono

nell’insieme {1,…k}


D(k) [i,j] = W[i,j] se k = 0

D(k) [i,j] = min {D(k-1) [i,j], D(k-1) [i,k]+ D(k-1)[k,j]}

se k > 0


Sottoproblemi comuni

D(5)[1,6]

D(4)[1,6] D(4)[1,5] + D(4)[5,6]

D(3)[1,6] D(3)[1,4] + D(3)[4,6]

D(3)[1,5] D(3)[1,4] + D(3)[4,5]

D(3)[5,4] + D(3)[4,6]D(3)[5,6]


Calcolo iterativo della sequenza di matrici D(0),…, D(n)

Floyd-Warshall(W) //W matrice di adiacenza n n

D(0) W

for k = 1 to n

for i = 1 to n

for j = 1 to n

D(k) [i,j] min{D(k-1)[i,j], D(k-1)[i,k] + D(k-1)[k,j]}

return D(n)

Complessità: O(n3)


Calcolo dei cammini minimi

Matrice dei predecessori

P(k) [i,j] = predecessore di j in un cammino minimo

da i a j in cui tutti i vertici intermedi

sono nell’insieme {1,…,k}.

i jx

P(k) [i,j] = x


Relazione di ricorrenza per i predecessori

• per k = 0

P(k)[i,j] = NULL se i = j oppure W[i,j]= P(k)[i,j] = i se i j e W[i,j] <

• per k > 0

P(k)[i,j] = P(k-1)[i,j]

se D[i,j](k-1) D [i,k](k-1) + D[k,j](k-1)

P(k)[i,j] = P(k-1)[k,j]

se D[i,j](k-1) > D [i,k](k-1) + D[k,j](k-1)


Calcolo delle matrici D(0),…, D(n) e P(0),…, P(n)

Floyd-Warshall(W)Inizializza D(0) e P(0) mediante W

for k = 1 to n

for i = 1 to n

for j = 1 to n

D(k) [i,j] D(k-1)[i,j]

P(k) [i,j] P(k-1)[i,j]

if D(k) [i,j] > D (k-1) [i,k] + D(k-1)[k,j]

then D(k) [i,j] D (k-1) [i,k]+ D(k-1)[k,j]

P(k) [i,j] P(k-1)[k,j]

return <D(n), P(n) >


Esempio

1

2 4

32

53

5

-3

41 2 3 4

1 0 5 2 2 0 3 43 0 54 -3 0

W


1 2 3 41 0 5 2 2 0 3 43 0 54 -3 0

1 2 3 41 N 1 1 N2 N N 2 23 N N N 34 N 4 N N

1 2 3 41 0 5 2 2 0 3 43 0 54 -3 0

1 2 3 41 N 1 1 N2 N N 2 23 N N N 34 N 4 N N

D(0) P(0)

D(1) P(1)


1 2 3 41 0 5 2 2 0 3 43 0 54 -3 0

1 2 3 41 N 1 1 N2 N N 2 23 N N N 34 N 4 N N

1 2 3 41 0 5 2 92 0 3 43 0 54 -3 0 0

1 2 3 41 N 1 1 22 N N 2 23 N N N 34 N 4 2 N

D(1) P(1)

D(2) P(2)


1 2 3 41 0 5 2 92 0 3 43 0 54 -3 0 0

1 2 3 41 N 1 1 22 N N 2 23 N N N 34 N 4 2 N

1 2 3 41 0 5 2 72 0 3 43 0 54 -3 0 0

1 2 3 41 N 1 1 32 N N 2 23 N N N 34 N 4 2 N

D(2) P(2)

D(3) P(3)


1 2 3 41 0 5 2 72 0 3 43 0 54 -3 0 0

1 2 3 41 N 1 1 32 N N 2 23 N N N 34 N 4 2 N

1 2 3 41 0 4 2 72 0 3 43 2 0 54 -3 0 0

1 2 3 41 N 4 1 32 N N 2 23 N 4 N 34 N 4 2 N

D(3) P(3)

D(4) P(4)


1 2 3 41 N 4 1 32 N N 2 23 N 4 N 34 N 4 2 N1

2 4

32

535

-3

4

1 32

2 4

5

-3

1

2 4

33

4


1 2 3 41 N 4 1 32 N N 2 23 N 4 N 34 N 4 2 N1

2 4

32

535

-3

4

1

2 4

3

5

-3

1

2 4

33

-3

Master Bioinformatica 2002: Grafi Problema: cammini minimi da tutti i vertici a tutti i vertici Dato...

Documents

Transcript of Master Bioinformatica 2002: Grafi Problema: cammini minimi da tutti i vertici a tutti i vertici Dato...