Amigos, entregas e neurôniosCientistas espanhóis
criaram um algoritmo que usa o comportamento das formigas para
encontrar conexões entre membros de uma rede social.
Um dos desafios para criar um programa desse tipo é que as
redes sociais são gigantescas, exigindo um processamento muito
pesado. E quem busca as conexões de alguém quer a resposta muito
rapidamente.
Quando expressaram o problema em termos da teoria dos grafos,
Jessica Rivero e seus colegas da Universidade Carlos III
descobriram que o esforço poderia valer a pena porque a solução
teria uma utilização muito ampla.
Por exemplo, um programa eficiente desse tipo permite traçar
rotas para caminhões de entrega, descobrir caminhos mais curtos
em navegadores GPS, saber se duas palavras estão relacionadas de
alguma forma - ou descobrir as conexões entre pessoas nas redes
sociais.
Além do interesse ou da curiosidade dos próprios usuários, as
conexões nas redes sociais têm sido cada vez mais usadas como
instrumento de pesquisa pela antropologia e pela psicologia. O
mesmo mecanismo é usado pela neurociência para o estudo das
conexões entre os neurônios.
Múltiplas trilhas
Cada indivíduo, ou cada ponto de entrega, ou cada destino,
são representados como pontos de um grafo - grafo é uma
representação que usa pontos interligados por retas para mostrar
as interconexões de uma rede.
Percorrer todas as rotas possíveis para encontrar as ligações
é um problema que cresce exponencialmente conforme se avança
pelos nós individuais, tornando essa técnica de força bruta
inviável em termos computacionais quando os grafos têm mais do
que algumas centenas de nós.
Os pesquisadores espanhóis foram buscar inspiração nas
formigas, que constroem trilhas a partir do seu formigueiro para
encontrar comida.
Eles explicam que, além da trilha química que as formigas
traçam usando seu feromônio, quando estão buscando alimento,
elas deixam outros sinais químicos, equivalentes do "cheiro da
comida".
E isto permite que a colônia localize a fonte de alimento
muito mais rapidamente e de forma praticamente direta, sem ter
que percorrer todos os múltiplos caminhos que as batedoras
usaram quando estavam procurando o alimento.
Algoritmos inspirados em insetos
Embora muitos outros programadores já tenham se inspirado no
comportamento de insetos para desenvolver algoritmos de busca, a
inclusão desses sinalizadores adicionais deu resultados
estupendos.
"Os resultados iniciais mostram que a aplicação desse
algoritmo às redes sociais gera uma resposta ótima em um tempo
muito curto, na casa das dezenas de milissegundos," contou
Jessica.
Segundo ela, o principal ganho é que, imitando as trilhas
multiplamente sinalizadas das formigas, torna-se possível evitar
a modificação do grafo para a busca, reduzindo muito o tempo de
processamento.
Inovação Tecnológica
