Como funciona o algoritmo do Google Maps?

Google Maps utiliza o algoritmo A* para encontrar o caminho mais curto e alternar os percursos em tempo real. O algoritmo A* é uma forma avançada de primeira busca do Breadth. Ele evita o caminho mais caro e escolhe o caminho mais promissor. É um algoritmo muito inteligente. Ele é usado aproximadamente o caminho mais curto em situações da vida real, como em mapas, jogos onde pode haver muitos obstáculos. É formulado em termos de gráficos ponderados no caso do google map este peso é o tempo de viagem. A partir de um nó específico (nó fonte) de um gráfico, ele constrói uma árvore de caminhos a partir desse nó, expandindo caminhos um passo de cada vez, até um de seus caminhos terminar no nó de destino pré-determinado.

A cada iteração de seu loop principal, A* precisa determinar quais de seus caminhos parciais se expandem em um ou mais caminhos mais longos. Ele o faz com base em uma estimativa do custo (tempo total) ainda a ir para o nó de destino. Especificamente, A* seleciona o caminho que minimiza.

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

onde n é o nó de destino no caminho, g(n) é o custo do caminho do nó inicial para n, e h(n) é um heurístico que estima o caminho mais curto da origem até o destino. A heurística é específica do problema. Neste caso, é o tempo necessário para chegar a algum lugar.