:::: MENU ::::

sexta-feira, 29 de outubro de 2010

Problema do Caixeiro-viajante


Imagine uma cena que acontece todos os dias: um vendedor deve percorrer várias cidades e gostaria de saber o caminho mais curto que lhe permita visitar todas.

O problema é velho conhecido dos matemáticos e dos cientistas da computação, tão conhecido que é chamado de Problema do Caixeiro-viajante - caixeiros-viajantes eram pessoas que antigamente saíam vendendo badulaques pelas cidadezinhas do interior.

O fato é que não existe um algoritmo eficiente para resolver o problema. Mesmo os grandes supercomputadores podem ficar ocupados por dias tentando achar a solução para um número relativamente pequeno de cidades - isto porque ele precisa comparar todas as combinações possíveis de rotas.

Circuito neural mínimo


Mas a equipe do professor Lars Chittka, da Universidade de Londres, na Inglaterra, descobriu que as abelhas encontram a solução para o problema sem precisar de supercomputadores - e tendo um cérebro pouco maior do que a cabeça de um alfinete.
Abelhas não vendem badulaques por aí, mas elas precisam achar a rota mais eficiente para visitar diversas flores.
"As abelhas têm que associar centenas de flores de uma maneira que minimize a distância da viagem e, em seguida, encontrar de forma confiável o caminho de casa - não é uma façanha trivial se você tiver um cérebro do tamanho de uma cabeça de alfinete," diz Chittka.

Ao estudar como as abelhas fazem, os cientistas conseguiram identificar o circuito neural mínimo necessário para a solução de problemas complexos.

Da Internet ao trânsito


Chittka e seus colegas usaram flores artificiais controladas pelo computador para verificar se as abelhas iriam seguir uma rota definida pela ordem em que elas descobriram as flores ou se iriam procurar a rota mais curta.

Eles se espantaram ao ver que, depois de explorar a localização das diversas flores, as abelhas aprenderam rapidamente a fazer o percurso mais curto possível. A parte mais difícil da pesquisa foi ficar esperando o computador calcular o menor caminho possível, para checar se as abelhas estavam certas.

A descoberta tem uma ampla gama de aplicações - da entrega de pacotes de dados na Internet e de pacotes reais pelos Correios, até a eliminação de engarrafamentos nas cidades, apenas para citar alguns.

E, compreendendo como as abelhas podem resolver um problema que para os humanos se tornou um dilema, mesmo tendo um cérebro tão pequeno, poderemos melhorar nossas capacidades de administração de nossas necessidades diárias sem depender de computadores superpoderosos o tempo todo.


Bibliografia:
Travel Optimization by Foraging Bumblebees through Readjustments of Traplines after Discovery of New Feeding Locations
Mathieu Lihoreau, Lars Chittka, Nigel E. Raine
The American Naturalist
October 25, 2010
Vol.: 176, pp. 000-000
DOI: 10.1086/657042

SITE INOVAÇÃO TECNOLÓGICA. Abelhas resolvem dilema da computação. 28/10/2010. Online. Disponível em www.inovacaotecnologica.com.br/noticias/noticia.php?artigo=abelhas-resolvem-problema-caixeiro-viajante. Capturado em 29/10/2010. 


Categories: ,

0 comentários:

Postar um comentário

Só não vale xingar a mãe ou puxar cabelo nos comentários =)

Posts populares