Menéame: comentarios [1077756]

#57 Las abejas son más rápidas que los ordenadores [ENG]

pepitoperez — Thu, 04 Nov 2010 16:09:36 +0000

#56 No he visto el comentario hasta ahora, imagino que ya no lo leerás pero respondo de todas maneras

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.

» autor: pepitoperez

#56 Las abejas son más rápidas que los ordenadores [ENG]

vayavaya — Wed, 27 Oct 2010 16:34:20 +0000

#52

<<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.

» autor: vayavaya

#55 Las abejas son más rápidas que los ordenadores [ENG]

caledonio — Wed, 27 Oct 2010 04:00:48 +0000

A cambiar salas de servidores por colmenas!!!

» autor: caledonio

#54 Las abejas son más rápidas que los ordenadores [ENG]

--210566-- — Tue, 26 Oct 2010 22:54:20 +0000

[Usuario deshabilitado]

» autor: --210566--

#53 Las abejas son más rápidas que los ordenadores [ENG]

estoyausente — Tue, 26 Oct 2010 22:03:04 +0000

#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.

» autor: estoyausente

#52 Las abejas son más rápidas que los ordenadores [ENG]

pepitoperez — Tue, 26 Oct 2010 19:51:58 +0000

#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:

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.

» autor: pepitoperez

#51 Las abejas son más rápidas que los ordenadores [ENG]

portera — Tue, 26 Oct 2010 07:57:25 +0000

Los ordenadores on torpes, ni siquiera imaginan que exista el transistor.

» autor: portera

#50 Las abejas son más rápidas que los ordenadores [ENG]

vayavaya — Tue, 26 Oct 2010 07:34:03 +0000

#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.

Creo yo

» autor: vayavaya

#49 Las abejas son más rápidas que los ordenadores [ENG]

--212786-- — Tue, 26 Oct 2010 06:28:09 +0000

#28 y #31 Sí, hablo inglés, pero cuando leí el comentario no relacioné. Lo siento ^^

» autor: --212786--

#48 Las abejas son más rápidas que los ordenadores [ENG]

neike — Tue, 26 Oct 2010 05:50:48 +0000

Voy a tirar mi ordenador y sustituirlo por unas cuantas abejas

» autor: neike

#47 Las abejas son más rápidas que los ordenadores [ENG]

Pipopk — Mon, 25 Oct 2010 23:18:36 +0000

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

» autor: Pipopk

#46 Las abejas son más rápidas que los ordenadores [ENG]

GoldenPockets — Mon, 25 Oct 2010 23:12:22 +0000

#5 Teniendo en cuenta que estamos en España, eso es facil

» autor: GoldenPockets

#45 Las abejas son más rápidas que los ordenadores [ENG]

--193218-- — Mon, 25 Oct 2010 23:06:24 +0000

#36 Si hombre, pero tú has visto a Belen Esteban dando clases de Historia?
videos.larioja.com/informaciondecontenido.php?con=2185
Estoy seguro que hasta una abeja puede aprender antes que algunas personas sobre la edad media.

» autor: --193218--

#44 Las abejas son más rápidas que los ordenadores [ENG]

estoyausente — Mon, 25 Oct 2010 21:50:43 +0000

#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.

Pero afirmar... no podemos.

» autor: estoyausente

#43 Las abejas son más rápidas que los ordenadores [ENG]

Viridiana — Mon, 25 Oct 2010 21:22:10 +0000

¿Categoría abejas ya? ¿Qué le pasa a Menéame con estos insectos, que todos los días tenemos una portada suya?

» autor: Viridiana

#42 Las abejas son más rápidas que los ordenadores [ENG]

adelphos — Mon, 25 Oct 2010 21:17:33 +0000

Estamos a años luz de los desarrollos optimizados de la naturaleza.

Somos su creación más compleja.

» autor: adelphos

#41 Las abejas son más rápidas que los ordenadores [ENG]

RaiderDK — Mon, 25 Oct 2010 21:05:34 +0000

#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).

» autor: RaiderDK

#40 Las abejas son más rápidas que los ordenadores [ENG]

--26866-- — Mon, 25 Oct 2010 20:53:40 +0000

#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.

» autor: --26866--

#39 Las abejas son más rápidas que los ordenadores [ENG]

--13675-- — Mon, 25 Oct 2010 20:33:54 +0000

Voy a llevarles el eternity II a ver si me lo resuelven

