La matematica nella vita quotidiana: il navigatore satellitare

Il navigatore satellitare è sicuramente uno strumento di utilizzo molto comune, e spesso si suppone che il suo funzionamento sia semplicemente quello di ricevere informazioni dai satelliti che “indicano la strada”. In realtà la sua capacità di stabilire il percorso per raggiungere una qualsiasi destinazione è frutto di una combinazione di tecniche differenti, che riguardano la capacità di identificare con precisione il punto in cui ci troviamo in ogni istante, la disponibilità di mappe stradali accurate e aggiornate e, soprattutto, la capacità di calcolare il tragitto migliore per arrivare alla nostra meta. In questo articolo focalizzeremo la nostra attenzione su quest’ultimo punto, spiegando che alla base di questo calcolo c’è una ben precisa teoria matematica, la “teoria dei grafi” che ci permette di capire come sia possibile identificare il percorso più corto tra due punti. In pratica, vediamo come una astratta nozione scientifica diventi il fondamento di un oggetto pratico, reale e soprattutto utilissimo.

Innanzitutto, partiamo dal basso: cos’è un grafo?

In realtà, non è niente di più di un insieme di elementi collegati fra loro: ognuno degli elementi è detto “nodo”, ed i collegamenti sono detti “archi”. Un esempio di grafo è quello che ha come elementi una serie di città collegate tra loro attraverso la rete autostradale: in questo caso, i nodi sono le città e gli archi sono i segmenti autostradali fra le città stesse. Possiamo immaginare un grafo come una serie di palline o cerchi colorati (i nodi) collegati tra loro da linee (gli archi). Un arco può essere orientato o non orientato: un arco orientato è quello che consente il passaggio solo dal nodo di partenza a quello di arrivo (e non viceversa); un arco non orientato è quello che consente il passaggio in ambedue le direzioni. Nel nostro esempio del navigatore, una strada può essere considerata un arco orientato se è a senso unico, mentre può essere considerata un arco non orientato se è a doppio senso.

Un grafo si dice pesato se ad ogni arco viene associato un valore, detto appunto peso. Questo valore può essere, in generale, positivo o negativo. Rifacendoci all’esempio precedente delle città e delle autostrade, possiamo ottenere un grafo pesato associando a ciascun tratto autostradale la sua lunghezza in chilometri. In un grafo, è in teoria possibile andare da un nodo A ad un nodo B in più modi diversi, utilizzando archi differenti, proprio come nella realtà è possibile andare da una città all’altra utilizzando strade differenti. Chiameremo allora “cammino minimo” la “strada più corta” per collegare il nodo A al nodo B.

Per il nostro navigatore satellitare, trovare il  percorso tra il punto di partenza e il punto di arrivo equivale proprio a trovare il cammino minimo all’interno di un grafo. Nella teoria matematica dei grafi, il problema di calcolare il cammino minimo è stato studiato ed analizzato sotto ogni punto di vista, e sono molti gli algoritmi prodotti. Uno dei più utilizzati, ad esempio, è l’algoritmo di Dijkstra, ma ne esistono molti altri. E’ scelta quindi del costruttore di navigatori scegliere l’algoritmo che ritiene più appropriato. In questo scelta è sicuramente da considerare che la teoria alla base della ricerca del cammino minimo tra due nodi può essere molto complessa, soprattutto quando si tratta di effettuare il calcolo su mappe stradali molto articolate. Ad esempio, è stato sviluppato l’algoritmo A* che ricerca il cammino minimo utilizzando una “stima statistica” per ciascun nodo; parlando in “parole difficili”, tale stima rappresenta la valutazione aprioristica del vantaggio di passare per un nodo rispetto ad un altro nel percorso verso la destinazione finale. In ogni caso, entrare nel dettaglio degli algoritmi diventa alquanto complicato e presuppone conoscenze specifiche; speriamo in ogni caso di aver fornito una visione di base del problema e magari di aver stimolato l’interesse per una teoria matematica con molti risvolti pratici nella vita quotidiana.

di Giovanni Calcerano