Lezione n°22

(1)

Lezione n

°

22

Problema dell’albero dei cammini minimi

Lezioni di Ricerca Operativa

Corso di Laurea in Informatica ed Informatica Applicata Università di Salerno

(2)

Il problema dei cammini minimi

1 5 6 4 7 2 3 8 9 69 44 7 1 35

G=(N,A)

5 7 1 21 15 sorgente 11 28 9 40 10 21 destinazione

p

[Versione uno a uno]

Sia G = (N,A) un grafo orientato su cui sia definito un vettore c = [c_ij] dei costi associati agli archi del grafo; inoltre, siano s e t due nodi distinti, detti rispettivamente origine e destinazione. Il problema dei cammini minimi 1 a 1 consiste nel determinare il percorso di costo minimo (più corto) da s a t in G.

(3)

1 5 6 4 7 2 3 8 9 69 44 7 1 35

G=(N,A)

5 7 1 21 15 sorgente 11 28 9 40 10 21

c

_ij= costo dell’arco (i,j)

x

_ij= variabili decisionali

x

_ij

=

1 se x

ij

Î

p

0 se x

_ij

Ï

p

destinazione

p

(4)

1 5 6 4 7 2 3 8 9 69 44 7 1 35 5 7 1 21 15 11 28 9 40 10 21

(5)

1 5 6 4 7 2 3 8 9 69 44 7 1 35 5 7 1 21 15 11 28 9 40 10 21

(6)

1 5 6 4 7 2 3 8 9 69 44 7 1 35 5 7 1 21 15 11 28 9 40 10 21

(7)

Il problema dei cammini minimi

(varianti)

Ø

Uno ad uno

Ø

Uno a tutti

Ø

Tutti a tutti

(8)

Il problema dei cammini minimi (uno a tutti)

1 5 6 4 7 2 3 8 9 69 44 7 1 35 5 7 1 21 15 sorgente 11 28 9 40 10 21

T

G=(N,A)

Qual’è il modello matematico per la versione uno a tutti?

[Versione uno a tutti]

Sia G = (N,A) un grafo orientato su cui sia definito un vettore c = [c_ij] dei costi associati agli archi del grafo; inoltre, siano s il nodo origine. Il problema dei cammini minimi 1 a tutti consiste nel determinare l’albero dei cammini minimi da s a tutti gli altri nodi di G.

(9)

1 5 6 4 7 2 3 8 9 69 44 7 1 35 5 7 1 21 15 11 28 9 40 10 21

T

}

