Università degli Studi di Pisa

Valerio Cutini

insegnamento di

Tecnica Urbanistica• Corso di laurea triennale in Ing. Edile

Ingegneria del Territorio• Corso di laurea magistrale

in Ing. Idraulica,Trasporti e Territorio

Lezione n° 3. Lezione n° 3. Gli algoritmi del minimo Gli algoritmi del minimo

percorsopercorso

a.a. 2013 / 2014

valerio cutini

a.a. 2013-2014a.a. 2013-2014

Il problema della determinazione del più breve percorso fra due punti di un sistema insediativo è fondamentale nella modellistica territoriale

Il problema del minimo percorso

Al fine di evitare che si operi per tentativi, sono stati introdotti metodi rigorosi per risolvere la questioneTali metodi hanno una logica iterativa, ed hanno in comune alcune caratteristiche:

sono oggettivi e ripetibiliforniscono i risultati nel minor numero possibile di passaggiogni singolo passaggio è determinato univocamente dal precedente e determina univocamente il successivoogni singolo passaggio determina un avvicinamento alla soluzione del problema

valerio cutini

a.a. 2013-2014a.a. 2013-2014

I metodi per la determinazione del più breve percorso fra due punti di un sistema insediativo sono detti algoritmi del minimo percorso (shortest path algorithms)

Il problema del minimo percorso

Le loro caratteristiche di iteratività li rendono agevolmente applicabili mediante software specificiPer la comprensione del loro funzionamento, è utile schematizzare un sistema insediativo mediante l’uso di grafi

valerio cutini

a.a. 2013-2014a.a. 2013-2014

I grafi sono un metodo di rappresentazione di un sistema, particolarmente utile ad evidenziare le relazioni fra i suoi singoli elementi

I grafi

Un grafo è composto da nodi e da archiun nodo (node, vertex) rappresenta un punto dello spazioun arco (edge, line) rappresenta la relazione di collegamento diretto (se esitente) fra due nodi

valerio cutini

a.a. 2013-2014a.a. 2013-2014

I grafi

1 2 3

4 5

67

8

9

10

11

12

13

14

i/j 1 2 3 4 5 6 7 8 910

11

12

13

14

1 0 - - 3 - - - - - - - - - -

2 - 0 3 2 - - - - - - - - - -

3 - 3 0 - 2 - - - - - - - - -

4 3 2 - 0 2 - - - - - - - - -

5 - - 2 2 0 4 - - - - - - - -

6 - - - - 4 0 1 - - 1 5 3 - -

7 - - - - - 1 0 - - - - - - -

8 - - - - - - - 0 2 1 - - - -

9 - - - - - - - 2 0 - - - - -

10

- - - - - 1 - 1 - 0 - - - -

11

- - - - - 5 - - - - 0 - - -

12

- - - - - 3 - - - - - 0 2 2

13

- - - - - - - - - - - 2 0 -

14

- - - - - - - - - - - 2 - 0

3 m

2 m 2 m 3 m

4 m

2 m

2 m

5 m

2 m

1 m

1 m

1 m

2 m

3 m

valerio cutini

a.a. 2013-2014a.a. 2013-2014

Un grafo si dice connesso se per ogni coppia di nodi (v, w) c’è un percorso che li unisce

I grafi

Un grafo si dice orientato se la relazione di connessione non è simmetrica, ovvero se esiste almeno una coppia di nodi (v,w) tali che il percorso che li unisce P (v, w) ≠ P (w, v) In un grafo, i singoli nodi possono essere nodi di origine (source vertices) o di destinazione (sink vertices) di percorsiNegli algoritmi del minimo percorso, utilizzeremo grafi connessi e non orientati

valerio cutini

a.a. 2013-2014a.a. 2013-2014

Due qualità sono richieste ad un algoritmo del minimo percorso

Gli algoritmi del minimo percorso

Queste due qualità raramente coesistono

fornire risultati completi ed esaustivi fornire risultati con il minor numero di passaggi

esistono metodi speditivi, ma chhe forniscono risultati parziali ed incompletiesistono metodi che forniscono risultati esaustivi, a prezzo di un elevato numero di passaggi

In particolare, gli SPA si dividono in due famigliequelli che determinano il percorso più breve da

un nodo a tutti gli altri (single-source)quelli che determinano il percorso più breve fra tutte le possibili coppie di nodi (all pairs)

valerio cutini

a.a. 2013-2014a.a. 2013-2014

L’algoritmo di Dijkstra è il più noto e usato degli algoritmi che determinano il minimo percorso da un unico nodo i, assunto come origine

Gli algoritmi single-source:l’algoritmo di Dijkstra

E.W. Dijkstra

valerio cutini

a.a. 2013-2014a.a. 2013-2014

Gli algoritmi single-source:l’algoritmo di Dijkstra

La logica dei passaggi dell’algoritmo è la seguente: Si assegna per ogni dij un valore di tentativo,

ponendo:

Fra tutti i collegamenti dij, si individua il minimo valore dik, e lo si trasforma in valore definitivo

per i=j, dij = 0per i≠j, se esiste un collegamento diretto l0, dij = l0per i≠j, se non esiste un collegamento diretto, dij = ∞

se dik+dkj < dijk-1

, dijk =

dik+dkj se dik+dkj ≥ dijk-1

, dijk =

dijk-1

Si assume il nodo k come nodo perno (pivot) e lo si interpone in tutti i collegamenti dij, sostituendo il valore della misura risultante, nel caso sia minore della precedente. Ovvero:

Si procede, fino a che tutti i valori dei collegamenti non sono diventati definitivi

valerio cutini

a.a. 2013-2014a.a. 2013-2014

L’algoritmo di Floyd è il più noto e usato degli algoritmi che determinano il minimo percorso di connessione fra tutte le possibili coppie i, j di nodi di un grafo

Gli algoritmi all-pairs:l’algoritmo di Floyd

Robert W. Floyd

valerio cutini

a.a. 2013-2014a.a. 2013-2014

Gli algoritmi all-pairs:l’algoritmo di Floyd

La logica dei passaggi dell’algoritmo è la seguente: Si costruisce la matrice dei collegamenti dij,

ponendo:

Alla k-esima iterazione, si interpone il nodo k fra i e j, sostituendo il valore della misura risultante, nel caso sia più breve della precedente. Ovvero:

per i=j, dij = 0per i≠j, se esiste un collegamento diretto l0, dij = l0per i≠j, se non esiste un collegamento diretto, dij = ∞

se dik+dkj < dijk-1

, dijk =

dik+dkj se dik+dkj ≥ dijk-1

, dijk =

dijk-1Si procede per n iterazioni (n matrici), fino a che

tutti i nodi k non sono stati interposti