Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi
-
Upload
adrian-porter -
Category
Documents
-
view
25 -
download
0
description
Transcript of Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi
![Page 1: Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi](https://reader030.fdocumenti.com/reader030/viewer/2022032606/56812ec5550346895d9464cf/html5/thumbnails/1.jpg)
Lezione n° 21: 25-26 Maggio 2009
Problema dell’albero dei cammini minimi
Anno accademico 2008/2009
Prof. Cerulli – Dott.ssa Gentili
Lezioni di Ricerca OperativaCorso di Laurea in Informatica ed Informatica Applicata
Università di Salerno
![Page 2: Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi](https://reader030.fdocumenti.com/reader030/viewer/2022032606/56812ec5550346895d9464cf/html5/thumbnails/2.jpg)
Il problema dei cammini minini
1
5
6
4
7
2
3
8
9
69
44
7
1
35
G=(N,A)
5
7
1
21
15
sorgente
1128
940
10
21
cij = costo dell’arco (i,j)
xij = variabili
decisionali
xij
=
1 se xijp
0 se xijp
destinazione
p
![Page 3: Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi](https://reader030.fdocumenti.com/reader030/viewer/2022032606/56812ec5550346895d9464cf/html5/thumbnails/3.jpg)
Modello matematico1
5
6
4
7
2
3
8
9
69
44
7
1
35
5
7
1
21
15
1128
940
10
21
![Page 4: Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi](https://reader030.fdocumenti.com/reader030/viewer/2022032606/56812ec5550346895d9464cf/html5/thumbnails/4.jpg)
Modello matematico
1
5
6
4
7
2
3
8
9
69
44
7
1
35
5
7
1
21
15
1128
940
10
21
![Page 5: Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi](https://reader030.fdocumenti.com/reader030/viewer/2022032606/56812ec5550346895d9464cf/html5/thumbnails/5.jpg)
Modello matematico
1
5
6
4
7
2
8
9
69
44
7
1
35
5
7
1
21
15
1128
40
21
![Page 6: Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi](https://reader030.fdocumenti.com/reader030/viewer/2022032606/56812ec5550346895d9464cf/html5/thumbnails/6.jpg)
Il problema dei cammini minini (varianti)
Uno ad uno
Uno a tutti
Tutti a tutti
![Page 7: Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi](https://reader030.fdocumenti.com/reader030/viewer/2022032606/56812ec5550346895d9464cf/html5/thumbnails/7.jpg)
Il problema dei cammini minini
1
5
6
4
7
2
3
8
9
69
44
7
1
35
5
7
1
21
15
sorgente
1128
940
10
21
T
G=(N,A)
![Page 8: Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi](https://reader030.fdocumenti.com/reader030/viewer/2022032606/56812ec5550346895d9464cf/html5/thumbnails/8.jpg)
Etichette dei nodi
1
5
6
4
7
2
3
8
9
69
44
7
1
35
G=(N,A)
5
7
1
21
15
1128
940
10
21
d1 d2 d9
d5
d6
d7
d8
d3
d4
![Page 9: Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi](https://reader030.fdocumenti.com/reader030/viewer/2022032606/56812ec5550346895d9464cf/html5/thumbnails/9.jpg)
Algoritmo prototipoPasso 1: Inizializzazione.
ds=0, Ps=NULL, dk=, Pk=s kN\{s},
Q={s};
Passo 2: Estrai un vertice x da Q (Q= Q \{x}) ed aggiorna quando possibile le etichette dei vertici in FS(x):
yFS(x) se dx + cxy < dy allora
dy = dx + cxy , Py= x e se y Q inseriscilo in Q (Q= Q {y}) (test di ottimalità)
![Page 10: Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi](https://reader030.fdocumenti.com/reader030/viewer/2022032606/56812ec5550346895d9464cf/html5/thumbnails/10.jpg)
Aggioramento delle etichette
5
9
427
34
15
42
67
18
21
yFS(x) se dx + cxy < dy allora dy = dx + cxy e Py= x
x=4, y=5d4 + c45 < d5 ?d5 = d4 + c45 e P5= 4
x=4, y=2d4 + c42 < d2 ?
…………………
x=4, y=9d4 + c49 < d9 ?d9 = d4 + c49 e P9= 4
36
55
![Page 11: Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi](https://reader030.fdocumenti.com/reader030/viewer/2022032606/56812ec5550346895d9464cf/html5/thumbnails/11.jpg)
Algoritmo prototipoPasso 1: Inizializzazione.
ds=0, Ps=NULL, dk=, Pk=s kN\{s},
Q={s};
Passo 2: Estrai un vertice x da Q (Q= Q \{x}) ed aggiorna quando possibile le etichette dei vertici in FS(x):
yFS(x) se dx + cxy < dy allora
dy = dx + cxy , Py= x e se y Q inseriscilo in Q (Q= Q {y}) (test di ottimalità)
Passo 3: Fino a quando Q ripeti il passo 2 ;
![Page 12: Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi](https://reader030.fdocumenti.com/reader030/viewer/2022032606/56812ec5550346895d9464cf/html5/thumbnails/12.jpg)
Gli algoritmi per l’SPT si distinguono per:
– La politica di estrazione del nodo da Q (label setting e label correcting)
– La struttura dati utilizzata per implementare Q
Differenti implementazioni
![Page 13: Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi](https://reader030.fdocumenti.com/reader030/viewer/2022032606/56812ec5550346895d9464cf/html5/thumbnails/13.jpg)
Dijkstra (G,s)
Inizializzazione; ( ds=0, Ps=NULL, dk=, Pk=s kN\{s} , Q={s})
while ( Q ){ x = Extract_min(Q); Test_ottimalità(x,y); con yFS(x);
}
Algoritmo di Dijkstra (label setting)
![Page 14: Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi](https://reader030.fdocumenti.com/reader030/viewer/2022032606/56812ec5550346895d9464cf/html5/thumbnails/14.jpg)
79512
L’algoritmo di Dijkstra (label setting)
1
5
6
4
7
2
3
8
9
69
44
7
1
35
G=(N,A)
5
7
1
21
15
1128
940
10
21
0 Q
7
9
2 7
0
![Page 15: Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi](https://reader030.fdocumenti.com/reader030/viewer/2022032606/56812ec5550346895d9464cf/html5/thumbnails/15.jpg)
247
95
9
7
L’algoritmo di Dijkstra (label setting)
1
5
6
4
7
2
3
8
9
69
44
7
1
35
G=(N,A)
5
7
1
21
15
1128
940
10
21
0 Q
47
42
22
9
747
3 42
4 22
9
5 9
3 42
4 22
![Page 16: Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi](https://reader030.fdocumenti.com/reader030/viewer/2022032606/56812ec5550346895d9464cf/html5/thumbnails/16.jpg)
6478
47
9
7
1
5
6
4
7
2
3
8
9
69
44
7
1
35
G=(N,A)
5
7
1
21
15
1128
940
10
21
0 Q
42
22
9
9
3 42
4 22
5
47
78
93 42
22
6
47
78
L’algoritmo di Dijkstra (label setting)
![Page 17: Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi](https://reader030.fdocumenti.com/reader030/viewer/2022032606/56812ec5550346895d9464cf/html5/thumbnails/17.jpg)
4878
47
9
7
1
5
6
4
7
2
3
8
9
69
44
7
1
35
G=(N,A)
5
7
1
21
15
1128
940
10
21
0 Q
42
22
33
43
50
9
42
22
6
47
78
3
7 43
33
50
73 42
8 33
43
L’algoritmo di Dijkstra (label setting)
![Page 18: Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi](https://reader030.fdocumenti.com/reader030/viewer/2022032606/56812ec5550346895d9464cf/html5/thumbnails/18.jpg)
47
9
7
1
5
6
4
7
2
3
8
9
69
44
7
1
35
G=(N,A)
5
7
1
21
15
1128
940
10
21
0 Q
42
22
33
43
50
34
96
47
50
73 42
8 33
43
34
L’algoritmo di Dijkstra (label setting)
![Page 19: Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi](https://reader030.fdocumenti.com/reader030/viewer/2022032606/56812ec5550346895d9464cf/html5/thumbnails/19.jpg)
34
34
47
9
7
1
5
6
4
7
2
3
8
9
69
44
7
1
35
G=(N,A)
5
7
1
21
15
1128
940
10
21
0 Q
22
33
43
50
96
47
50
73
43
44
44
L’algoritmo di Dijkstra (label setting)
![Page 20: Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi](https://reader030.fdocumenti.com/reader030/viewer/2022032606/56812ec5550346895d9464cf/html5/thumbnails/20.jpg)
4344
44
349
7
1
5
6
4
7
2
3
8
9
69
44
7
1
35
G=(N,A)
5
7
1
21
15
1128
940
10
21
0 Q
22
3350
96 50
7 43
48
48
L’algoritmo di Dijkstra (label setting)
![Page 21: Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi](https://reader030.fdocumenti.com/reader030/viewer/2022032606/56812ec5550346895d9464cf/html5/thumbnails/21.jpg)
Il problema dei cammini minini
1
5
6
4
7
2
3
8
9
69
44
7
1
35
5
7
1
21
15
1128
940
10
21
T
![Page 22: Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi](https://reader030.fdocumenti.com/reader030/viewer/2022032606/56812ec5550346895d9464cf/html5/thumbnails/22.jpg)
Albero dei Cammini minimi albero di copertura minimo
1
2
3
5
7
6
0
5
7
4
10
11
15
SPT=22
![Page 23: Lezione n° 21: 25-26 Maggio 2009 Problema dell’albero dei cammini minimi](https://reader030.fdocumenti.com/reader030/viewer/2022032606/56812ec5550346895d9464cf/html5/thumbnails/23.jpg)
Albero dei Cammini minimi albero di copertura minimo
1
2
3
5
7
6
0
5
7
4
10
11
15
1
2
3
5
7
64
10
11
MST=21
SPT=22