O Simples e Elegante Algoritmo Que Torna o Google Maps Possível
Escrito
por
EDITOR
25 March 2015 // 11:00 AM CET
ESTE texto maravilhoso, escrito com o
espirito critico e personal de Michael Byrne para a revista MOTHERBOARD
despertou em mim a lembrança eterna das primeiras aulas de turbo pascal no ICEX
da UFMG. Saudade de um tempo, o IBM poderoso, enorme, o tempo escasso para
programar. Legal demais, queria ter lido este texto naquele tempo.
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.
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 as, 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 dobservamos 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 testá 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
No comments:
Post a Comment