» autor: --13675--

#38 Las abejas son más rápidas que los ordenadores [ENG]

Felip — Mon, 25 Oct 2010 20:26:59 +0000

¿Ahora mediremos la capacidad de almacenamiento en Megabees?

» autor: Felip

#37 Las abejas son más rápidas que los ordenadores [ENG]

--148944-- — Mon, 25 Oct 2010 20:09:54 +0000

[Usuario deshabilitado]

» autor: --148944--

#36 Las abejas son más rápidas que los ordenadores [ENG]

--2516-- — Mon, 25 Oct 2010 20:07:03 +0000

[Usuario deshabilitado]

» autor: --2516--

#35 Las abejas son más rápidas que los ordenadores [ENG]

pepitoperez — Mon, 25 Oct 2010 20:05:10 +0000

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.

» autor: pepitoperez

#34 Las abejas son más rápidas que los ordenadores [ENG]

--194262-- — Mon, 25 Oct 2010 19:59:32 +0000

Pues yo me iba a comprar un ordenador nuevo pero ahora me lo voy a pensar

» autor: --194262--

#33 Las abejas son más rápidas que los ordenadores [ENG]

bubota — Mon, 25 Oct 2010 19:56:08 +0000

Tendré que contratar a la abeja Maya

» autor: bubota

#32 Las abejas son más rápidas que los ordenadores [ENG]

rocambolescus — Mon, 25 Oct 2010 19:55:25 +0000

#28 Veo que tu tampoco

» autor: rocambolescus

#31 Las abejas son más rápidas que los ordenadores [ENG]

elbuit — Mon, 25 Oct 2010 19:53:35 +0000

#22 en.wikipedia.org/wiki/Bee

» autor: elbuit

#30 Las abejas son más rápidas que los ordenadores [ENG]

--56829-- — Mon, 25 Oct 2010 19:53:21 +0000

Como he leído hace un rato en Slashdot aquí news.slashdot.org/comments.pl?sid=1838028&cid=34012988

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

» autor: --56829--

#29 Las abejas son más rápidas que los ordenadores [ENG]

koki — Mon, 25 Oct 2010 19:51:02 +0000

Y mi cerebro más

» autor: koki

#28 Las abejas son más rápidas que los ordenadores [ENG]

chulonsky — Mon, 25 Oct 2010 19:48:42 +0000

#22 du yu not espik inglis pikinglis true?

» autor: chulonsky

#27 Las abejas son más rápidas que los ordenadores [ENG]

--213981-- — Mon, 25 Oct 2010 19:48:15 +0000

[Usuario deshabilitado]

» autor: --213981--

#26 Las abejas son más rápidas que los ordenadores [ENG]

Arcano — Mon, 25 Oct 2010 19:48:06 +0000

#22 Me imagino que el comentario intenta hacer un juego de palabras con Bee (abeja en inglés).

» autor: Arcano

#25 Las abejas son más rápidas que los ordenadores [ENG]

Arcano — Mon, 25 Oct 2010 19:47:10 +0000

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_(Discworld)

» autor: Arcano

#24 Las abejas son más rápidas que los ordenadores [ENG]

Hatuey — Mon, 25 Oct 2010 19:47:03 +0000

Seamos abejas, pero nunca 'obejas' que estas no llegan a ninguna parte

» autor: Hatuey

#23 Las abejas son más rápidas que los ordenadores [ENG]

--205705-- — Mon, 25 Oct 2010 19:44:02 +0000

Las abejas son como las células de nuestro cuerpo, su sociedad crea un macroorganismo aunque quizás no tan evidente como nuestro cuerpo humano.

» autor: --205705--

#22 Las abejas son más rápidas que los ordenadores [ENG]

--212786-- — Mon, 25 Oct 2010 19:40:35 +0000

#2 ABEJAS, no OVEJAS. Beestia...

» autor: --212786--

#21 Las abejas son más rápidas que los ordenadores [ENG]

sorrillo — Mon, 25 Oct 2010 19:02:52 +0000

No si el portátil viaja en un AVE.

» autor: sorrillo

#20 Las abejas son más rápidas que los ordenadores [ENG]

Juanfernando4532 — Mon, 25 Oct 2010 16:44:02 +0000

Una conversación en el futuro:

- 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.

» autor: Juanfernando4532

#19 Las abejas son más rápidas que los ordenadores [ENG]

