Come funziona l'algoritmo di Google Maps?

Google Maps usa l'algoritmo A* per trovare il percorso più breve e alterna i percorsi in tempo reale. L'algoritmo A* è una forma avanzata di Breadth first search, che evita il percorso costoso e sceglie il percorso più promettente. È un algoritmo molto intelligente. Viene usato per approssimare il percorso più breve in situazioni di vita reale, come nelle mappe e nei giochi dove ci possono essere molti ostacoli. E' formulato in termini di grafici ponderati, nel caso di Google Map questo peso è il tempo di viaggio. Partendo da un nodo specifico (nodo sorgente) di un grafo, costruisce un albero di percorsi partendo da quel nodo, espandendo i percorsi un passo alla volta, fino a quando uno dei suoi percorsi termina al nodo di destinazione predeterminato.

Ad ogni iterazione del suo ciclo principale, A* deve determinare quale dei suoi percorsi parziali espandere in uno o più percorsi più lunghi. Lo fa sulla base di una stima del costo (tempo totale impiegato) per raggiungere il nodo di destinazione. Nello specifico, A* seleziona il percorso che minimizza.

[math] f(n)=g(n)+h(n)[/math]

dove n è il nodo di destinazione sul percorso, g(n) è il costo del percorso dal nodo iniziale a n, e h(n) è un'euristica che stima il percorso più breve dalla sorgente alla destinazione. L'euristica è specifica del problema. In questo caso è il tempo impiegato per arrivare da qualche parte.