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!
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.
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 fazer a previsão considerando todas essas rotas?
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.
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.
Ó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.
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”.
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.
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.
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.
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.
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.
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!
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,
Para acessar outras publicações de Python, clique aqui!
Expert em conteúdos da Hashtag Treinamentos. Auxilia na criação de conteúdos de variados temas voltados para aqueles que acompanham nossos canais.
Quer sair do zero no Python e virar uma referência na sua empresa? Inscreva-se agora mesmo no Python Impressionador