O ex-aluno de mestrado do Departamento de Ciência da Computação (DCC) da UFMG, Bruno Monteiro, transformou as ruas da região central de Belo Horizonte em um complexo quebra-cabeça matemático. Instigado por um desafio não oficial de ciclistas que rodaram 216 quilômetros na área, ele utilizou algoritmos de otimização para calcular a rota mais curta que passasse por todas as vias delimitadas pela Avenida do Contorno. O resultado prático foi uma ultramaratona de 178 quilômetros, concluída a pé em 34 horas e meia.
A ideia surgiu após Monteiro analisar o esforço excessivo das tentativas empíricas e questionar, sob a ótica da Ciência da Computação, qual seria a distância mínima real. O primeiro obstáculo foi definir e mapear o que de fato era uma rua. Ao extrair dados de mapas digitais, ele precisou criar regras próprias e filtrar o sistema para excluir calçadas duplicadas e rotas inacessíveis a pedestres, gerando um modelo estruturado da cidade com centenas de cruzamentos.
Para traçar o caminho perfeito, ele se baseou no “Problema do Carteiro Chinês”. A lógica determina que, para não repetir ruas desnecessariamente, todos os cruzamentos precisam ter um número par de vias conectadas. Como a malha urbana não é perfeitamente simétrica e possui cruzamentos ímpares, Monteiro utilizou um algoritmo para conectar esses pontos com a menor distância possível, definindo com exatidão quais quarteirões teriam que ser percorridos duas vezes. O cálculo puramente matemático apontou um trajeto ideal de 145 quilômetros.
No entanto, a rota gerada pelo computador apresentava um traçado errático e repleto de ziguezagues, inviável para a navegação humana durante uma corrida. Para resolver a questão, o desenvolvedor aprimorou o código introduzindo uma estratégia que priorizava escolhas em linha reta a cada esquina, minimizando as mudanças bruscas de ângulo.
Com o arquivo finalizado e carregado em seu relógio GPS, o ex-aluno foi para o asfalto. Apesar da estimativa teórica inicial, imprecisões do sistema de posicionamento e pequenos erros de trajeto estenderam o percurso. Ainda assim, a marca final de 178 quilômetros representa uma redução estrutural profunda em relação às rotas não otimizadas. O relato completo da jornada, que detalha a aplicação do código e o desgaste das horas ininterruptas de atividade, está disponível no blog do ex-aluno, mostrando como conceitos abstratos de engenharia podem ser executados literalmente passo a passo.
Acesse o blog: https://codeforces.com/blog/entry/154192
