Por @Alvy — 26 de Diciembre de 2018

Este curioso vídeo muestra algo parecido a una ameba resolviendo el Problema del viajante (TSP) de forma sorprendentemente más «eficiente» –comillas obligatorias– que algunos algoritmos conocidos hasta la fecha. Este clásico problema matemático consiste básicamente en «encontrar la ruta más corta posible que visite cada ciudad de un mapa una sola vez». Se trata de un trabajo de investigadores de la Universidad Keio de Japón: Remarkable problem-solving ability of unicellular amoeboid organism and its mechanism (The Royal Society Publishing).

En el experimento todo está convenientemente adaptado y simplificado para el mundo de una ameba gelatinosa (Physarum polycephalum). El problema está simplificado a ocho «ciudades» que quedan conectadas con las demás mediante unos canales, todo ello sobre una placa con un medio de cultivo y con luces que actúan para cerrarle el paso a la criatura una vez ha visitado cada «ciudad». La ameba cambia de forma y se las apaña para encontrar la «comida» y absorber nutrientes poco a poco. Hasta ahí todo bien.

Remarkable problem-solving ability of unicellular amoeboid organism and its mechanism

¿Dónde está lo llamativo? El problema del viajante se considera matemáticamente dentro de la llamada clase de complejidad NP-difícil y su dificultad aumenta exponencialmente a medida que aumenta el número de ciudades. Es por eso que las personas o incluso los ordenadores más potentes llega a ser inabarcable, aunque se conocen algoritmos aproximados, «casi óptimos» o «más razonables» para resolverlo en la práctica.

Lo interesante es que según los investigadores «la ameba tan solo necesita una cantidad lineal de tiempo para encontrar la solución (casi óptima) al pasar de 4 a 8 ciudades». En otras palabras, aunque el número de combinaciones de posibles rutas aumenta exponencialmente, la ameba se las arregla para encontrar por sí misma una solución casi óptima en no tanto tiempo (linealmente). No es, obviamente, mejor que un ordenador y su método ni siquiera es el más efectivo (por no hablar de que ocho es un número muy reducido), pero les ha resultado llamativo para un pequeño ser vivo de ese tipo.

Dicen que estudiando «cómo se las apaña» se podría pensar en encontrar por el mismo método soluciones razonables a problemas del mismo tipo, por ejemplo a robots que deben ir aprendiendo movimientos o en ciertos otros problemas computacionales del mismo estilo.

(¡Gracias @ARC por la pista!)

Compartir en Flipboard Compartir en Facebook Tuitear

PUBLICIDAD

Microsiervos Selección


La Información

EUR 23,65 (Reseña en Microsiervos)

Comprar


Viajar en el tiempo

EUR 12,34

Comprar


Programming The Universe

EUR 9,72 (Reseña en Microsiervos)

Comprar


Amazon Associates

Los productos aquí enlazados están a la venta en Amazon. Incluyen un código de Afiliado Amazon Associates que nos cede un pequeño porcentaje de las ventas. Los productos están seleccionados por los autores del blog, pero ni Amazon ni los editores de los libros o fabricantes de los productos participan en dicha selección.

Más libros y productos en:

Microsiervos Selección