Oggi ci chiediamo: come funziona il navigatore?

C’è chi (come me) si rifiuta di usarlo nella propria città (“La so girare anche bendato” mi sento già dire), chi invece lo accende per qualsiasi spostamento, anche di pochi chilometri, anche se un altro viaggiatore può indicare la strada. Oggi ci chiediamo come funziona il navigatore, croce e delizia dei viaggiatori.

Come funziona il navigatore? – Il GPS

Oggi non è più necessario acquistare un dispositivo dedicato al navigatore, essendo integrato negli smartphone, negli smartwatch o sugli autoveicoli. E tutti sappiamo bene o male come funziona la tecnologia di Global Positioning System, GPS, di stampo militare statunitense. Ma l’intento odierno è chiederci: come fa il segnale a sapere, per ogni singolo nostro spostamento, qual è il percorso più veloce?

La risposta alla domanda come funziona il navigatore? è: sfruttando l’algoritmo di Dijkstra. Venne sviluppato dall’informatico olandese Edser Dijkstra (Rotterdam, 1930 – Nuenen, 2002), in venti minuti davanti a una tazza di caffè dopo una mattinata di shopping ad Amsterdam con la fidanzata, nel 1956. Venne poi pubblicato nel 1959 ed è tutt’oggi utilizzato per lo sviluppo ottimale di reti idriche, telecomunicazioni, stradali etc.

Il navigatore mi ha fatto fare un giro assurdo!

Distinguiamo il percorso più veloce dal percorso più corto, questo per rispondere a tutte le volte in cui ci vediamo indicata una strada assurdamente lunga: è semplicemente il percorso più veloce perché più scorrevole, anche se meno corto! Ci sembra un giro assurdo quando siamo abituati ad un certo percorso, o perché la nostra mente ritiene più sensato un percorso più diretto… Ma forse più trafficato.

I grafi – Poche righe di teoria

L’algoritmo funziona sui grafi, strutture matematiche composte da archi e nodi: ciascun arco congiunge due nodi (chiamati estremi dell’arco). Gli archi possono avere un peso, ossia una sorta di valore di distanza tra i due estremi. Ancora, il grafo può essere orientato, ossia si può andare da un nodo A a un nodo B ma non viceversa.

Nelle reti stradali, gli archi sono le strade, i nodi gli indirizzi. Il peso di un arco è il tempo di percorrenza di quella strada. Se la strada è a senso unico, l’arco corrispondente sarà orientato.

Possiamo quindi vedere le nostre città come grafi con centinaia di archi e migliaia di nodi. L’algoritmo di Dijkstra viene applicato inizialmente dal nostro punto di partenza al punto di arrivo. Durante il movimento il nostro punto di partenza cambia continuamente: se cambiamo strada rispetto a quanto suggerito, l’algoritmo ricalcola il nuovo percorso più veloce.

Come funziona il navigatore? – Spiegazione dell’algoritmo

Supponiamo di voler partire da Via Accademia delle Scienze 6 (punto A) per arrivare in via Montebello 20 (punto B). Le vie possibili sono molte, e gli indirizzi decine e decine seppur l’area sia ridotta.

Il sistema integrato nel navigatore riduce il numero di possibili nodi attraverso cui lavorare, altrimenti dovrebbe calcolare il percorso minimo tra tutti i possibili miliardi di percorsi attorno al globo. Diciamo quindi che si riduca all’area nell’immagine, ossia ogni strada è un arco e ogni indirizzo è un nodo. Nell’esempio che seguirà, i nodi saranno solo gli incroci, e esporremo solo un certo numero di archi (strade).

Inizializzazione – Etichette

• Ad ogni nodo devono essere assegnate delle etichette: inizialmente tutti i nodi sono nell’insieme DaValutare; quando un nodo è valutato entra nell’insieme Valutati. All’inizio Valutati contiene solo A.
• A ciascun nodo viene assegnato il peso Potenziale dal nodo A di partenza, ossia la distanza minima da A. Il nodo A ha Potenziale nullo (ovviamente, dista zero da sé stesso); a tutti gli altri è assegnato Potenziale infinito.
• Per ciascun nodo viene annotato Precedente, ossia il nodo che lo precede nel cammino minimo.

