martes, 26 de octubre de 2010

Abejas resuelven “El problema del viajero”

Abejas resuelven “El problema del viajero”: "

Abejas resuelven “El problema del viajero”

Todos sabemos que existen problemas cuya complejidad es tal, que resultan inabordables incuso para los superordenadores más potentes. Sin embargo, su solución -si es que existe- podría encontrarse utilizando otras formas de procesamiento. Científicos de la escuela de Ciencias Biológicas de la Universidad de Londres ha descubierto que las abejas son capaces de resolver “El problema del viajero”, uno de los más más voraces consumidores de tiempo de CPU. Pero ¿Como lo hacen?

Alguna vez, en un artículo sobre el “algoritmo voraz te contamos en que consiste el llamado “problema del viajero”. Se trata de un problema que prácticamente todos los alumnos de carreras relacionadas con la informática deben enfrentar en algún momento de sus estudios: “¿Cual es la ruta mas corta que permite a un viajero visitar una lista determinada de destinos?”. Este problema, cuya solución es trivial cuando el numero de destinos posibles es solo dos y bastante fácil de hallar para un número de destinos posibles pequeño -basta con aplicar la “fuerza bruta”, evaluando todos los recorridos posibles y quedarse el trazado que utiliza la menor distancia- se convierte en un dolor de cabeza cuando la cantidad de ciudades implicadas aumenta.

Visto en Neoteo: Abejas resuelven “El problema del viajero”
Las abejas son capaces de resolver “El problema del viajero” (Wikimedia/Alvesgaspar)
Las abejas son capaces de resolver “El problema del viajero” (Wikimedia/Alvesgaspar)

El número de posibles rutas que puede seguir el viajero viene dado por el factorial del número de ciudades (N!) que debe visitar, lo que hace que cada ciudad que se agregue en el recorrido eleve enormemente la complejidad del problema. Si disponemos de un ordenador que pueda analizar un millón de recorridos por segundo, podría hallar la ruta óptima para un recorrido por 10 ciudades en poco más de de 3 segundos. Si fuesen 11 ciudades, demoraría más de medio minuto. Y si fuesen solo 20 ciudades, necesitaría unos 77.146 años en encontrar el recorrido más corto. Pero puede que al elegir un superordenador como herramienta para resolver este problema nos hayamos equivocado: un equipo de científicos de la escuela de Ciencias Biológicas y la escuela Queen Mary de Ciencias Biológicas y Químicas de la Universidad de Londres ha descubierto que las abejas pueden encontrar la ruta más corta posible entre grupos de flores. ¿Es superior el cerebro de una humilde abeja a un superordenador que cuesta millones de euros? Parece que cuando se trata de resolver determinados problemas la respuesta es un rotundo “si”.

Visto en Neoteo: Abejas resuelven “El problema del viajero”
Las abejas son capaces de comportamientos extraordinarios.(Photo-Morgia)
Las abejas son capaces de comportamientos extraordinarios.(Photo-Morgia)

En su ambiente natural las abejas necesitan visitar cientos de flores cada día, siguiendo una ruta que minimice la distancia recorrida”, explica Lars Chittka, uno de los autores de la investigación cuyos resultados serán publicados esta semana en la revista American Naturalist. “No está nada mal, sobre todo si consideramos que el cerebro de este animal no es más grande que la cabeza de un alfiler”, agrega. Los científicos diseñaron un experimento en el que se dispusieron flores artificiales sobre un terreno para comprobar si las abejas se limitaban a seguir una ruta fija, dictada por el orden en el que descubrían las flores o si, por el contrario, podían encontrar rutas más cortas y eficientes. Los expertos descubrieron que, luego de explorar el terreno para determinar la ubicación de las flores, las abejas rápidamente comenzaron a visitarlas siguiendo el camino más corto. En otras palabras, habían resuelto el “problema del viajero”. Hasta donde sabemos, es la primera vez que se demuestra que un animal puede resolver un problema semejante.

Visto en Neoteo: Abejas resuelven “El problema del viajero”
¿Es superior el cerebro de una humilde abeja a un superordenador? (Flickr/Autan)
¿Es superior el cerebro de una humilde abeja a un superordenador? (Flickr/Autan)

El Doctor Nigel Raine, coautor del artículo próximo a publicarse, explica que las abejas resuelven este problema cada día, y que el trabajo de su equipo servirá para comprender la forma en que los enjambres de abejas se mueven polinizando cosechas y flores salvajes, a la vez que nos proporcionarán la clave para mejorar el trazado de las carreteras y rutas de distribución. "A pesar de disponer de un cerebro pequeño, las abejas son capaces de comportamientos extraordinarios. Necesitamos entender cómo pueden resolver este problema sin un utilizar un ordenador. En este momento no sabemos como lo hacen”, explica Raine. ¿Lo sabremos algún día? Probablemente si. Hace falta realizar más experimentos, diseñados especialmente para que podamos obtener pistas que nos ayuden a comprender como lo hacen. Es evidente que el cerebro de las abejas resuelve este problema sin recurrir a la “fuerza bruta”, pero -hoy por hoy- no sabemos mucho más.


Enlaces relacionados:
Visto en Neoteo: Abejas resuelven “El problema del viajero”
Visto en The Guardian

Technorati Tags:
Tags Blogalaxia: "