A maioria dos humanos deixou de estimular a sua capacidade natural de orientação. Hoje, confiamos a definição do nosso rumo, mesmo em distâncias curtas e habituais, a sistemas de navegação por satélite. São ecossistemas complexos, equipados com mapas actualizados em tempo real, dados sobre o trânsito, acidentes e, em países como a China, até a temporização dos semáforos. Com tanta informação ao dispor, estes sistemas conseguem facilmente definir o trajeto perfeito, certo?
Errado. Calcular a rota ideal parece simples porque o cérebro humano é mestre em ignorar visualmente opções absurdas. Para um computador, o problema é puramente matemático e a complexidade explode rapidamente, especialmente se tentarmos descobrir a melhor rota entre vários pontos. Este desafio é o cerne do Problema do Caixeiro-Viajante: a dificuldade não reside na distância entre os pontos, mas no número astronómico de combinações possíveis.
Mesmo o cálculo entre apenas dois pontos é um grande desafio para um computador que não vê o mapa como nós; onde vemos uma linha reta, a máquina vê um “grafo”, uma rede de milhões de segmentos interligados (arestas) e interseções (nós). Numa metrópole, existem dezenas de milhares de interseções e o computador precisa de testar estas conexões para garantir que não ignorou um atalho num beco ou numa via rápida.
O método clássico e exacto para resolver este problema é o algoritmo de Dijkstra. Ele funciona “espalhando-se” a partir da origem em todas as direções, calculando a distância de cada interseção até atingir o destino. É um método exaustivo que explora caminhos na direção oposta ao destino apenas para garantir, por exclusão de partes, que são mais longos. Já a solução moderna, o algoritmo ‘A’, utiliza uma “heurística” (uma estimativa) para dar prioridade aos caminhos que parecem levar na direção correta, poupando imenso processamento.
A complexidade escala porque o “custo” de uma rua não é apenas a distância em metros. O computador atribui um “peso” a cada segmento que muda constantemente: trânsito, semáforos e consumo de combustível. É um puzzle de otimização com milhares de peças voláteis.
Para evitar a sobrecarga dos processadores, os sistemas modernos utilizam hierarquias: dão prioridade estradas principais e autoestradas, onde há menos nós para processar. Contudo, isto cria um “efeito de manada” que entope as vias rápidas, enquanto estradas secundárias ficam desertas. No final, beneficiaríamos todos se usássemos estes sistemas como apoio e não como guias inquestionáveis.