sinosukenoaramenea — Mon, 25 Oct 2010 10:51:21 +0000

En español: www.rtve.es/noticias/20101025/abejas-son-mas-rapidas-ordenadores/36470

» autor: sinosukenoaramenea

#18 Las abejas son más rápidas que los ordenadores [ENG]

--142346-- — Mon, 25 Oct 2010 09:36:48 +0000

Pues ya saben, que construyan ordenadores con estructura de panal de abeja, que algo queda seguro

» autor: --142346--

#17 Las abejas son más rápidas que los ordenadores [ENG]

nfinlandia — Mon, 25 Oct 2010 09:28:04 +0000

#14 LOL

» autor: nfinlandia

#16 Las abejas son más rápidas que los ordenadores [ENG]

Zorlek — Mon, 25 Oct 2010 09:02:56 +0000

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...

» autor: Zorlek

#15 Las abejas son más rápidas que los ordenadores [ENG]

--170229-- — Mon, 25 Oct 2010 07:46:13 +0000

[Usuario deshabilitado]

» autor: --170229--

#14 Las abejas son más rápidas que los ordenadores [ENG]

Neowizard — Mon, 25 Oct 2010 02:35:07 +0000

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

» autor: Neowizard

#13 Las abejas son más rápidas que los ordenadores [ENG]

Ramanutha — Mon, 25 Oct 2010 02:19:35 +0000

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.

» autor: Ramanutha

#12 Las abejas son más rápidas que los ordenadores [ENG]

--82961-- — Mon, 25 Oct 2010 00:23:12 +0000

#1 bien sencillo, porque las abejas no resuelven un problema puramente matemático. Existen miles de factores (viento, partículas de polen, experiencia...)

» autor: --82961--

#11 Las abejas son más rápidas que los ordenadores [ENG]

SamCrow — Mon, 25 Oct 2010 00:10:32 +0000

Tranquilos, ya pronto Ono comienza a anunciar su nueva oferta de internet de 50 Abejas, más rápido que en Japón oigan!

» autor: SamCrow

#10 Las abejas son más rápidas que los ordenadores [ENG]

nacco — Sun, 24 Oct 2010 23:45:15 +0000

Pues yo oigo un zumbido en mi ordenador. ¿Quiere eso decir, qué a partir de ahora, irá más rápido?.

» autor: nacco

#9 Las abejas son más rápidas que los ordenadores [ENG]

lenn — Sun, 24 Oct 2010 23:29:39 +0000

A navegar con abejas, ¡vamos!

» autor: lenn

#8 Las abejas son más rápidas que los ordenadores [ENG]

formulauno — Sun, 24 Oct 2010 23:11:24 +0000

#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

» autor: formulauno

#7 Las abejas son más rápidas que los ordenadores [ENG]

formulauno — Sun, 24 Oct 2010 23:09:48 +0000

Lo de siempre.....

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

» autor: formulauno

#6 Las abejas son más rápidas que los ordenadores [ENG]

--153963-- — Sun, 24 Oct 2010 23:08:58 +0000

¿Como saben los investigadores que es la más corta?. No me queda claro.

» autor: --153963--

#5 Las abejas son más rápidas que los ordenadores [ENG]

pedrobotero — Sun, 24 Oct 2010 23:01:15 +0000

Y las palomas, no te ensajero nada, mas rápidas que el adsl

» autor: pedrobotero

#4 Las abejas son más rápidas que los ordenadores [ENG]

vviccio — Sun, 24 Oct 2010 22:59:58 +0000

Esto sería útil para nuestra sociedad basada en las redes: tráfico, comunicaciones, reparto de suministros, ...

» autor: vviccio

#3 Las abejas son más rápidas que los ordenadores [ENG]

yoma — Sun, 24 Oct 2010 22:55:22 +0000

Relacionada: www.meneame.net/story/abejas-ven-supercolores-supervelocidad-casi-cinc

» autor: yoma

#2 Las abejas son más rápidas que los ordenadores [ENG]

InfameIznogud — Sun, 24 Oct 2010 22:52:53 +0000

¡Qué beestias!

» autor: InfameIznogud

#1 Las abejas son más rápidas que los ordenadores [ENG]

vviccio — Sun, 24 Oct 2010 22:52:21 +0000

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

Ahora la cuestión es: ¿cómo lo hacen?.

» autor: vviccio