Ariel Palazzesi
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.
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”.
“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.
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.
Bueno, sera cuestion de tener un par de abejas mutantes gigantes con localizador y colocar flores acorde a su tamaño en todas las ciudades para marcar las nuevas rutas de gps(suena un poco a peicula bizarra… no? xD ).
Hola!
Quizás baste con poner las flores sobre un "modelo a escala" del mapa a resolver. Digamos que en un terreno de 200×200 metros o asi. Y luego ver que ruta siguen… 🙂
Saludos!
obs: las abejas no son animales ¬¬’
¿No?
"Animales", "vegetales" y "minerales"…. en que grupo las pondrías ? 🙂
No son MAMIFEROS, pero son animales. Concretamente, invertebrados del filo de los artrópodos.
Saludos!
son hongos no te enteraste?? xD
Claro el animal sos vos….
¡Animal! xD
Y por cierto, ¿cual creen que sea su algoritmo? Yo opino que sus sentidos les ayudan a ubicar la flor más cercana, y que en cada parada es la dirección que toman.
reino animalia; filo arthropoda; clase insecta; orden hymenoptera; suborden apocrita; superfamilia apoidea; familia apidae; subfamilia apinae; tribu apini; genero apis; especie apis mellifera.
Y TU ERES UN TONTO Y TE CALLAS
La clásica teoría del caos de toda la vida. De lo simple a lo complejo e impredecible.
pani_alex: Quedate tranquilo que vos sos un ANIMAL con todas las letras 😉
No pueden defender la evolución si les molesta que les digan "animales", ANIMALES :D.
Y en cuanto a la abeja… sin palablas.
Gracias.
Hemos de recordar que los humanos han IMITADO lo que la naturaleza hace, los algoritmos que usa nuestro cerebro no los puede imitar una supercomputadora, lo mismo pasa con los insectos, animales, etc, sus algoritmos no son iguales al de nosotros. Las abejas tienen ese nivel de procesamiento porque es VITAL para su vida, no por hobby. Cuando las cosas son vitales la naturaleza optimiza sus recursos….
Los humanos solo nos limitamos a imitar lo que la naturaleza hace, solo que lo hacemos de otra manera, con maquinas y ordenadores.
Larga vida a la Madre Naturaleza que nos demuestra quien es mas sabia
no coincido contigo. Si existe en la naturaleza se puede imitar por el hombre solo que quizás necesitemos un ordenador con una arquitectura diferente a la que hoy se usa (véase arquitectura de von neuman o cmo coño se escriba)
Tampoco es verdad que la naturaleza optimice las características que nos benefician sino que aquellos individuos que las poseen tienen una mayor ventaja en la competencia que supone la vida (véase teoría de la ev. ) Como los seres humanos no tenemos que competir entre nosotros sino que la ventaja la impone el dinero que no se transmite en el ADN creo firmemente que el hombre ha dejado de evolucionar biológicamente y así será hasta el maldito día en que nos tengamos que pegar por los recursos ("no se como combatirá en la 3ª guerra mundial, pero en la 4ª se hará con palos y piedras" Einstein.)
es diferente una abeja a una ciudad pero bueno …
la abeja memoriza peviamente todas las rutas inconscientemente para despues hacer una diferencia de cual esta mas cerca y cual esta mas lejos con lo que despues pasa por las otras que se supone que estan mas lejos para despues volver directa a la colmena
a el ordenador le pides que calcule todos los recorridos sin previo conocimiento y por eso tarda enb procesar ademas que el ordanador no " ha pasado por ahi antes "
esas son las razones que creo acertadas para decir que una abeja no tiene un algortimo " magico " para saber como hacelo mas rapido sino que ya tiene todos los datos previamente y no tiene que ir a un sitio en especifico sin ya seberlo
lo que se da, se acabo !
Chuck: justamente eso que dices es fuerza bruta: analizar TODAS las opciones y de alli elegir la mas corta.. y eso lleva muchisimo procesamiento por lo que hay que analizar si las abejas hacen realemente eso o siguen algun otro algoritmo aun no descubierto…
eee no contradigas a Chuck, cuidado, te puede mandar a volar con una patada giratoria
Teoria de Grafos en la mente de la abejas.
es que las abejas pueden hacer un par de cositas que un ordenador no, primero puede volar un poco mas alto para tener una vista general de panorama sin necesidad de visitar todas las flores y segundo, que es lo que haria personalmente, es ir de una flor a la otra mas cercana evitando las ya visitadas, esto ultimo pordria funcionar si de nodo en nodo de una red la informacion fuera enviada hacia el punto mas cercano, seria una forma de solucionar el problema aunque reconosco que no es la mas optima pero si la mas cercana.
me imagino que no estaras hablando en serio…
parece que nunca has visto una abeja en tu vida…
Ah es eso! Mi ordenador no vuela lo suficientemente alto entonces…
Existen más de un método para resolver el problema. Si alguien de ustedes ha llevado en la universidad la materia "investigación de operaciones" sabe entonces de que estoy hablando.
"¿Es superior el cerebro de una humilde abeja a un superordenador que cuesta millones de euros?"
No creo que esté bien enfocada esta pregunta, obviamente un superordenador es muy potente pero siempre estará limitado a los programas con los que trabaje, si al superordenador no le damos un algoritmo, una fórmula o algo con lo que pueda trabajar en este problema seguirá haciéndolo de forma bruta y poco eficiente, como dice el autor del artículo sobre este problema no sabemos mucho del cómo resolverlo, esto es lo primero que hay que hacer, aprender a resolverlo y luego pasarselo a algún ordenador para que haga el trabajo.
el cerebro de las abejas esta basado en Linux, por eso son mas rapidas……
Lapidacion en 3, 2, 1……….
como molas…
jajajjaja +1 por la excelente respuesta que me saco una sonrisa.
Lastima que hay personas que se ofenden muy rapido, jajaja saludos.
Acaban de poner en ridiculo a las supercomputadoras xD
querras decir a los algoritmos que corren esas supercomputadoras. como ya comentaron antes, el problema no es la computadora sino el algoritmo.
Me recordaron las aventuras de la abeja maya, valla que tiempos aquellos. snif
me imagino que se guian por los sentidos, dejan marcas quimicas así evitan que otra abeja busque donde ya estuvieron y ademas de guiarse por la luz ultravioleta tambien me imagino que se guian por el olfato a oler el polen.
Como pueden afirmar que las abejas secorren el camino mas corto? y si recorren 20 flores? estos tipos tendrian que tardar 77.146 años para poder afirmar que las abejas hacen eso.
tal vez probaron con pocas flores, y se cumple su premisa pero no se puede generalizar para cualquier numero de flores.
Tal vez usaron muchas supercomputadoras 😀
Jeje, no se, pero tu apunte me parece notable. A pesar que parece sencillo de darse cuanta de eso, no lo habia notado. Aunque, pueden haber casos en los que se sepa el resultado del problema, no se, como el de las flores, y se prueba con abejas, recuerda que el articulo dice que se demorarian ese tiempo con "fuerza bruta", pero podria usar otro algoritmo para probar que las abejas efectivamente recorren el camino mas corto.
Hola, para encontrar el camino óptimo de un recorrido no hace falta utilizar el algoritmo por fuerza bruta, existen muchos algoritmos heurísticos que reducen el tiempo considerablemente de búsqueda del camino óptimo.
Otros algoritmos, como algoritmos genéticos o el de colonia de hormigas, que poseen una tasa de error muy baja pueden localizar el corto mas corto (puede ser o no el óptimo) en un tiempo muchísimo menor. Este ultimo (en de colonias de hormigas) puede resolver sistemas con mas de 1000 nodos!! y es el algoritmo que se utiliza para el ruteo de nodos de internet.
Saludos
gracias por explicárselos tan claramente, te llevaste un +1
Buen punto!
Corrijanme si estoy mal… 🙂
Como ejemplo, tomar la distancia con la vista, calcular "al ojo" que existe X distancia y luego tomar la ruta mas corta. ¿Eso no se llama aprendizaje?. Una vez que puedas cargarle al ordenador de informacion con distancias, tiempo etc, no seria mas facil para el algoritmo descartar las mas lejanas y obviamente menos cortas?.
No creo que sea necesario un cerebro muy grande y creo que las abejas adquieren experiencia de acuerdo a las vivencias por sus sentidos, asi como nosotros.
pues te dire que tu propuesta aunque logica en un principio, es engañosa y te lo digo yo que lo he comprobado comparando trayectorias en mi ciudad usando Google earth, me sorprendi algunas veces al darme cuenta que lo que pensaba que era la ruta mas corta en realidad sumaba mas kilometraje.
Si fuera tan sencillo, ya estaría resuelto. De hecho, eso que comentas (descartar las más lejanas y coger las más cercanas) es una versión de "fuerza bruta" al hacer el cálculo.
El objetivo es acortar la distancia total recorrida y, aunque parezca que lo intuitivo es "coger en cada salto la distancia más corta", no tiene por qué ser la mejor opción. En cada nodo, las opciones que tienes dependen de los que ya hayas visitado, por lo que acortar a corto plazo, puede alargar el total.
Veamos un ejemplo:
Partiendo de Sevilla, tenemos que visitar Madrid, Valencia y Oporto y volver (supongamos línea recta).
Desde Sevilla, lo más cercano es Madrid. Desde Madrid, entre Oporto y Valencia, lo más cercano es Valencia. Finalmente, Oporto y vuelta a Sevilla: aproximadamente 1897 Km.
Si miramos lo que hemos hecho, hemos recorrido Madrid-Valencia dos veces, ida y vuelta, porque de Valencia a Oporto pasas por Madrid (casi).
Si hacemos: Sevilla-Valencia-Madrid-Oporto-Sevilla, la distancia son unos 1737 Km. Ahorramos 160 km, pero en el primer salto no hemos cogido el más corto.
Es decir, no siempre usar el salto más corto da el recorrido total más corto. Esto, ampliado a muchos nodos, da tantas combinaciones posibles, que aún no se sabe como coger la mejor. Sí hay algoritmos que dan soluciones "suficientemente buenas", pero no se ha encontrado la manera de encontrar el camino más corto consistentemente y en un tiempo razonable.
Por supuesto que el cerebro de una abeja es superior a un superordenador
Mi primera leccion en la universidad fue
"los ordenadores son bestias" xd
No pienso que sean bestias
Son solo entes que requieren ser controlados por nosotros
Los humanos… vaya que si que somos bestias
Interesante el articulo.
¿Cuan dificil seria explicar una simple
funcion de vida de un ser?
Pues… ahi esta la respuesta
A ver si sacan abejas para mi GPS y dejo de dar vueltaaassss!!!!
Todas la abejas tomas rutas aleatoria al recolectar miel, cuando regresar entrega la miel y los datos de posicionamiento, luego la reina usa eso datos y se conecta a los otros paneles y usando el computo en paralelo de todos los panales a nivel mundial resuelve la ruta mas corta con fuerza bruta. Bueno me voy a dormir tengo días de transnochos -.-
Muy Interesante el articulo, el algoritmo es un sentido de la abeja o la union de varios!
La Preguntaa Es Cual esa Percepcion que la abjea tiene?
Como han dicho otros, no se puede saber si las abejas eligen el camino óptimo, porque si el número de nodos es suficientemente grande, los investigadores tampoco lo pueden saber. Así que basta con que elijan un camino "suficientemente bueno", como hacen los algoritmos conocidos, para ver que son muy listas, pero no queda demostrado que hayan resuelto el problema.
A mi parecer hacen falta mas datos respecto del experimento con las abejas, yo me imagino que si es cierto lo que dicen, en dos experiencias aisladas deberia ocurrir lo mismo, osea: se tienen dos maquetas con areas iguales, cada una con mmm no lo se… 6 flores, ubicadas en los mismos puntos del area de las maquetas, luego se tienen 2 abejas, una para cada maqueta, y se procede a soltarlas para la experiencia, el resultado de la ruta seguida por ambas deberia ser el mismo no es cierto? mmmm creo que lo probare aqui en casa xD.