O Caixeiro Viajante caçando Pokemons

Está na iminência de chegar ao Brasil o novo jogo que vem revolucionando o mundo dos gamers – e acho que o dos não gamers também. É difícil encontrar hoje alguém que ainda não conheça, pelo menos um pouco, o jogo Pokemon Go. A Nintendo sem dúvida encontrou a nova disrupção no mundo dos Games e, apesar de ter tanto amantes quanto detestadores dessa nova onda, é impossível ignorar o impacto que o jogo trouxe para a sociedade. A imagem abaixo, por exemplo, mostra a movimentação não usual do Central Park em Nova York quando apareceu por lá um Vaporeon (pokemon poderoso e relativamente raro).

FONTE: http://ftw.usatoday.com/

Podemos destacar também o estímulo à criatividade proporcionado pelo jogo. Na imagem abaixo, por exemplo, vemos um celular preso a uma galinha – já que é necessário andar 2, 5 ou 10km para chocar ovos que contenham pokemons ou prêmios. No outro caso, a Marinha norte americana tenta angariar novos funcionários usando como isca a possibilidade de capturar Pokemons raros que não são encontrados nos Estados Unidos.

E na área da logística e Pesquisa Operacional? O que esse jogo tem a ver com a gente?

No século XIX os matemáticos W.R. Hamilton e Thomas Kirkman formularam o problema do Caixeiro Viajante (Travelling Salesman Problem). Trata-se de um dos problemas mais estudados pela Pesquisa Operacional, no qual deseja-se obter o caminho mais curto passando por diversas cidades (apenas uma vez) e retornando à origem. A descrição pode parecer simples, mas o problema é combinatorial, o que pode deixar a solução ótima impossível de ser encontrada. Desde a década de 1930 o problema vem sendo extensivamente estudado de forma que hoje existem metodologias de resolução que trazem, no mínimo, uma resposta boa, se não a ótima.

Atualmente, esta modelagem é usada como base em diversos problemas mais complexos, principalmente àqueles que envolvem roteirização de diversos pontos - por exemplo, entregas urbanas, problemas de coleta e entrega e até mesmo o Uber Pool.

E o que isso tem a ver com o Pokemon Go? Pois bem, em diversas cidades, estão disponíveis mapas de PokeSpots -lugares onde se pode coletar ovos e prêmios. Então, para maximizar a eficiência dos jogadores, uma equipe da Universidade de Waterloo resolveu o problema do Caixeiro Viajante, considerando os PokeSpots como as cidades do problema, garantindo assim que os jogadores possam percorrer todos os PokeSpots identificados, percorrendo a mínima distância possível.

O resultado obtido é muito legal, por exemplo, na região de São Francisco, são 99 pontos e 104.503 metros. Em Toronto são 109 pontos e 148.706 metros e o percurso mais comprido fica para os jogadores de Houston, que precisam visitar 2008 pontos e 2.121.499 metros! (talvez nesse caso pouca gente tope caçar todos os Pokemons a pé).

FONTE: http://www.math.uwaterloo.ca/tsp/poke/

Brincadeiras à parte, essa experiência mostra a potencialidade das ferramentas da Pesquisa Operacional, como modelos de otimização que resolvem o famoso Problema do Caixeiro Viajante, e como trata-se de uma área super versátil da ciência de tomada de decisões, já que conseguimos aplicar até para a mais nova tendência em jogos.

#pokemón #caixeiroviajante

Categorias
Posts recentes
Arquivo
 
Telefone: (11) 3032 - 6742      contato@genoads.com.br      Rua Álvaro Anes, 46, Pinheiros, São Paulo - SP