Como o Waze Funciona? Como Calcular o Melhor Caminho?

Nesta aula quero mostrar como o Waze funciona! Como ele te leva do ponto A ao ponto B tão rápido? Aprenda hoje!

Caso prefira esse conteúdo no formato de vídeo-aula, assista ao vídeo abaixo ou acesse o nosso canal do YouTube!

O que você aprende neste vídeo

Resposta rápida: A aula explica a lógica por trás do Waze, e não o código dele, que não é aberto: o tempo de outros usuários em cada trecho, o desafio das infinitas rotas possíveis e o passo a passo do algoritmo A estrela, que usa uma estimativa até o destino para deixar de lado caminhos improváveis.

Neste vídeo (18 min):

  • 1:32 - O Waze usa o tempo de outros usuários em cada rua para estimar cada trecho
  • 2:44 - Os dois desafios das infinitas possibilidades: achar o melhor caminho e achar rápido
  • 3:24 - Entra o algoritmo A estrela, uma variação do que o Waze usa, segundo a aula
  • 4:35 - Passo a passo no desenho: a cada passo entra o ponto de menor tempo a partir dos já analisados
  • 7:28 - Quantos pontos puderam ser ignorados sem calcular todas as possibilidades
  • 9:26 - A estimativa do A estrela, como a distância em linha reta até o destino
  • 11:08 - Prioridade para os pontos que tendem a estar mais perto do destino
  • 12:40 - A nova conta: tempo já conhecido mais a estimativa até o destino
  • 14:14 - Exemplo numérico: o caminho por C, com estimativa de 6 minutos, vence os de 8 e 11 minutos
  • 16:26 - Qual linguagem de programação usar, e o Python na ciência de dados

Trechos do vídeo:

  • A lógica mostrada na aula é a que está por trás do Waze, segundo o instrutor. O código detalhado linha por linha não é aberto ao público.
  • O ganho do algoritmo é não precisar analisar todas as possibilidades: com infinitos caminhos possíveis, o objetivo é reduzir a quantidade a analisar até ela ficar manuseável.
  • No A estrela, a estimativa pode ser simplesmente a distância em linha reta até o destino, ignorando as ruas no meio do caminho. Ela indica quais trajetos provavelmente levam ao destino de forma mais rápida.
  • O A estrela troca a certeza de achar o melhor dos melhores caminhos pelo melhor caminho possível em pouco tempo. Segundo a aula, na grande maioria dos casos ele ainda encontra o melhor caminho.
  • Um ponto que fica para trás e tem distância até o destino muito maior que a do ponto de partida até o destino muito provavelmente acaba ignorado.

Nesta aula quero mostrar como funciona o algoritmo do Waze! Como ele te leva do ponto A ao ponto B tão rápido? Aprenda hoje!

Você conhece o Waze? É um app muito usado, ele serve basicamente para calcular trajetos e mostra como ir do ponto A ao ponto B da maneira mais rápida.

O aplicativo faz a mudança de trajeto em menos de um minuto mesmo que o trajeto seja muito longo.

Nós vamos explicar nesta aula a lógica usada pelo aplicativo para encontrar o trajeto.

O algoritmo detalhado linha por linha de código não é aberto ao público e não é o objetivo desta aula. Nosso objetivo é entender a lógica usada.

Como o Waze funciona?

Imagine que estamos querendo ir de um ponto A até um ponto B, por exemplo.

Rota simples.
Rota simples.

Se existisse somente um caminho possível para este trajeto seria muito fácil fazer esta previsão, porque seria apenas uma questão de calcular o tempo médio que os usuários levam para fazer o trajeto.

Mas o que acontece normalmente é existirem muitas opções de rotas que levam para o mesmo lugar.

Como o Waze Funciona
Rota simples 2.

Como fazer a previsão considerando todas essas rotas?

Como o Waze Funciona
Rota simples – tempo.

A forma mais simples de fazer isso é obtendo uma projeção do tempo que se leva para completar cada um desses percursos.

O Waze teria que obter a partir do trajeto dos outros usuários um tempo médio estimado para cada um dos trajetos.

Ícone PythonPython Impressionador

Você vai aprender a linguagem de Programação que mais cresce no Mundo para fazer automações incríveis, desenvolver sites, fazer análises de dados, trabalhar com Ciência de Dados, Inteligência Artificial, mesmo que você nunca tenha tido nenhum contato com Programação na vida.

Black Friday · Lote Especial · Lote 1 · Último Lote

De R$ 1.497 56% OFF54% OFF53% OFF

por 12x R$ 6467,5069

Preço do Lote Especial por tempo limitadoPreço do Lote Especial só até amanhã, 13/11, às 23h59Preço do Lote Especial até 13/11, às 23h59Último dia do Lote Especial: o preço vale até hoje, às 23h59Preço do Lote 1 por tempo limitadoPreço do Lote 1 só até amanhã, 20/11, às 23h59Preço do Lote 1 até 20/11, às 23h59Último dia do Lote 1: o preço vale até hoje, às 23h59Preço do Último Lote por tempo limitadoPreço do Último Lote só até amanhã, 27/11, às 23h59Preço do Último Lote até 27/11, às 23h59Último dia do Último Lote: o preço vale até hoje, às 23h59

Começar agoraQuero a oferta de Black FridaySeta para a direita
Fundo PythonTelas Python
Luz Python

Assim ele consegue somar os tempos das rotas que levam ao destino que o usuário inseriu e mostrar a mais rápida.

Isso seria ótimo, mas, na prática, não é o que realmente acontece…

