Reducción de blob calcula soluciones de vendedor ambulante

El problema del viajante es uno de los retos más famosos de las matemáticas. Este es el problema de encontrar la ruta más corta para visitar varias ciudades una vez y luego regresar al lugar de origen.

Por supuesto, es sencillo encontrar rutas que visiten cada ciudad de esta manera. El gran desafío es encontrar el más corto.

Hay una forma segura de hacer esto: por pura fuerza bruta. Eso significa medir la duración de cada recorrido y determinar cuál es el más corto. El problema es que esta tarea se vuelve cada vez más larga a medida que aumenta el número de ciudades. De hecho, para un gran número de ciudades, es computacionalmente inviable.

Es fácil imaginar que podría haber algún tipo de atajo matemático inteligente que resuelva este problema. No tan. De hecho, los matemáticos tienden a estar de acuerdo en que nunca se encontrará un atajo general (este es el llamado debate P = NP).

En su lugar, tienen que depender de procesos de optimización que buscan soluciones breves, pero no pueden demostrar que sean las más breves.

Entonces, el desafío para todos los propósitos prácticos es encontrar algoritmos que produzcan buenos resultados y que sean computacionalmente eficientes.

Hoy, Jeff Jones y Andrew Adamatzky de la Universidad del Oeste de Inglaterra en el Reino Unido revelan un enfoque inusual. Estos muchachos dicen que se puede encontrar una solución razonable representando las ciudades como una serie de puntos en una placa de Petri virtual, sumergiendo los puntos en una mancha de sustancia viscosa virtual y luego encogiendo la mancha.

En términos simplificados, la mancha se adhiere a los puntos a medida que se encoge, uniéndolos con una superficie mínima, como la superficie de una burbuja de jabón. A medida que la mancha se encoge, morfológicamente se adapta a la configuración de las ciudades, dicen.

Cuando todos los puntos se asientan en la superficie de la mancha, la superficie resultante es una solución al problema del vendedor ambulante que en general es bastante bueno.

El ingrediente mágico de todo esto es la sustancia viscosa especial. Consiste en muchas partículas que se mueven cada una de acuerdo con un conjunto de reglas simples, como agentes autónomos. Estos se sientan en un mar de quimioatrayentes, un aroma virtual que atrae a las partículas. En cada etapa del cálculo, cada partícula detecta el quimioatrayente a su alrededor y luego se mueve hacia la región de mayor concentración. A medida que se mueve, deja su propio rastro del quimioatrayente para que lo sigan otras partículas.

El resultado es una especie de mancha inteligente que muestra un comportamiento emergente, como la capacidad de minimizar su superficie.

Jones y Adamatzky han puesto a prueba esta sustancia inteligente al dejarla perdida en los problemas de los vendedores ambulantes que consisten en 20 ciudades distribuidas aleatoriamente en una placa de Petri virtual. Han colocado videos del proceso de encogimiento aquí .

Los resultados son buenos pero no perfectos. El creó 20 escenarios diferentes de 20 ciudades y ejecutó el blob 6 veces en cada uno. Luego compararon la ruta más corta de la mancha con la ruta más corta real encontrada por la fuerza bruta. Jones y Adamatzky dicen que si esta ruta más corta es de longitud 1, el blob inteligente encontró recorridos con una mejor duración promedio de recorrido de 1.04, una duración promedio de recorrido promedio de 1.07 y una duración promedio de peor recorrido de 1.09.

No esta mal. Pero la ventaja real está en la simplicidad del enfoque, que es esencialmente emergente y no implica procesos especiales de optimización. También produce un mapa de la ruta al final (aunque se requiere alguna interpretación humana para darle sentido).

Hay desventajas, por supuesto. Hay algunas configuraciones de ciudades que el blob no puede afrontar. Estos ocurren cuando la ruta más corta forma una especie de estrecho entre dos ciudades en lugar de una conexión, como el Estrecho de Gibraltar entre el Océano Atlántico y el Mar Mediterráneo. En cambio, la mancha tiende a conectarlos.

Sin embargo, esta es una forma interesante de computación no convencional que produce una fascinante alternativa a los algoritmos convencionales de los viajantes de comercio. Tiene la mayor semejanza con los enfoques de bandas elásticas que rodean las ciudades con una banda elástica y luego intentan estirar progresivamente la banda para conectar las ciudades en su interior. La gran diferencia es que las propiedades materiales de la gota son emergentes en lugar de preprogramadas.

Jones y Adamatzky dicen que el siguiente paso sería crear un modelo físico de este sistema en el que una mancha real hace el trabajo, quizás usando viscoelástica, minimización de energía libre. Sin embargo, diseñar un material de este tipo puede resultar complicado.

Otro enfoque, que podría tener una aplicación más amplia, sería destilar las propiedades de este cálculo no convencional en un algoritmo clásico.

Lo mejor de todo es la posibilidad de que los gerentes de logística planifiquen rutas de entrega sumergiendo modelos de redes de carreteras en depósitos de sustancia viscosa inteligente. Así que esperaremos con anticipación esta nueva ciencia de la alquimia del viajante.

Ref: arxiv.org/abs/1303.4969 : Cálculo del problema del vendedor ambulante mediante una gota que se encoge

esconder