O Desafio do Caixeiro Viajante
Você foi contratado para otimizar a logística de uma cooperativa agroindustrial. Sua missão é criar a rota de coleta dos caminhões.
Regras:
- Comece clicando em qualquer ponto no mapa.
- Clique nos outros pontos para conectá-los. Você deve visitar todos os pontos exatamente uma vez.
- Para finalizar a rota, clique novamente no ponto inicial.
- O objetivo é criar o caminho com a menor distância total possível!
A Matemática por trás da Logística
O que você acabou de tentar resolver é conhecido na Matemática e na Pesquisa Operacional como o Problema do Caixeiro Viajante (TSP). Trata-se de um problema clássico da Teoria dos Grafos.
- Nós (Vértices): Representam as fazendas, silos ou indústrias no mapa.
- Arestas (Arcos): Representam as estradas ou rotas entre eles.
- Pesos: É o custo (neste caso, a distância em quilômetros) de ir de um ponto a outro.
O objetivo é encontrar o Ciclo Hamiltoniano de Menor Custo (um caminho que visita todos os vértices uma única vez e retorna ao início custando o mínimo possível).
Para um mapa com apenas 7 pontos (como o deste jogo), existem 360 rotas diferentes para verificar. O computador calcula isso em milissegundos. Mas veja o que acontece se aumentarmos o número de cidades na rota de entrega:
- 10 Cidades: 181.440 rotas possíveis.
- 15 Cidades: 43 bilhões de rotas.
- 20 Cidades: 60 quatrilhões de rotas!
Como o número de rotas possíveis apresenta crescimento fatorial, sendo da ordem de (n-1)! / 2, este é classificado como um problema NP-Difícil. Não existe, até hoje, uma fórmula matemática que resolva esse problema de forma rápida para mapas muito grandes. É por isso que engenheiros de produção e analistas de logística usam algoritmos de aproximação (heurísticas) para planejar rotas de caminhões de safra e frotas de entrega, economizando milhões em combustível e tempo!