​O Simples e Elegante Algoritmo Que Torna o Google Maps Possível

Algoritmos são uma ciência baseada em engenhosidade. Uma manifestação natural do raciocínio lógico – indução matemática, em especial – um bom algoritmo é como um retrato passageiro e condenatório da alma de um problema. Uma selva de propriedades e relações torna-se uma simples relação de recorrência, um passo recursivo de linha única produzindo caos e complexidade sem limites. E para ver através desta complexidade, é necessário engenhosidade.

Foi o pioneiro da programação Edsger W. Dijkstra quem realmente sacou isso, e o algoritmo que leva seu nome segue como uma das coisas mais engenhosas na informática. Um defensor ferrenho da simplicidade e elegância na matemática, ele meio que acreditava que todo problema complicado tinha uma parte acessível, uma entrada, e a matemática era uma ferramenta a ser usada para encontrá-la e explorá-la.

Em 1956, Dijkstra estava trabalhando no ARMAC, uma máquina de computação paralela instalada no Centro Matemático da Holanda. Tratava-se da sucessora dos computadores ARRA e ARRA II, que haviam sido, essencialmente, as primeiras máquinas deste tipo no país. Seu dever era programar aquela coisa, e assim que estivesse pronto para ser revelado ao público – após dois anos de esforço conjunto – Djikstra precisava de um problema para solucionar.

"Para uma demonstração feita para pessoas não ligadas à informática, o problema tem que ser descrito de forma que não-matemáticos possam compreender", relembrou Dijkstra em uma entrevista concedida não muito antes de sua morte, em 2002. "Elas tem que entender até mesmo a resposta. Então projetei um programa que encontraria a rota mais curta entre duas cidades na Holanda, usando uma espécie de mapa reduzido do país, em que havia escolhido 64 cidades."

"Qual a distância mais curta para ir de Rotterdam à Groningen?", disse Dijkstra. "É o algoritmo para o caminho mais curto, que desenvolvi em cerca de 20 minutos."

O Google Maps faz isso por nós agora e nem precisamos pensar no quão complexa pode ser esta tarefa. Problemas de caminhos mais curtos, característica essencial da teoria dos grafos com um monte de aplicações óbvias no mundo real, podem ficar muito complexos muito rápido. O resultado é conhecido (informalmente) como explosão combinatória, que é o onde número de diferentes combinações a serem exploradas em determinado problema cresce exponencialmente.

O resultado de tal explosão é que problemas, como estes de caminho mais curto, crescem tão rapidamente de forma a ficarem praticamente incomputáveis, levando uma quantidade praticamente infinita de tempo para serem resolvidos. É necessário somente um punhado de pontos em um mapa ou grafo para que o número de possíveis combinações chegue aos milhões, exigindo quantidades absurdas de tempo.

A maneira mais fácil de explicar o algoritmo de Dijkstra é provavelmente através de um exemplo. Observe o gráfico abaixo, os números são os pesos de cada conexão. (Um peso pode ser uma distância simples ou qualquer custo relativo associado de percorrer determinada conexão que queremos minimizar.) Inicialmente atribuímos a s, nossa posição inicial, o valor 0. São necessários 0 quilômetros (ou o que for) para chegar aqui pois é a posição inicial. Em seguida, vemos os nodos vizinhos a s, que podemos imaginar como fronteiras a serem exploradas.

Na primeira iteração, observamos o nodo mais próximo, a 1 unidade de distância. Conferimos um rótulo ao nodo com esse valor, a, e observamos os próximos nodos e suas respectivas distâncias. b está a 1 de distância (2 a partir do início), c está a 2 de distância (3 a partir do início), e também temos o d, a 2 de distância do início. Já que buscamos o caminho mais curto do início, somos forçados a nos mover de d a partir de s (2 unidades), conferindo a d o valor de 2. Na próxima iteração do algoritmo, de d observamos c a 10 de distância (12 a partir de s), mas observamos novamente a partir de a, onde podemos chegar a c em 2 (3 a partir do início) e b em 1 (2 a partir do início). Nossa próxima parada será b e lhe conferimos o valor de 2 (2 movimentos desde o início).

Nosso explorador no b irá se desapontar agora. O único movimento possível para t está a 10 unidades de distância (12 a partir do início). E isto é mais que as 2 unidades de a a c (3 a partir do início) e a mesma viagem de s a c por d, uma possibilidade que podemos descartar seguramente (chegando a c com apenas 3 unidades, ao invés das 12 exigidas via d). Agora estamos em c e tudo parece complicado, mas não é. Só estamos dando passos cuidadosos de nodo a nodo, enquanto somos forçados pelo algoritmo a sempre considerar o caminho mais curto desde o início.

Finalmente, observamos de b para t, mais uma vez notando que o caminho total é 12. Enquanto isso, o salto final de c custa 1 unidade, para uma distância total mais curta de 4. Então um problema incrivelmente complexo – explosivamente complexo – pode ser resolvido de forma elegante, simples e até mesmo intuitiva, no papel.

Mais exemplos:

Dijkstra diz ter pensado nisso enquanto tomava uma xícara de café em alguma cafeteria local. "De fato, foi publicado em 1959, três anos depois", lembrou. "A publicação segue ótima. uma das razões pelas quais é tão boa é que a criei sem papel nem lápis. Sem esses dois você é quase forçado a evitar complexidades. Eventualmente aquele algoritmo se tornou, para minha surpresa, um dos pilares de minha fama."

É este algoritmo que faz o Google Maps funcionar, ou ao menos alguma variação dele. De verdade, é isso que possibilita o ato de traçar rotas: engenhosidade o bastante para ver em meio a todo o caos.

Tradução: Thiago "Índio" Silva