Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Paola Festa » 21.Problemi di Cammino Minimo


Problemi di Cammino Minimo, 1

Individuare un cammino connettente due o più nodi di un grafo è un problema che compare come sottoproblema di molti altri problemi di ottimizzazione discreta ed ha, inoltre, numerosissime applicazioni nel mondo reale.

Si pensi, ad esempio, al problema di individuare un percorso tra due località riportate in una cartina stradale, in cui i vertici sono le località, mentre gli archi sono le strade che le collegano.
In tal caso, ad ogni arco è associato un costo che può essere la lunghezza in chilometri della strada o il tempo medio necessario per percorrerla (in quest’ultimo caso, dipendente dal traffico).

Se invece di un percorso qualunque, si vuole individuarne uno di costo totale minimo, allora il problema risultante è noto come problema del cammino minimo in un grafo.

Nel seguito si supporrà il caso più generale in cui il grafo istanza del problema sia orientato, per cui il costo di collegamento tra due nodi dipende dalla direzione del percorso.
Si noti che il caso di grafo orientato è più generale, dato che un grafo non orientato può sempre essere trasformato
in un grafo orientato.

Problemi di Cammino Minimo, 2

Sia

→ G=(V,A) un grafo orientato, |V|=n, |A|=m;
c_{ij}\in {\mathbb R} il costo associato all’arco (i,j), per ogni (i,j) in A;
P=\{v_1,v_2,\ldots,v_k\} un cammino che collega v_1 a v_{k} visitando in sequenza i nodi intermedi v_2,v_3,\ldots,v_{k-1} ed ha costo (lunghezza) totale pari a
\displaystyle{c(P)=\sum_{i=1}^{k-1} c_{v_i\,v_{i+1}}}.
Un cammino P che collega il nodo v_1 al nodo v_k è detto minimo se non esiste in G un cammino alternativo di costo totale inferiore a c(P).

Tipicamente, si può essere interessati ad individuare in G

  1. un cammino P di costo minimo da un nodo sorgente s in V ad un nodo destinazione d in V;
  2. n-1 cammini minimi da nodo sorgente s in V ai restanti nodi di G.

Il problema 1. è noto come problema di cammino minimo singola origine – singola destinazione (SPP – Shortest Path Problem).
Il problema 2. è noto come problema dell’albero dei cammini minimi (SPT – Shortest Path Tree Problem).

Problemi di Cammino Minimo, 3

I problemi 1. e 2. ammettono soluzione se

  • in G non esiste un cammino P che inizia da (o passa per) il nodo origine s e che contiene un ciclo di costo negativo;
  • G è fortemente connesso: quest’ipotesi non è restrittiva, in quanto è sempre possibile definire pari a +\infty la distanza fra nodi non connessi;
  • c_{ij}\in {\mathbb Z},\ \forall (i,j)\in A : quest’ipotesi non è restrittiva, in quanto è sempre possibile convertire numeri razionali in numeri interi moltiplicandoli per un numero grande opportunamente scelto.

SPP, 1

