Martedì, 24 Settembre 2019 14:17

Il celebre algoritmo che ha consentito la navigazione su Google Maps

a91b0ae51d3acabb3d726ca38457647b MGoogle Maps è stata ed è senza dubbio una delle più famose applicazioni geospaziali di sempre, avendo trasformato il modo in cui navighiamo utilizzando una mappa digitale per andare dal punto A al punto B. Prima di Google Maps la maggior parte delle persone utilizzava le mappe di carta per navigare e poi ha cominciato ad usare le mappe digitali.

Google maps comunque non è stato il primo sistema a dare queste possibilità, basta ricordare Tom Tom e gli altri navigatori, ma certamente ha contribuito a rendere la navigazione con mappe digitali una cosa oggi considerabile tradizionale.

La mappa digitale ha mostrato subito di avere diversi vantaggi rispetto all'equivalente di stampa - diversi livelli di zoom, possibilità di aggiungere i propri punti di interesse, ecc, ma forse la caratteristica più interessante è stata la possibilità di utilizzare il computer (o lo smartphone) per calcolare la distanza più breve dal punto A al punto B senza bisogno di capirlo da soli o chiedere a qualcuno che ha vissuto nel posto abbastanza a lungo per derivarlo dall'esperienza.

L'algoritmo che ha reso possibile tutto ciò si è basato su molti studi precedenti, riferibili alla Teoria dei Grafi che da molti anni studia questioni poi riprese dall'algoritmo iniziale di navigazione attribuito a Edsger W. Dijkstra. Basta pensare ai concetti di Maximal or Minimal Spanning Tree, che nella Teoria dei Grafi individuano rispettivamente i percorsi più lunghi o quelli più corti per portarsi da un nodo A a un nodo B di un Grafo.

Dijkstra Animation1

Il lavoro del Dr. Dana Tomlin nei primi anni '80 dal titolo "Map Algebra" ha aperto la strada al GIS per diventare la potente applicazione che è oggi. Allo stesso modo, è stato il lavoro di Edsger W. Dijkstra sull'algoritmo per il percorso più breve che alla fine porta il suo nome - l'algoritmo di Dijkstra - che ha reso possibile la navigazione.

Il nucleo di questo algoritmo è quello che alimenta ancora oggi le funzionalità per navigare sulle Google Maps, sulle mappe di Apple, Here, OpenStreetMap e sicuramente qualsiasi altra mappa digitale. Ovviamente con le dovute variazioni e ottimizzazioni occorse nel tempo, ma di sicuro tutte riferite all'algoritmo iniziale di Dijkstra, che all'epoca risolse il problema di trovare il percorso più breve ed efficiente possibile tra due nodi di una rete strutturata a grafo. Basti ricordare che Teleatlas, iniziale innovatore del settore oggi acquisita da TomTom, chiamava Grafo Stradale la sua rete digitale di strade rilevate all'inizio in tutta Europa.

Lo studio originale di Dijkstra che ha più di 50 anni è qui:

http://www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.pdf 

Riferimenti di questa nota sono derivati da:

http://geoawesomeness.com/the-famous-algorithm-that-made-navigation-in-google-maps-a-reality/ 

06 Luglio 2015  Autore :  Renzo Carlucci - Short Link : www.geoforall.it/k38cc  

© 2019 HSH Informatica & Cultura. All Rights Reserved.