EDICIóN GENERAL
213 meneos
3196 clics
Una ameba encuentra solución aproximada a problema de dificultad NP en tiempo lineal (ING)

Una ameba encuentra solución aproximada a problema de dificultad NP en tiempo lineal (ING)  

Los investigadores, liderados por Masashi Aono en la Universidad de Keio, han demostrado que una ameba, un organismo unicelular que consiste en protoplasma gelatinoso, tiene capacidades informáticas únicas que pueden algún día ofrecer una alternativa competitiva a los métodos usados por las computadoras convencionales. Asignaron a una ameba para resolver el Problema del Vendedor Viajero (TSP). El TSP es un problema de optimización en el que el objetivo es encontrar la ruta más corta entre varias ciudades. Lo resolvió en tiempo lineal.

| etiquetas: ameba , plasmodio , solución , resolver , problema , np , biotecnología
Tanta inteligencia artificial y no se nos ocurrió preguntarle a la ameba :-D Más: royalsocietypublishing.org/doi/10.1098/rsos.180396
#1 confirmado, esa ameba no fue a la URJC :troll:
Así pues la ameba esta supera al bachiller medio.
Ya ha superado al usuario medio de este portal.
Es muy difícil comentar sobre esto sin conocer bien el tema, y sin tener mayor información sospecharía del planteamiento del experimento. Hablar de "tiempo líneal" en el comportamiento de una ameba me parece complicado.
#4 Por? Duplicas el numero de 'ciudades' a visitar y a la ameba le lleva el doble de tiempo resolver el problema.
#7 Porque es un concepto aplicado generalmente a algoritmos, computadores, y al menos yo veo complicado aplicarlo a la ameba. No sabemos nada de la capacidad de "cómputo" la ameba, ni de como computa dichos caminos. No discuto el experimento de forma objetiva, solo las conclusiones que parecen extraer de él. Al hablar de problemas NP hablamos de problemas que se pueden resolver en tiempo polinómico con una máquina no determinista. Muchos problemas NP son resolubles en tiempo…   » ver todo el comentario
#9 Lo has explicado fenomenal.
Comparto tus dudas.
#9 igual si te lees el artículo en vez de hacerte pajas mentales, te aclaras.
#16 Creo que #22 también aplica aquí... pero sin tener que leer todo el artículo sólo la primera línea.
#27 Es cierto, comenté antes de leerme el artículo y luego vi que no iba por los mismos derroteros. Lo cual me dejó un poco frío porque aquí se pasa de N = 4 a N = 8 en tiempo lineal que es como... meh. Es pura deformación profesional, al haber trabajado en temas similares.
#9 Desde mi desconocimiento, creo que leí hace mucho tiempo que las soluciones al problema tiempo_óptimo-ruta que daban algunas razas de perros también superaban a los algoritmos convencionales de un procesado binario.
#7 pues no, desde el punto de partida con 3 ciudades hay 6 rutas, pero con 4 ciudades hay 24 rutas posibles y con 5 son 120.
#20 Eso es la solucion exacta: O(n!). En el articulo hablan de una aproximacoin lineal O(n).
Además que parece claro por el título que no lo soluciona. Encuentra una solución aproximada, con lo cual está a la altura de otras heurísticas.
#5 No si es una aproximación más cercana a la optima o la encentra más rápido.
#5 sí, pero gastando muchas menos células.... Por tanto, toda esta mierda de la evolución no sirve para nada.

LARGA VIDA A LAS AMEBAS >:-(
Fijo que la ameba se lee el artículo entero y no la entradilla
#6 por eso las amebas están tan mal vistas en menéame.
Pronto seremos gobernados por amebas.
#8 Ya llevamos tiempo
Amo a ve,

Igual que una persona jugando al ajedrez, no resuelve el problema examinando todas las posibilidades, sino que el sentido común (el menos común de los sentidos) descarta muchas posibilidades y resuelve en un tiempo lineal con la talla del problema.
En este sentido, imagino que el sentido evolutivo de supervivencia del 'bisho' hace que se optimice el consumo de energía, pero sin valorar todas las posibilidades, sólo de manera instintiva...
o han encontrado a una ameba a la que podrían darle un premio nobel...
Hay amebas que a primera vista parecen tontas y cuando las vas conociendo te llevas una sorpresa
Informática Zerg
Ya teníamos noticias de amebas de esas hace tiempo,  media
Este tema tampoco es la panacea, que se diga. Es una idea que se lleva explorando bastante tiempo, ya que los organismos vivos se reproducen a velocidad exponencial (al menos hasta que saturas la capacidad del medio). La idea es que, si puedes resolver un caso de un problema en una célula, y puedes trasladar cada caso a una célula distinta, en un tiempo lineal obtienes capacidad de cómputo exponencial.

El problema es que la capacidad de cómputo exponencial se ve limitada por los recursos. Tu…   » ver todo el comentario
Ahora dadle los putos filósofos, con su falta de tenedores y los spaghetti y a ver hace la listilla
#21 xD muy bueno esa
#21 No recuerdo quien me lo dijo que el problema tiene mucho más sentido cuando los filósofos son chinos y utilizan palillos :-D
Uff... Ahora vendrán a decirnos que no tenemos razón y que maltratamos a los bichos cuando decimos: "eres más tonto que una ameba". ?(
#25 y cuidadin que acaba en a. A ver si te va a denunciar
Así empezó matrix
Vale. Pero no hay cojones de conseguirlo con un votante de PP, C$ o VOX.
#32 "Los votantes de derechas soooon tooontos"

Muy bien magsx, ya has hecho tu simplificación boba del dia. Limpiate los mocos que comemos en nada.
Detalle importante: solución aproximada. Algoritmos que resuelvan el TSP de manera aproximada en tiempo lineal existen desde hace ya mucho, lo verdaderamente revolucionario hubiera sido que pudiera resolverlo de manera exacta.
También hay otro experimento similar donde se usa un hongo en el mapa de España y el alimento son las ciudades más importantes al final el hongo dibujaría el mapa de ferrocarril o carretera más eficiente.
Como apuntan otros comentarios el truco de que dice solución aproximada y no exacta. La solución exacta en tiempo lineal no existirá, a menos que NP=P. Por tanto, casi imposible que ocurra.

Hay muchos seres vivos que damis buenas soluciones. El propio ser humano (y algún animal superior) tiene una predisposición innata a resolver este problema. Otros organismos más simples pero que viven en colonias también tienen esa capacidad.

Lo que creo que es novedad en este estudio de que un único ser unicelular sin capacidad neuronal tenga mecanismos que den una buena aproximación al TSP
Yo no soy una ameba (aunque las amebas tengas más vida social que yo!) y ya conseguí la demostración exacta hace muchos años en un examen!!! Pero lejos de darme el millón de dólares, encima me suspendieron vílmente!!! He aquí tal portentosa demostración! Sea P la nota de "Presentarse" a este exámen, sea NP la nota de "No Presentarse" ... P=NP!!!

Pero no hay problema, inventé una máquina para viajar al futuro cuyo único objetivo es saltar de iteración en iteración para envenar al pobre Alan Turing (Y sí, que pasa! Soy un poco rencoroso!!!)

menéame