Università degli studi di Padova 2008-2009
Tesi di laurea di primo livello
Ausilio didattico in Excel-Visual Basic per
il ricavo dei cammini di costo minimo
con l'algoritmo di Ford-Moore-Bellman
Laureando: Enrico Sperindio
Relatore: Prof. GIORGIO ROMANIN JACUR
Il problema dei cammini minimi su grafi
Tipici problemi di interesse
1.
2.
3.
Trovare il cammino minimo tra un nodo s detto sorgente ed un nodo t detto
destinazione
Per un assegnato nodo s , trovare il percorso più breve da s a tutti gli altri nodi
Trovare il cammino più breve tra tutte le coppie di nodi
Applicazioni
•
•
•
•
•
•
•
•
Pianificazione urbana del traffico
Rotta ottima per i trasporti su strada in presenza anche di congestioni
Protocolli di routing (OSPF, BGP, RIP)
Pipelining nei circuiti elettronici a larga scala di integrazione
Navigazione dei robot
Schedulazione degli operatori per il telemarketing
Gestione delle subroutine negli algoritmi di alto livello
Smistamento messaggi nelle telecomunicazioni
Una possibile soluzione
Una soluzione ammissibile al problema dei cammini minimi consiste nel
determinare n-1 cammini, uno per ogni coppia di nodi, ognuno dei quali ha
origine nel nodo r e giunge ad uno dei rimanenti nodi del grafo.
Sotto opportune ipotesi una soluzione ammissibile è una arborescenza di radice
r, e la soluzione cercata è una arborescenza di radice r di costo minimo.
Teorema di Bellman
Una soluzione ammissibile T è ottima se e solo se valgono le seguenti
condizioni per ogni arco (u,v):
l(v) = l(u) + c(u,v)
l(v) ≤ l(u) + c(u,v)
se (u,v) appartiene a T
se (u,v) non appartiene a T
Principio di ottimalità:
l*(v) = MIN { l*(u) + c(u,v) }
v
0
9
7
s
2
u
5
Ciò permette di definire algoritmi
basati sulla sostituzione degli archi
che violano tale principio
L’algoritmo di Ford-Bellman-Moore
• R. Bellman, On a routing problem, 1958.
• L. R. Ford, Jr. Network flow theory, 1956.
• E. F. Moore, The shortest path through a maze, 1959.
Q := {0}
l[v] := ∞ p[v] := 0
l[s] := 0 p[s] := s
EnQueue (s,Q)
while do
u := DeQueue (Q)
for each edge (u,v) do
if l[v] > l[u] + c(u,v) then
l[v] := l[u] + c(u,v)
l[v] := u
if v not in Q then
EnQueue (v,Q)
endif
endfor
endwhile
Per ogni nodo si ha un predecessore p(u) e la
miglior distanza attualmente trovata l(u)
Si appoggia ad una struttura Q che contiene
tutti i nodi i cui archi uscenti potrebbero
violare le condizioni di Bellman
1) Si estrae un nodo u da Q e si controlla se le
condizioni di ottimalità valgono per ciascun
arco della sua stella uscente.
2) Per ogni arco (u,v) che non soddisfa le
condizioni, si pone p[v]=u e l’etichetta di v
viene aggiornata.
3) Non si effettua però l’aggiornamento delle
etichette in tutti i nodi del sottoalbero di
radice v, ma si inserisce v in Q
La versione di Pape
•
•
•
•
Insieme Q implementato come
deque
L’inserimento di in avviene
secondo questa regola di natura
euristica:
 se è la prima volta che
viene inserito, esso deve
essere posto in coda alla
lista;
 se invece era già stato
inserito in precedenza,
allora si pone all’inizio della
lista stessa.
Idea di sfruttare subito il
miglioramento dell’etichetta
Prestazioni migliori solo su grafi
sparsi
[inizializzazione]
EnQueue (s,Q)
while do
u := DeQueue(Q)
for each edge (u,v) do
if l[v] > l[u] + c(u,v) then
if v not in Q then
if D[v] = ∞ then
EnQueueB(v; Q)
else
EnQueueF(v; Q)
endif
endif
l[v] := l[u] + c(u,v)
p[v] := u
endif
endfor
endwhile
L’implementazione in Excel
L’implementazione in Excel
Algoritmo
Strutture dati
n  numero nodi
e  numero archi
s  nodo sorgente
Edges  vettore archi
dist  lista delle lunghezze del miglior cammino
da s a v correntemente trovato
pred  lista dei predecessori
inList  flag che indica se un nodo è
attualmente nella lista
nEstr  vettore che indica per ogni nodo quante
volte è stato estratto
Q  lista dei nodi da esaminare
Esempio
Esempio
Q = {s}
Si esaminano gli archi uscenti da s
Si aggiornano le etichette di a e c
Q = {a,c}
Esempio
Q = {a,c}
Si esaminano gli archi uscenti da a
Si aggiornano le etichette di b e d
Q = {c,b,d}
Esempio
Q = {c,b,d}
Si esaminano gli archi uscenti da c
Non si aggiornano etichette
Q = {b,d}
Esempio
Q = {b,d}
Si esaminano gli archi uscenti da b
Si aggiorna l’etichetta di c
Inserisco c in testa in quanto già inserito in precedenza
Q = {c,d}
Esempio
Q = {c,d}
Si esaminano gli archi uscenti da c
Non si aggiornano etichette
Q = {d}
Esempio
Q = {d}
Si esaminano gli archi uscenti da d
Non si aggiornano etichette
Q = { }  Termine algoritmo
Esempio
Arborescenza di radice s dei cammini minimi
Esempio
In caso di ciclo negativo
•
•
•
Soluzione infinitamente
migliorabile
Algoritmo deve terminare
Presenza di tale ciclo indicata con
un messaggio di errore