Na prática, existem vários e vários caminhos possíveis e isso deixa o Waze com dois grandes problemas para solucionar.

O primeiro é calcular o tempo de trajeto de tantas rotas possíveis e encontrar a melhor delas.

O segundo problema é ter que fazer isso rápido o suficiente para que o usuário não desista de usar o aplicativo.

Afinal, se toda vez que mudássemos a rota o aplicativo demorasse muito só para mostrar uma opção, não iria valer a pena usar o Waze.

Vamos com a imagem abaixo exemplificar esta situação, imagine que estamos representando todas as rotas possíveis.

Como o Waze Funciona
Vários percursos possíveis.

Ótimo, então como ele faz?

O Waze vai usar uma variação de um algoritmo chamado A*, sendo uma variação do algoritmo Dijkstra.

Algoritmo Dijkstra.

Vamos dizer que o Waze tem as estimativas de tempo dos percursos do ponto A ao ponto B como dissemos anteriormente.

A primeira coisa que ele vai ver é de onde o usuário está saindo, seu ponto de partida que vamos chamar de ponto A, saindo do ponto A qual o menor trajeto até o próximo ponto.

Lembrando que nosso objetivo é ir do ponto A para o ponto B como na foto abaixo.

Partindo do ponto de início do trajeto o ponto A qual o menor trajeto até o próximo ponto?

Neste caso é o trajeto de A até E que só leva 1 minuto.

Menor tempo partindo de A.
Menor tempo partindo de A.

Agora ele vai passar a considerar o ponto E no cálculo.

Partindo do ponto A e do ponto E qual o menor trajeto para chegar no ponto B.

Se somarmos o tempo de A + E + F vai resultar em 16 minutos.

Voltando ao ponto A vamos verificar o próximo menor tempo, qual a segunda opção de menor tempo partindo de A?

Se olharmos bem vamos ver que de A até E olhando para a parte de cima da imagem, leva 2 minutos e é a segunda menor distância.

Calculando esse novo trajeto e comparando com o primeiro vamos ver o de cima é mais rápido 10 minutos, agora o Waze vai considerar estes pontos também ponto A, “E de cima” e “E de baixo”.

Comparando as rotas.
Comparando as rotas

O próximo menor caminho é de A até D com 3 minutos, somando os demais pontos, todos têm tempo superior, veja na imagem abaixo.

Como o Waze Funciona
Comparando as rotas

Agora partindo destes novos pontos que estão sendo considerados, entre A + D + B ou A + C + B o que vai levar menos tempo até o destino?

Neste exemplo são os pontos A + C +B com oito minutos apenas.

Como o Waze Funciona
Encontrando a melhor rota.

Sempre partindo desta lógica, somando os pontos partindo de A, comparando e inserindo pontos até encontrar  o menor trajeto chegamos ao resultado A + C + B com 8 minutos.

Você pode estar pensando que isso deu bastante trabalho, mas considere que em uma situação real vamos ter muito mais trajetos possíveis e fazendo dessa forma conseguimos ignorar muitos pontos que não foram considerados, isso em grande escala economiza muito tempo.

O que nós temos que ter é uma quantidade de opções que seja manuseável, que nós conseguiríamos verificar de forma rápida e eficiente.

Ainda assim essa segunda forma que analisamos dá bastante trabalho…

Imagine que além desses pontos nós tivéssemos pontos com tempos pequenos de trajeto na direção oposta à do destino.

Esses trajetos também teriam que ser incluídos na análise porque comparado aos demais trajetos esses possuem um tempo menor, mesmo que não levem a lugar nenhum.

Ou seja, o aplicativo terá que analisar muitas rotas inúteis, fazendo muitos cálculos desnecessários.

Percursos opostos.
Percursos opostos.

Algoritmo A*:

É nesta hora que entra o A* sendo uma variação do Dijkstra.

O que ele faz é calcular a estimativa de tempo que levaria saindo do ponto A e indo direto para o ponto B.

Como o Waze Funciona
A*

Fazendo dessa forma além de identificar mais facilmente qual o provável trajeto em que o tempo será menor, nós ainda evitamos que trajetos opostos ao nosso destino sejam considerados pelo algoritmo, afinal, podemos ter um trajeto oposto com um tempo menor? Isso é muito pouco provável não é mesmo.

Neste modelo abrimos mão de encontrar o melhor caminho possível para conseguir encontrar o melhor caminho combinado com o menor tempo para calcular este caminho.

O Waze vai calcular o menor tempo apenas com os pontos que são prováveis.

Restringindo opções.
Restringindo opções.

Não será calculado o caminho partindo do tempo que leva do ponto A até o próximo ponto.

Agora o caminho é calculo considerando a estimativa.

Partindo do ponto A para o ponto C quanto tempo vamos gastar considerando a estimativa de A até o destino passando pelo ponto C?

Se esta estimativa for menor que as demais, então esse cálculo será priorizado.

Dessa forma os demais caminhos e pontos podem ser ignorados e isso torna o processo todo mais rápido.

Gostou da aula e quer saber mais sobre algoritmos e linguagem de programação! Clique nos links!

Conclusão – Como o Waze Funciona

Nesta aula nós explicamos como funciona a lógica por trás do aplicativo Waze.

De uma forma rápida, prática e com ilustrações simples mostramos a diferença da lógica entre algoritmos.

A partir deste exemplo você pode entender melhor como funcionam os algoritmos e como nos ajudam de forma prática no nosso dia a dia.

Espero que tenham gostado! Até mais,

Hashtag Treinamentos

Para acessar outras publicações de Python, clique aqui!


Quer aprender mais sobre Python com um minicurso básico gratuito?