Dijkstra, Orkut e Cursinho

O cursinho da poli costuma ministrar palestras sobre as diversas carreiras para os seus alunos, e este último domingo foi a 7a Jornada de Trajetórias Profissionais.

O professor Carlinhos do deparatamento de Ciência da Computação da USP não poderia comparecer, então ele me obrigou indicou a participar em seu lugar. Lá fui eu, tentar recrutar nossos futuros colegas de pesquisa e de trabalho. Tentei bolar algo que fosse interessante aos jovens em idade de cursinho.

Comecei a apresentação com uma citação que eu acho perfeita para quebrar a ilusão de que nosso ramo é dominar o computador (ilusão a qual nossos parentes e amigos insistem em mater pedindo nossa ajuda na instalação de uma webcam ou scanner):

Ciência da Computação tem tanto a ver com o computador como a Astronomia com o telescópio, a Biologia com o microscópio, ou a Química com os tubos de ensaio. A Ciência não estuda ferramentas, mas o que fazemos e o que descobrimos com elas.

É de Edsger Dijkstra. E foi através de seu famoso algoritmo para resolver o problema do caminho mínimo que eu comecei a apresentar o que estudamos no curso. Introduzi o problema de encontrar a menor rota entre duas cidades dado o mapa do Brasil e a distância entre cada uma delas. Tentei fazer com que eles percebessem que uma solução qualquer, testando todos os caminhos, chegaria a n! combinações, um número astronômico (e.g., 15 fatorial = 1307674368000). Também mostrei que a solução gulosa, sempre procurando pelo vizinho mais próximo, da solução errada. Por último apenas disse que poderíamos fazer algo muuuuito rápido e rodei uma simulação, sem dizer nada sobre nlogn.

Mas a platéia reagiu mesmo quando fiz a comparação com o Orkut: “sabe quando você entra no perfil de uma pessoa do Orkut, e o site te mostra o caminho entre você e a outra pessoa? Então, o Orkut Büyükkokten, criador do site, estudou computação e aplicou esses conhecimentos para poder fornecer esse tipo de informação”, todos balançaram a cabeça, de maneira afirmativa. Ok, confesso que menti um pouco. Na verdade o Orkut não precisa de caminho mínimo pois as arestas não tem peso, basta uma busca em largura. Além disso o Orkut não vai disparar uma busca em largura em um grafo com 10 milhões de nós a cada vez que você acessar um perfil diferente, ele na verdade mantém (penso eu) uma estrutura de dados para realizar operações em grafos dinâmicos.

Com isso espero ter angariado um ou outro novo cientista da computação. E quem sabe mais programadores Java!

5 Comentários

  1. Luiz Aguiar 21/08/2006 at 10:31 #

    Puxa já encaminhei essa frase pra todos os meus primos… heheh… tomara que eles parem de me pedir pra arrumar o Windows deles agora heheh 🙂

  2. Oberon 21/08/2006 at 11:36 #

    Beeemm, vc não mentiu.. taaaanto. Vc pode considerar que as arestas não tenham peso na busca em largura…. ou considerar que todas tenham o mesmo peso como uma “simplificação” de um problema maior (o citado). HAEhaeheahaehhaeea

    Segundo o Thiago, na matemática é difícil haver uma situação onde realmente vc esteja mentindo.

    []´s

  3. Paulo Silveira 21/08/2006 at 11:45 #

    É verdade. Mas é um overkill escrever dijkstra para resolver uma busca em largura. Um jeito mais elegante é você criar uma busca onde os nós vão sendo inseridos em uma java.util.Collection. Aí, dependendo da implementação usada, sai algo diferente:

    java.util.ArrayList – vai gerar uma busca em largura
    java.util.Stack – vai gerar uma busca em profundidade
    java.util.PriorityQueue, onde a prioridade é o peso do caminho até aquele nó – vai gerar Dijkstra

  4. Fernando Boaglio 21/08/2006 at 18:39 #

    Legal o artigo Paulo, alguns links pra complementar:

    http://www.unf.edu/~wkloster/foundations/DijkstraApplet/DijkstraApplet.htm
    http://www.cs.sunysb.edu/~skiena/combinatorica/animations/dijkstra.html
    http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

    Fico curioso como isso é armazenado… se fosse no mundo relacional,uma tabela com auto-relacionamento seria suficiente, mas na prática para gerar a rede inteira de uma pessoa com muitas pessoas seria meio lento ou insano…

  5. Paulo Silveira 21/08/2006 at 18:47 #

    É. Se tivermos 1 milhão de usuários, seriam 1 trilhão de linhas na tabela associativa do auto relacionamento. Não há chances. Creio que eles façam um cache LRU, por isso as vezes o orkut já mostra a distância, as vezes ele demora, porque fez uma requisição AJAX e realiza a busca em largura.

    Repare que mesmo a busca em largura, para buscar alguém que está a 5 de distância de você, e considerando uma média de 100 amigos por pessoa, essa busca realizaria 100^5 = 10,000,000,000… 10 bilhões de comparações. Por isso o orkut só te mostra o caminho de quem está no máximo a 3 de distância, para realizar apenas 1 milhão de comparações.

    Se você pesquisar por grafos online/dinâmicos, vai ver que já existem estruturas de dados para que ele consiga modificar o grafo e atualizar as distâncias de maneira mais rápida, sem ter de pesquisar novamente!

Deixe uma resposta