0 {

È

Î

_Z

+

x

_ij

(10)

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 11 28 9 40 10 21 d₁ _d₂ _d₉ d₅ d₆ d₇ d₈ d₃ d₄

(11)

Algoritmo prototipo

Passo 1:

Inizializzazione

.

d

_s

=0, P

_s

=NULL, d

_k

=¥, P

_k

=s "k

Î

N\{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):

"

_y

Î

_{FS(x) se}

_d

_x

_{+ c}

_xy

_{< d}

_y

_allora

d

_y

= d

_x

+ c

_xy

, P

_y

= x e se y ÏQ inseriscilo in

Q

(Q= Q

È

_{{y}) (}

_Relaxing

₎

(12)

Aggioramento delle etichette

5 9 4 7 2 34 15 42 67 18 21 "_{yÎFS(x) se}_d_x _{+ c}_xy _{< d}_y _{allora d}_y _{= d}_x _{+ c}_xy _{e P}_y_{= x} Ø x=4, y=5 d₄ + c₄₅ < d₅? d₅ = d₄ + c₄₅ e P₅= 4 Ø x=4, y=2 d₄ + c₄₂ < d₂? ……… Ø x=4, y=9 d₄ + c₄₉ < d₉? d₉ = d₄ + c₄₉ e P₉= 4 36 55

(13)

Algoritmo prototipo

Passo 1:

Inizializzazione

.

d

_s

=0, P

_s

=NULL, d

_k

=¥, P

_k

=s "k

Î

N\{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):

"

_y

Î

_{FS(x) se}

_d

_x

_{+ c}

_xy

_{< d}

_y

_allora

d

_y

= d

_x

+ c

_xy

, P

_y

= x e se y ÏQ inseriscilo

in Q

(Q= Q

È

_{{y}) (}

_Relaxing

₎

(14)

Differenti implementazioni

Gli algoritmi per l’SPT si distinguono per:

- La politica di estrazione del nodo da

Q

(label setting e label correcting)

(15)

Label Correcting

Algoritmi label correcting [Bellman-Ford]:

- I nodi vengono estratti dalla coda Q in ordine FIFO (è una delle possibili implementazioni dell’algoritmo)

- Le etichette dei nodi sono temporanee per tutta la durata della computazione. Solo al termine dell’algoritmo tali

etichette rappresenteranno le distanze minime.

- L’algoritmo è in grado di risolvere il problema dei cammini minimi su un qualsiasi grafo che non presenta cicli di peso negativo.

(16)

Label Setting

Algoritmi label setting [Dijkstra]:

- Ad ogni iterazione viene estratto dalla coda Q il nodo x con etichetta minima.

- L’etichetta del nodo x estratto rappresenta la distanza minima dalla sorgente al nodo stesso. Tale etichetta viene fissata in modo permanente e non viene più aggiornata

(quindi una volta estratto un nodo non può essere reinserito in Q).

- Gli algoritmi label setting sono più efficienti dei label

correcting, ma possono essere applicati solo su grafi dove c_ij≥0.

(17)

Algoritmo di Dijkstra (label setting)

Dijkstra (G,s)

Inizializzazione;

( ds=0, Ps=NULL, dk=¥, Pk=s "kÎN\{s} , Q={s})

while ( Q ¹ Æ){

x = Extract_min(Q);

Relax(x,y); con yÎFS(x);

}

(18)

79

512

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 11 28 9 40 10 21 0 ¥ ¥

Q

¥ ¥ ¥ ¥ ¥ ¥ 7 9 2 7 0 1 1 1

(19)

2 47 9 5 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 11 28 9 40 10 21 0 ¥

Q

¥ ¥ ¥ ¥ ¥ 47 42 22 9 7 47 3 42 4 22 9 5 9 3 42 4 22 1 1 2 2 2 2 2 2 1

(20)

64 78 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 11 28 9 40 10 21 0

Q

¥ ¥ ¥ 42 22 9 9 3 42 4 22 5 47 78 9 3 42 22 6 47 78

L’algoritmo di Dijkstra (label setting)

2 2 2 15 5 2 2 2

(21)

48 78 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 11 28 9 40 10 21 0

Q

¥ ¥ 42 22 33 43 50 9 42 22 6 47 78 3 7 43 33 50 7 3 42 8 33 43

L’algoritmo di Dijkstra (label setting)

5 2 2 24 4 4 4 2 4

(22)

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 11 28 9 40 10 21 0

Q

42 22 33 43 50 34 9 6 47 50 7 3 42 8 33 43 34

L’algoritmo di Dijkstra (label setting)

2 4 4 2 4 8

(23)

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 11 28 9 40 10 21 0

Q

22 33 43 50 9 6 47 50 7 3 43 44 44

L’algoritmo di Dijkstra (label setting)

2

4 4 8

(24)

43 44 44 34 9 7 1 5 6 4 7 2 3 8 9 69 44 7 1 35

G=(N,A)

5 7 1 21 15 11 28 9 40 10 21 0

Q

22 33 50 9 6 50 7 43 48 48

L’algoritmo di Dijkstra (label setting)

4 4

3

(25)

Il problema dei cammini minimi

1 5 6 4 7 2 3 8 9 s

……….

Quali sono i valori delle variabili x_ij nella soluzione ottima?

}

0 {

È

Î

_Z

+

x

_ij