Post on 01-May-2015
transcript
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.
Master Bioinformatica 2002: Grafi
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
Master Bioinformatica 2002: Grafi
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
Master Bioinformatica 2002: Grafi
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
Master Bioinformatica 2002: Grafi
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
Master Bioinformatica 2002: Grafi
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
Master Bioinformatica 2002: Grafi
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.
Master Bioinformatica 2002: Grafi
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}
Master Bioinformatica 2002: Grafi
• 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}.
Master Bioinformatica 2002: Grafi
• 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}.
Master Bioinformatica 2002: Grafi
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}.
Master Bioinformatica 2002: Grafi
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}
Master Bioinformatica 2002: Grafi
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
Master Bioinformatica 2002: Grafi
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]
Master Bioinformatica 2002: Grafi
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)
Master Bioinformatica 2002: Grafi
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
Master Bioinformatica 2002: Grafi
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)
Master Bioinformatica 2002: Grafi
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) >
Master Bioinformatica 2002: Grafi
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
Master Bioinformatica 2002: Grafi
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)
Master Bioinformatica 2002: Grafi
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)
Master Bioinformatica 2002: Grafi
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)
Master Bioinformatica 2002: Grafi
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)
Master Bioinformatica 2002: Grafi
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
Master Bioinformatica 2002: Grafi
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