Elaborazione

Ad ogni ciclo di elaborazione, l’algoritmo cerca nell’insieme DaValutare il nodo X con Potenziale minimo. Una volta trovato, aggiorna il suo Precedente, lo toglie dall’insieme DaValutare e lo inserisce in Valutati. Poi aggiorna i Potenziali dei suoi adiacenti sommando il peso da X al suo Potenziale (solo se inferiore). L’algoritmo procede finché non viene trovato un cammino tra A e B, e restituisce il percorso.

Non ho capito – Ecco un esempio

Riprendiamo il nostro esempio: vogliamo andare dal Museo Egizio di Torino alla Mole Antonelliana. Tra tutti i percorsi possibili consideriamo solo quelli indicati nel disegno. Il Potenziale(A) è pari a 0; i Potenziali di tutti gli altri nodi valgono infinito.

Passo 1. Valutati = {A}; Cercare gli adiacenti ad A (solo C):

• Potenziale(C) = Potenziale(A) + peso = 0+10 = 10; Precedente(C) = A.

Il nodo con Potenziale minore (unico) è C. Il cammino è A, C. Valutati = {A, C}

Passo 2. Cercare gli adiacenti a C:

• Potenziale(D) = 10+8 = 18; Precedente(D) = C;
• Potenziale(E) = 10+9 = 19; Precedente(E) = C.

Il nodo con Potenziale minore è D. Il cammino è A, C, D. Valutati = {A, C, D}

Passo 3. Cercare gli adiacenti a D:

• Potenziale(E) = 18+2 = 20, ma questo Potenziale è superiore al precedente, quindi non è aggiornato e Precedente(E) rimane C;
• Potenziale(F) = 18+4 = 22; Precedente(F) = D.

Il nodo con Potenziale minore è E, che ha come Precedente C.

Quindi il cammino è A, C, E. Valutati = {A, C, D, E}

Passo 4. Cercare gli adiacenti a E:

• Potenziale(F) = 20+1 = 21, questo Potenziale è inferiore al precedente, quindi viene aggiornato; Precedente(F) = E;
• Potenziale(G) = 20+4 = 24; Precedente(G) = E.

Il nodo con Potenziale minore è F. Il cammino è A, C, E, F. Valutati = {A, C, D, E, F}

Passo 5. Cercare gli adiacenti a F (solo G):

• Potenziale(G) = 21+2 = 23; Precedente(G) = F.

Il nodo con Potenziale minore (unico) è G. Il cammino è A, C, E, F, G. Valutati = {A, C, D, E, F, G}

Passo 6. Cercare gli adiacenti a G (solo B, per due vie):

• Potenziale(B) = 23+8 = 31; Precedente(B) = G;
• Potenziale(B) = 23+7 = 30; Precedente(B) = G.

Il nodo con Potenziale minore (unico) è B (di peso 7). Il cammino è A, C, E, F, G, B. Valutati = {A, C, D, E, F, G, B}

Il cammino minimo è A, C, E, F, G, B, con lunghezza 30.

Tecnologia GPS

Quando avviamo il navigatore per il nostro viaggio, esso calcola con questo algoritmo il cammino più breve: come abbiamo visto, il nodo D è alla fine scartato. Grazie alla tecnologia GPS il punto di partenza è costantemente aggiornato con il nostro movimento. Mano a mano che ci avviciniamo all’obiettivo, il peso totale si riduce, ossia il tempo e la distanza rimanente. Quando questi sono nulli, significa che abbiamo raggiunto la destinazione.

Come funziona il navigatore? – Il fascino della matematica

L’algoritmo di Dijkstra è stato pubblicato nel 1959 quando la tecnologia GPS era lontana dall’essere pensata, vi era solo in progettazione la tecnologia Transit. Esso venne pensato esclusivamente per amore della conoscenza e della sfida intellettiva, trovando, come spesso accade, molte applicazioni pratiche.