Si definiscano m variabili di decisione binarie con il seguente significato:
\[ \forall\ \ (i,j)\in A,\ \ \ x_{ij}=\left\{ \begin{array}{lll} 1,   & \mbox{{\rm se }} (i,j)\in P; \\ 0,   & \mbox{{\rm altrimenti.}} \end{array} \right . \]

L’obiettivo è minimizzare il costo totale del percorso P e cioè

\[ \min\ \displaystyle{\sum_{(i,j)\in A}c_{ij}x_{ij}}. \]

Per definire i vincoli del problema, occorre imporre la semplicità del percorso soluzione P.

SPP, 2

A questo punto, si hanno tutti gli elementi per descrivere formalmente il problema SPP da un nodo s ad un nodo d diverso da s di un grafo orientato G=(V,A):

\[  \begin{array}{llll}  \mbox{(SPP)} & \min & \displaystyle{\sum_{(i,j)\in A} c_{ij}x_{ij}}\\ & \mbox{{\rm s.a}} \\ &     & \forall\ i\in V,\ \ \ \displaystyle{\sum_{j\in FS(i)}x_{ij}-\sum_{j\in BS(i)}x_{ji}}=\left\{ \begin{array}{rll} 1,   & \mbox{{\rm se }} i=s; \\    -1,   & \mbox{{\rm se }} i=d; \\   0 ,  & \mbox{{\rm altrimenti.}} \end{array}   \right .\\ \\ &  & x_{ij}\in\{0,1\},\ \forall\ (i,j)\in A.       \end{array} \]

Nota: la matrice dei vincoli tecnologici è la matrice di incidenza nodo-arco di G ed è unimodulare. Dunque, qualunque soluzione ammissibile del rilassamento continuo avrà componenti intere.

SPT

Con analoghi ragionamenti si giunge alla descrizione matematica del problema SPT da un nodo s ai restanti nodi di un grafo orientato G=(V,A):

\[  \begin{array}{llll} \mbox{(SPT)} & \min & \displaystyle{\sum_{(i,j)\in A} c_{ij}x_{ij}}\\ & \mbox{{\rm s.a}} \\   &     & \forall\ i\in V,\ \ \ \displaystyle{\sum_{j\in FS(i)}x_{ij}-\sum_{j\in BS(i)}x_{ji}}=\left\{ \begin{array}{ll} n-1,   & \mbox{{\rm se }} i=s; \\   -1, & \mbox{{\rm altrimenti.}} \end{array}   \right .\\ \\ &  & x_{ij}\in\{0,1\},\ \forall\ (i,j)\in A. \end{array} \]

Nota: la matrice dei vincoli tecnologici è la matrice di incidenza nodo-arco di G ed è unimodulare. Dunque, qualunque soluzione ammissibile del rilassamento continuo avrà componenti intere.

Algoritmo di Dijkstra, 1

L’algoritmo di Dijkstra risolve il problema SPP ed il problema SPT in un grafo G=(V,A), tale che c_{ij}\geq 0,\ \forall (i,j)\in A (G non può contenere cicli di costo negativo).

In quanto segue faremo riferimento al problema SPT.
Gli n-1 cammini minimi da s sono memorizzati in un’arborescenza realizzata attraverso l’uso dell’array dei predecessori p[n], definito come segue:

\[ \forall\ i=1,2,\ldots,n,\ \ p_j=\left\{ \begin{array}{lll} 0,   & \mbox{{\rm se $j$ non \`e visitato da $P$};} \\ s,   & \mbox{{\rm se $j=s$};} \\ i,   & \mbox{{\rm se $i$ \`e visitato da $P$ immediatamente prima di $j$.}} \end{array} \right . \]

Algoritmo di Dijkstra, 2

Teorema. Sia G=(V,A) un grafo orientato. Sia S un sottoinsieme proprio di V, s in S e per ogni i in S, sia L[i] il costo del cammino minimo da s ad i (L[s]=0).
Sia, inoltre,
\[ (v,h)=\mbox{argmin}\ \{L[i]+c_{ij}\ \vert\ (i,j)\in \delta_G^+(S)\}. \]
Se c_{ij}\geq 0, \forall (i,j)\in A , allora L[v]+c_{vh}=L[h] .

Dimostrazione. Per dimostrare che L[v]+c_{vh} è il costo di un cammino minimo da s ad h, occorre
verificare che ogni altro percorso alternativo P non ha costo minore.

Algoritmo di Dijkstra, 2

Sia (i,j)\in \delta_G^+(S),\ (i,j)\not=(v,h) , e si partizioni il percorso P in P_1\cup\{(i,j)\}\cup P_2 , come mostrato in Figura.

E’ evidente che
\[ \begin{array}{lcll} c(P) &\stackrel{\mbox{def.}}{=}& \displaystyle{\sum_{(u,w)\in P}c_{uw}}\ =\ c(P_1)+c_{ij}+c(P_2) \\ \\ &\stackrel{c(P_1)\geq L[i]}{\geq} & L[i]+c_{ij}+c(P_2)\stackrel{c(P_2)\geq 0}{\geq} L[i]+c_{ij} \\ \\ & \geq & L[v]+c_{vh}. \end{array}\]

Percorso P dal nodo s al nodo v. Disegnata da Paola Festa

Percorso P dal nodo s al nodo v. Disegnata da Paola Festa


I materiali di supporto della lezione

D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008.

M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova, 1999.

S. Martello, Fondamenti di Ricerca Operativa L-A, Bologna, Società Editrice Esculapio, 2004.

S. Martello, Ricerca Operativa LS, Bologna, Società Editrice Esculapio, 2004.

Dispense del Corso di Ricerca Operativa presso l'Università degli Studi di Pisa.

Dispense ed Appunti del Corso prodotte da Paola Festa.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion