- NeoFronteras - http://neofronteras.com -

Abejorros y el problema del viajante

Al parecer los abejorros saben resolver el problema del viajante. Una tarea difícil que en computación se cataloga como problema NP.

Foto
Abejorro en flor artificial.

El problema del viajante consiste en salir de la sede de la empresa y volver a la misma visitando todas las ciudades una sola vez por el camino más corto posible. Matemáticamente se trata de encontrar un ciclo hamiltoniano sobre un grafo en el que los vértices del grafo representan ciudades unidas por aristas (las carreteras) con un peso dado (los kilómetros o el gasto en combustible del tramo en cuestión). Básicamente, para este problema no hay un algoritmo que lo resuelva de manera eficiente y se cree que no existe. Aquí se entiende por “eficiente” el que sea resoluble en un tiempo polinómico. Es decir, que el tiempo de resolución en relación al tamaño del problema (en nuestro caso al número de vértices del grafo que representa las ciudades unidas por carreteras) crezca polinómicamente y no exponencialmente.
Aunque hay muchos algoritmos que encuentran una buena aproximación al problema del viajante, no existe ninguno que sea eficiente y que a la vez dé la mejor solución posible. La única manera de encontrar la mejor solución consiste básicamente en enumerar todas las posibilidades y escoger la mejor (la ruta más corta), algo sumamente ineficiente. Se sospecha que algunos de estos problemas, como el del viajante, nunca tendrán una solución eficiente, al ser problemas de tipo NP o NP completos.
Obviamente para unas pocas ciudades unidas por unas pocas carreteras es relativamente sencillo resolverlo a la fuerza bruta, incluso con sólo un lápiz y un papel. Pero si son muchas le lleva a un ordenador mucho tiempo resolver el problema.
Lo que buscamos con la resolución del problema del viajante es encontrar la ruta que cumple con nuestros objetivos con el menor gasto de energía y tiempo. Pero esto es precisamente lo que tienen que hacer algunos animales. Un abejorro, por ejemplo, necesita recolectar polen y néctar en diversas flores y de cómo lo haga dependerá su eficacia y, por tanto, su supervivencia. Esto debe de crear una presión de selección que haya hecho que los abejorros hayan evolucionado con el tiempo para que ser más eficientes y que inconscientemente recorran el menor camino posible.
Esto es lo debieron pensar científicos de varias instituciones británicas cuando se pusieron a investigar la optimización de los vuelos del abejorro en su tarea de recolectar néctar. Descubrieron que los abejorros resuelven el problema del viajante, siendo el primer ejemplo de este tipo en el reino animal. Y todo con un cerebro diminuto.
El equipo de investigadores usó flores artificiales controladas computacionalmente para ver si estos animalillos seguían una ruta marcada con anterioridad o si descubrían con la nueva disposición la ruta más corta. Después de explorar la nueva localización de las flores, los abejorros rápidamente aprendieron a encontrar el camino más corto, es decir, la solución del problema del viajante para esa configuración. Es de suponer que hagan lo mismo en el campo.
Según Nigel Raine, las “abejas” resuelven el problema del viajante todos los días. Visitan flores en múltiples lugares y como usan mucha energía en el vuelo necesitan optimizar la ruta para mantener el camino que vuelan al mínimo.
Comprender cómo los abejorros efectúan este tipo de cálculo puede que nos ayude a diseñar sistemas o algoritmos (quizás basados en redes neuronales), más eficientes y que necesiten escasos recursos, pues el cerebro de los abejorros es muy pequeño. Podrían usarse, por ejemplo, en el control del tráfico y en la regulación de semáforos.
Raine dice que “a pesar de sus pequeños cerebros las abejas son capaces de proezas extraordinarias. Necesitamos comprender cómo resuelven el problema del viajante sin la ayuda de un ordenador. ¿Qué tipo de atajos usan? ”
En el mundo de la computación ya se habían utilizado algoritmos inspirados en animales (en concreto en las hormigas) para resolver el problema del viajante, pero este caso constituye el primer caso real en la Naturaleza.

Copyleft: atribuir con enlace a http://neofronteras.com/?p=3281 [1]

Fuentes y referencias:
Nota de prensa I. [2]
Nota de prensa II. [3]
Artículo original. [4]
Computador bacteriano resuelve problema. [5]
¿Es P no igual a NP? [6]
Otras maneras de contar. [7]