#1 Las abejas buscan la ruta más corta entre las flores que han sido encontradas en un orden aleatorio, resolviendo eficazmente el "problema del viajero". es.wikipedia.org/wiki/Problema_del_viajante
Habra cosas en las que seran mas rapidas calculando cosas y otras en las que seran mas lentas.... Ponles una raiz cuadrada y veremos quien es mas rapido.... otra cosa es que en lo suyo sean mejores
#8#5 A segun para que cosas podria decirse que si y para otras se podria decir que no
El ejemplo del pendrive, podria valer para distancias cortas.... ahora bien, mandalas a Japon en un viaje de ida y vuelta y a ver si la paloma no te manda a la mierda
#12#1 bien sencillo, porque las abejas no resuelven un problema puramente matemático. Existen miles de factores (viento, partículas de polen, experiencia...)
#13 Luego me leo la noticia al completo, pero resulta que el sentido común es más potente que un ordenador en muchísimos casos. Como ya he comentado en otra noticia, una persona en una partida de ajedrez no necesita analizar los millones de jugadas posibles en muchos casos para saber cual es la jugada más conveniente.
#14 Es completamente cierto, en mi clase había una abeja y siempre nos copiabamos de ella en matemáticas, además, para el recreo nos traía unos buenos bocadillos con miel
#16 espero que no utilicen un sistema operativo de Windows o en el proceso de polinizacion el tiempo seria: quedan 30 segundos...queda 1 minuto, queda 30 minutos, quedan 27 segundos...
- Te has enterado? he comprado el nuevo ordenador pemtium cuamtium III
- Pues hombre, te han estafado.
- Pero si es el nuevo Pemtium cuamtium III! anda, que me corre busca minas v32!
- Esta bien hombre, pero ya lo nuevo es el ordenador con chip de cabeza de abeja, ya sabes, el que te zumba recién inicia el windows 77.
#25 Me recuerda a cómo funciona la memodira de HEX, la inteligencia artificial que crea Terry Pratchett para la Universidad Invisible del Mundo Disco. La memoria de HEX está compuesta de paneles con abejas. en.wikipedia.org/wiki/Hex_%28Discworld%29
¿Es posible que las abejas no estén resolviendo el problema para nada, si no mas bien usando algún tipo de heurística desconocida que lleva a una solución que esté tan próxima a la óptima que parezca que lo han resuelto? Quizás eso es lo que deberíamos mirar mas que ver si las abejas, de alguna manera, tienen algún tipo de capacidad de cálculo mayor que la de un superordenador.
Después de todo, cuando jugamos al baseball y la bola viene hacia nosotros, no calculamos en nuestras cabezas la velocidad, resistencia al aire y otras variables envueltas en darle a la bola. Simplemente estiramos nuestros brazos y nuestro cerebro hace algun tipo de adivinación basada en heurísticas o algo así para darle.
#35 El problema del viajante de comercio es un problema de optimización combinatoria y pertenece a la clase NP, es decir no se puede resolver en tiempo polinómico.
Eso es tanto para un ordenador como para un abeja. Porque encontrar la solución, en este caso el camino más corto, para el problema básicamente consiste en enumerar todas las combinaciones posibles de soluciones para una instancia de dicho problema.
Así que la naturaleza como los informáticos lo que hacemos es conformarnos con encontrar un camino que, si bien, no es el más corto, si se acerca bastante; si queremos solucionarlo en un tiempo que no sea NP. Solución heurística.
El método para encontrar dicha "pseudo-solución" es lo que varía. La naturaleza proporciona varias soluciones por motivos de supervivencia y pocas conocemos.
Está demostrado que las colonias de insectos, sobretodo hormigas y abejas, son muy buenas resolviendo esto, es decir, encontrar rápidamente una buena solución (pseudo-solución) y, con una alta probabilidad, coinciden con la solución óptima. Muchas abejas salen aleatoriamente buscando polen, en su recorrido van soltando feromonas, que hace que las demás sigan su recorrido. Aquella abeja que por suerte ha encontrado el camino más corto, tardará menos tiempo en ir y volver, repetidamente, a la colmena a depositar el polen. Por tanto, su rastro (olor) de feromonas será mas intenso que la de otras abejas que tardan más en realizar su recorrido. De esta manera, el resto de abejas seguirán ese camino por acción de la feromona. Las hormigas funcionan igual.
Con los animales superiores: ser humano, elefantes, delfines también está demostrado, según varios estudios, que por naturaleza somos muy buenos resolviendo el problema del viajante de comercio en su versión euclidiana. Nuestras estructuras cerebrales pueden manejar de forma muy fácil planos en geometría euclidiana y resolver o proporcionar una buena solución al problema del viajante de comercio. De hecho, resolver este problema para nosotros, los humanos, y otros animales superiores nos dota de mayor capacidad a la superviviencia.
#40#1 En mi vida he abierto más los ojos que ahora, cuando he leído lo siguiente de tu enlace:
Por ejemplo, si un ordenador fuese capaz de calcular la longitud de cada combinación en un microsegundo, tardaría algo más 3 segundos en resolver el problema para 10 ciudades, algo más de medio minuto en resolver el problema para 11 ciudades y 77.146 años en resolver el problema para sólo 20 ciudades.
#41#ChuckFact
Chuck Norris encuentra la solucion casi optima al problema del viajante de comercio en tiempo Logaritmico. No es optima porque el señor viajante visita a Chuck Norris dos veces (por si acaso).
#44#35 ' El problema del viajante de comercio es un problema de optimización combinatoria y pertenece a la clase NP, es decir no se puede resolver en tiempo polinómico.
Eso es tanto para un ordenador como para un abeja. Porque encontrar la solución, en este caso el camino más corto, para el problema básicamente consiste en enumerar todas las combinaciones posibles de soluciones para una instancia de dicho problema. '
De momento no tiene solución, pero ahí están dándole vueltas. Nunca digas nunca. No se ha demostrado que no exista una solución de complejidad polinómica a ese problema, aunque si bien es cierto que no se ha demostrado lo contrario ni se ha encontrado una solución de ese estilo. De ahí que el problema P-NP esté de momento, por resolver.
#47 el prblema sería, ¿cómo programar a la abejas para que resuelvan un determinado problema? osea si, pueden ser mas rapidas, pero como las controlas para que hagan lo que necesitas?
aún asi es algo interesante
#50#35 "El problema del viajante de comercio es un problema de optimización combinatoria y pertenece a la clase NP, es decir..." ... se puede resolver en tiempo polinómico en una máquina no determinista.
#52#44 y #50 El problema del viajante de comercio está demostrado que pertenece a la clase NP-completo. Eso está demostrado matemáticamente. Así que, por mucho que queramos y inventemos la máquina que inventemos, no lo cambiará.
Lo que no está demostrado es la pregunta ¿P = NP? La comunidad científica sospecha que no son iguales y está pendiente de que se admita esta:
En el casi improbable caso de que P=NP, el problema del viajante de comercio es NP-completo, es decir, la clase de problemas más difíciles de NP. Y para los NP-completo existe otra sospecha de la comunidad científica, y es la clase NP-completa no pertenecería a P, en el caso de que P=NP.
En definitiva, sería más fácil pincharme con la aguja del pajar, antes que encontrar una solución en tiempo polinómico al problema del viajante de comercio.
#53#52 Sí, si estamos de acuerdo. Esa intuición tenemos, eso se cree y eso pensamos. ¡Pero falta demostrarlo! jeje
Que sólo era por poner la puntillina hombre, no te quitaba la razón, para una vez que tocamos un tema que me gusta y del que sé un poquito me apetecía pedantear.
<<Y para los NP-completo existe otra sospecha de la comunidad científica, y es la clase NP-completa no pertenecería a P, en el caso de que P=NP.>> ???
No me entero (y además no veo esas líneas en el enlace que pones)...
Premisas:
NP es el conjunto de problemas que se pueden resolver en tiempo polinomial en una máquina no determinista
NP-completo es el conjunto de los problemas más difíciles de resolver del conjunto NP.
P es el conjunto de problemas que pueden ser resueltos en tiempo polinomial por una máquina determinística. No se sabe con seguridad todavía si P es un subconjunto propio de NP, pero se cree que sí.
Entonces,
como el conjunto NP-completo es un subconjunto de NP, si se llega a demostrar que el conjunto P es igual al conjunto NP -> eso quiere decir que el conjunto NP-completo también sería un subconjunto de P.
Otra cosa distinta sería que se demostrara que P = (NP - NP-completo)
¿Qué opinas?
Además, el segundo párrafo de #35 tampoco convence, donde dices que los informáticos nos conformamos con encontrar un camino subóptimo y para ello resolvemos un problema que está fuera del conjunto NP.
El caso es que aunque P=NP, seguiría existiendo problemas que no estarían en P.
Además, el segundo párrafo de #35 tampoco convence, donde dices que los informáticos nos conformamos con encontrar un camino subóptimo y para ello resolvemos un problema que está fuera del conjunto NP.
Como dije en #35 llegar a este tipo de compromiso tiempo/calidad-solución nos ocurre tanto a humanos como a la propia naturaleza en sus soluciones. Y no sólo en este problema del viajante de comercio, en muchísimos otros.
No sé si eres informático universitario (no lo digo por discriminar a nadie, pero en otros niveles educativos de la informática no se suele estudiar teoría de la computación), te lo digo, porque a este tipo de soluciones se les llama heurísticas y es mucho más común de lo que tú crees.
Resolver hasta el óptimo el problema del viajante de comercio para 2000 ciudades aproximadamente pueden ser meses o años de computación. Si tienes un sistema crítico donde necesitas una solución en escasos segundos, no tienes más remedio que usar alguna técnica heurística.
La naturaleza lo hace, una colmena de abejas no se puede permitir el lujo de tardas tanto tiempo en encontrar alimento. Aplican su propio heurístico y que nosotros hemos copiado: "heurístico de la colonia de insectos". O si tu trabajas en una empresa de reparto qué haces: echas un vistazo al mapa y construyes tu propia solución (los humanos somos buenos en esto) o te sientas en una mesa con papel y bolígrafo y te pones a calcular la solución.
www.guardian.co.uk/world/2010/oct/24/bees-route-finding-p... 
Ahora la cuestión es: ¿cómo lo hacen?.
Habra cosas en las que seran mas rapidas calculando cosas y otras en las que seran mas lentas.... Ponles una raiz cuadrada y veremos quien es mas rapido.... otra cosa es que en lo suyo sean mejores
El ejemplo del pendrive, podria valer para distancias cortas.... ahora bien, mandalas a Japon en un viaje de ida y vuelta y a ver si la paloma no te manda a la mierda
- Te has enterado? he comprado el nuevo ordenador pemtium cuamtium III
- Pues hombre, te han estafado.
- Pero si es el nuevo Pemtium cuamtium III! anda, que me corre busca minas v32!
- Esta bien hombre, pero ya lo nuevo es el ordenador con chip de cabeza de abeja, ya sabes, el que te zumba recién inicia el windows 77.
Paso a traducir:
¿Es posible que las abejas no estén resolviendo el problema para nada, si no mas bien usando algún tipo de heurística desconocida que lleva a una solución que esté tan próxima a la óptima que parezca que lo han resuelto? Quizás eso es lo que deberíamos mirar mas que ver si las abejas, de alguna manera, tienen algún tipo de capacidad de cálculo mayor que la de un superordenador.
Después de todo, cuando jugamos al baseball y la bola viene hacia nosotros, no calculamos en nuestras cabezas la velocidad, resistencia al aire y otras variables envueltas en darle a la bola. Simplemente estiramos nuestros brazos y nuestro cerebro hace algun tipo de adivinación basada en heurísticas o algo así para darle.
Creo que tiene mucha razón ese comentario
Eso es tanto para un ordenador como para un abeja. Porque encontrar la solución, en este caso el camino más corto, para el problema básicamente consiste en enumerar todas las combinaciones posibles de soluciones para una instancia de dicho problema.
Así que la naturaleza como los informáticos lo que hacemos es conformarnos con encontrar un camino que, si bien, no es el más corto, si se acerca bastante; si queremos solucionarlo en un tiempo que no sea NP. Solución heurística.
El método para encontrar dicha "pseudo-solución" es lo que varía. La naturaleza proporciona varias soluciones por motivos de supervivencia y pocas conocemos.
Está demostrado que las colonias de insectos, sobretodo hormigas y abejas, son muy buenas resolviendo esto, es decir, encontrar rápidamente una buena solución (pseudo-solución) y, con una alta probabilidad, coinciden con la solución óptima. Muchas abejas salen aleatoriamente buscando polen, en su recorrido van soltando feromonas, que hace que las demás sigan su recorrido. Aquella abeja que por suerte ha encontrado el camino más corto, tardará menos tiempo en ir y volver, repetidamente, a la colmena a depositar el polen. Por tanto, su rastro (olor) de feromonas será mas intenso que la de otras abejas que tardan más en realizar su recorrido. De esta manera, el resto de abejas seguirán ese camino por acción de la feromona. Las hormigas funcionan igual.
Con los animales superiores: ser humano, elefantes, delfines también está demostrado, según varios estudios, que por naturaleza somos muy buenos resolviendo el problema del viajante de comercio en su versión euclidiana. Nuestras estructuras cerebrales pueden manejar de forma muy fácil planos en geometría euclidiana y resolver o proporcionar una buena solución al problema del viajante de comercio. De hecho, resolver este problema para nosotros, los humanos, y otros animales superiores nos dota de mayor capacidad a la superviviencia.
Por ejemplo, si un ordenador fuese capaz de calcular la longitud de cada combinación en un microsegundo, tardaría algo más 3 segundos en resolver el problema para 10 ciudades, algo más de medio minuto en resolver el problema para 11 ciudades y 77.146 años en resolver el problema para sólo 20 ciudades.
Chuck Norris encuentra la solucion casi optima al problema del viajante de comercio en tiempo Logaritmico. No es optima porque el señor viajante visita a Chuck Norris dos veces (por si acaso).
Somos su creación más compleja.
Eso es tanto para un ordenador como para un abeja. Porque encontrar la solución, en este caso el camino más corto, para el problema básicamente consiste en enumerar todas las combinaciones posibles de soluciones para una instancia de dicho problema. '
De momento no tiene solución, pero ahí están dándole vueltas. Nunca digas nunca. No se ha demostrado que no exista una solución de complejidad polinómica a ese problema, aunque si bien es cierto que no se ha demostrado lo contrario ni se ha encontrado una solución de ese estilo. De ahí que el problema P-NP esté de momento, por resolver.
Pero afirmar... no podemos.
videos.larioja.com/informaciondecontenido.php?con=2185
Estoy seguro que hasta una abeja puede aprender antes que algunas personas sobre la edad media.
aún asi es algo interesante
Creo yo
Lo que no está demostrado es la pregunta ¿P = NP? La comunidad científica sospecha que no son iguales y está pendiente de que se admita esta:
ciencia.barrapunto.com/ciencia/10/08/09/080213.shtml
En el casi improbable caso de que P=NP, el problema del viajante de comercio es NP-completo, es decir, la clase de problemas más difíciles de NP. Y para los NP-completo existe otra sospecha de la comunidad científica, y es la clase NP-completa no pertenecería a P, en el caso de que P=NP.
es.wikipedia.org/wiki/NP-completo
En definitiva, sería más fácil pincharme con la aguja del pajar, antes que encontrar una solución en tiempo polinómico al problema del viajante de comercio.
Que sólo era por poner la puntillina hombre, no te quitaba la razón, para una vez que tocamos un tema que me gusta y del que sé un poquito me apetecía pedantear.
<<Y para los NP-completo existe otra sospecha de la comunidad científica, y es la clase NP-completa no pertenecería a P, en el caso de que P=NP.>> ???
No me entero (y además no veo esas líneas en el enlace que pones)...
Premisas:
NP es el conjunto de problemas que se pueden resolver en tiempo polinomial en una máquina no determinista
NP-completo es el conjunto de los problemas más difíciles de resolver del conjunto NP.
P es el conjunto de problemas que pueden ser resueltos en tiempo polinomial por una máquina determinística. No se sabe con seguridad todavía si P es un subconjunto propio de NP, pero se cree que sí.
Entonces,
como el conjunto NP-completo es un subconjunto de NP, si se llega a demostrar que el conjunto P es igual al conjunto NP -> eso quiere decir que el conjunto NP-completo también sería un subconjunto de P.
Otra cosa distinta sería que se demostrara que P = (NP - NP-completo)
¿Qué opinas?
Además, el segundo párrafo de #35 tampoco convence, donde dices que los informáticos nos conformamos con encontrar un camino subóptimo y para ello resolvemos un problema que está fuera del conjunto NP.
Te pongo un diagrama de Venn donde verás bien como quedan los conjuntos con ambas hipótesis:
es.wikipedia.org/wiki/Archivo:P_np_np-completo_np-hard.svg
El caso es que aunque P=NP, seguiría existiendo problemas que no estarían en P.
Además, el segundo párrafo de #35 tampoco convence, donde dices que los informáticos nos conformamos con encontrar un camino subóptimo y para ello resolvemos un problema que está fuera del conjunto NP.
Como dije en #35 llegar a este tipo de compromiso tiempo/calidad-solución nos ocurre tanto a humanos como a la propia naturaleza en sus soluciones. Y no sólo en este problema del viajante de comercio, en muchísimos otros.
No sé si eres informático universitario (no lo digo por discriminar a nadie, pero en otros niveles educativos de la informática no se suele estudiar teoría de la computación), te lo digo, porque a este tipo de soluciones se les llama heurísticas y es mucho más común de lo que tú crees.
Resolver hasta el óptimo el problema del viajante de comercio para 2000 ciudades aproximadamente pueden ser meses o años de computación. Si tienes un sistema crítico donde necesitas una solución en escasos segundos, no tienes más remedio que usar alguna técnica heurística.
La naturaleza lo hace, una colmena de abejas no se puede permitir el lujo de tardas tanto tiempo en encontrar alimento. Aplican su propio heurístico y que nosotros hemos copiado: "heurístico de la colonia de insectos". O si tu trabajas en una empresa de reparto qué haces: echas un vistazo al mapa y construyes tu propia solución (los humanos somos buenos en esto) o te sientas en una mesa con papel y bolígrafo y te pones a calcular la solución.