Analice el problema del vendedor ambulante

La mente humana es un mago de la carretera. Piense en los días previos al bloqueo cuando todos hicimos varios recados en la ciudad. Siempre había un baile mental en la parte de atrás de tu cabeza para entender cómo planeaste el día. Podría ser como "primero al banco, luego dejar la tintorería. Dado que la oficina de correos está en camino a la tienda de comestibles, pasaré y enviaré esa caja que está en el maletero durante una semana".

Este tipo de gimnasia mental no es algo natural para las máquinas; en realidad, es un problema famoso en la informática conocido como el problema del vendedor ambulante. Si bien se clasifica en la industria como un problema NP-difícil en la optimización combinada, una definición más concisa y comprensible sería: dada una lista de destinos, ¿cuál es la mejor manera de ir y quién va a visitar cada lugar?

Este verano trajo la noticia de que se había roto el récord de 44 años para resolver el problema. Veamos por qué este es un problema difícil y cómo el equipo de investigación de la Universidad de Washington ha adoptado un enfoque diferente para lograr la velocidad.

La ciencia de venir de aquí para allá

El problema del vendedor ambulante (o TSP para abreviar) fue uno de los problemas más estudiados en la informática. Fue considerado por primera vez en el siglo XIX por los matemáticos WR Hamilton y Thomas Kirkman. A pesar de lo que pueda pensar, en realidad tiene aplicaciones fuera del sistema de navegación GPS de su teléfono inteligente. Lo que se puede modelar como un TSP incluye todo, desde el diseño de los ASIC, los planos de las rutas de los autobuses escolares, el orden de los agujeros de perforación para los PCB, hasta la secuencia de ADN. La "distancia" entre puntos podría significar distancia física o similitud entre genes.

En la década de 1930, Karl Menger, un matemático nacido en Austria que fue profesor invitado en Harvard y Rice aproximadamente al mismo tiempo, consideró la solución de la fuerza bruta, que simplemente considera todos los caminos posibles. Este enfoque se vuelve terriblemente difícil rápidamente porque solo 15 ubicaciones diferentes dan 1,307,674,368,000 rutas diferentes para calcular (es decir, 15 factores). Como puede imaginar, escalar a cientos o miles de destinos diferentes rápidamente se vuelve irresistible. Exactamente alrededor de 60 destinos diferentes dan aproximadamente el mismo número de rutas posibles que el número de partículas estimadas en el universo. Y así nació un clásico desafío informático.

Hay varias versiones diferentes del TSP, como límites métricos, euclidianos, asimétricos y más específicos de la casa, como agregar costos al viajar por diferentes rutas, además de las distancias en sí mismas. Esto conduce a una distinción entre el TSP sin marcar y sin marcar.

Nuestros talentos únicos

Curiosamente, la gente es lo suficientemente inteligente como para resolver la versión euclidiana del problema. Las personas pueden lograr una solución casi perfecta cercana al tiempo lineal incluso en casos con más de 120 destinos. La facilidad con la que podemos lograr esta hazaña ha fascinado a varios psicólogos cognitivos y ha dado lugar a decenas de estudios y artículos sobre el tema. De hecho, esta misma habilidad se ha demostrado en palomas y bacterias que cambian de forma.

La hipótesis actual es que las personas tienen varias heurísticas o abreviaturas que las hacen muy inteligentes para satisfacer, un término acuñado por Herbert A. Simon que simplemente significa llegar a una decisión "bastante buena". La mayor parte de lo que hacen las computadoras es calcular una respuesta específica y verificable. Está bien o mal sin lugar entre ellos. Es mucho más fácil llegar a la solución perfecta que definir qué es lo suficientemente bueno dado el contexto actual.

Las soluciones aproximadas

En este sentido, los científicos de la computación durante el último medio siglo han refinado y aplicado nuevas técnicas y aproximaciones que las computadoras pueden usar para adivinar el camino hacia una mejor solución. Técnicas como la programación dinámica podrían hacer que el número de rutas cuente hasta n22n o 7.372.800 rutas posibles para 15 destinos, mucho menos de un billón. Los algoritmos de rama y enlace pueden hacer esto aún más bajo, pero hasta ahora no se ha demostrado que exista un algoritmo perfecto que evalúe menos de 2n rutas.

En este artículo publicado en 1997 se propuso modelar colonias de hormigas que utilizan vías de feromonas para crear consenso para una vía más corta.

Esto sigue siendo en gran medida irrazonable para bases de datos más grandes, por lo que fue necesario resolver soluciones aproximadas en lugar de perfectas. Heurísticas como Next Neighbor, que simplemente va al destino no visitado más cercano, la búsqueda aleatoria por cadenas de Markov e incluso la simulación de colonias de hormigas son todas soluciones que se utilizan para producir soluciones aproximadas. Sin embargo, incluso el mejor de estos algoritmos solo puede garantizar que su solución será un 50% más larga que la solución perfecta.

Razor Thin Improvement vale más que su valor nominal

Si bien vimos hardware lanzado al TSP en ambos aceleradores personalizados y también en la cantidad de núcleos que trabajaban en el problema, no había algoritmos capaces de romper ese número del 50%. Hasta el reciente artículo preliminar publicado por Anna Karlin, Nathan Klein y Shayan Gharan sobre una nueva técnica que ofrece una ligera mejora para la versión métrica del TSP. La mejora simplemente reduce del 10 al 34 de ese 50%. Tal vez eso no parezca mucho y se puede argumentar que es tan pequeño que no les importa a todos, excepto a las bases de datos más grandes.

Sin embargo, la clave es que demostró matemáticamente que la mejora es y es posible. El récord de los últimos 44 años se ha roto y los autores del periódico esperan que inspire a otros. Un éxito similar ocurrió en 2011 cuando el caso gráfico del TSP experimentó una ligera mejora. Este pequeño refinamiento inspiró a otros investigadores que desarrollaron algoritmos reestructurados. Lo que comenzó como un simple aumento eventualmente llevó a romper la barrera del 50% al 40% para el caso gráfico.

La desventaja aquí es que los problemas se pueden resolver. Incluso los problemas que parecen haber llegado a un límite no tienen solución. Es agradable descubrir que los problemas de 44 años todavía prestan un poco de atención, arrastrando el estado del arte con ellos cuando nuevos ojos encuentran enfoques inesperados.

• Douglas Coulter dice:

  Demonios, todavía estoy esperando la solución previa general al problema de los 3 cuerpos. En mi caso, no me importa dónde estará Júpiter en 100 años a un pie.
  Pero me preocupa mucho poder modelar eficazmente el comportamiento de moléculas individuales en un fluido.
  Más específicamente, se aplicaron los iones en plasma con tal campo y gradiente.
  Las matemáticas existentes no lo llevan allí (un conjunto similar de problemas) y aquí, tenemos "gravedad" con ambas polaridades y diferentes valores de g (relación carga / masa).

  Acelerar un plasma más o menos coherente (flujo laminar) nos daría una fusión impulsada electrostáticamente con una ganancia, solo para expulsar algo de orientación del objetivo. Es una especie de mi pasatiempo. Al no desperdiciar energía poniéndola en falsos grados de libertad (como simplemente calentar las cosas y esperar que algunas colisiones se enfrenten entre sí), actúas mucho mejor, otras pérdidas también son mucho menos altas.

  Y sí, he hablado con los proveedores que hacen varios tipos de software de simulación física (no es barato pero ...), y básicamente dijeron "ahorre su dinero", es un problema de clase sobre "la muerte caliente del universo". . hacerlo con los habituales errores matemáticos y perturbadores te mataría de todos modos mientras repites, como decirme dónde estará Júpiter con los mismos métodos.

  Los experimentos de corte y prueba muestran que hay posibilidades, pero la cantidad de cosas que se pueden demostrar, incluso con el mejor simulador, la realidad en sí al menos funciona en tiempo real y es realmente precisa, es tan alta que es ridículo. Se necesita algo de tiempo para construir cada diseño.

  Las matemáticas fueron la reina de las ciencias. Ya no es así. Simplemente no se rompió: si me das un material y sé algunas cosas sobre las moléculas que lo componen (y cualquier estructura interna de los metamateriales), puedo usar las matemáticas existentes para contarte casi todo lo interesante sobre ese material.
  Pero NADA me permite insertar "Necesito estas características dentro de ciertas tolerancias" y decirme "así es como hacer eso con lo que está en la tabla periódica". Por ejemplo, tenemos reacciones, pero no un prólogo para muchas matemáticas científicas existentes. .

  • Anónimo dice:

    Pero matemáticamente se ha demostrado que el problema de n cuerpos para n> = 3 no acepta una solución analítica, mientras que el TSP es un problema NP-difícil del cual aún no estamos seguros de si existe una solución de tiempo P (que depende de P = NP, lo que probablemente no sea cierto).

• Anónimo dice:

  Por supuesto, la respuesta obvia debe incluir algo para que eventualmente los recursos informáticos lleguen al problema. Entiendo vagamente el concepto de computadoras cuánticas, por lo que tal vez este sea un medio aplicable para resolver este "rompecabezas" (en solo 64 KB de memoria).

• JNiccum dice:

  El problema del vendedor ambulante se ha estudiado repetidamente hasta la muerte. Recuerdo que mi profesor dio un ejemplo de fábrica de PCB sobre esto para minimizar la distancia del CNC entre los orificios de perforación de los componentes. Teniendo esto en cuenta, la formulación de los problemas sigue siendo competencia de las personas. Además, no olvide que con creatividad puede revertir el problema y encontrar una solución que lo elimine por completo, como cambiar de un orificio a componentes de montaje en superficie.

• Ren dice:

  Hablando de urracas,
  ¿No tienen los córvidos un cerebro realmente bueno para resolver problemas como el TSP?

• Jon dice:

  En una vida anterior yo era un mensajero de fedex, y el problema de las ventas itinerantes se resolvía tres veces al día (antes de las 10:30, el resto de las entregas, camiones) y tenía que incluir cosas como eficiencias adicionales para los flujos de tráfico normales, además al tiempo que permite puentes elevadores, paradas adicionales, barreras semipermeables y tiempo para las conexiones de los clientes en cada parada. La distancia también importaba menos que el tiempo.

  Quizás lo que hace que esto sea imposible para las computadoras y el pastel para los humanos es el contexto que le brindamos. Tantas cosas fuera del problema informan la solución, y luego, cuando se nos pide que realicemos el problema del vendedor ambulante en sí, ocupamos el arte y el lado dinámico fluido del problema en lugar de simples cálculos de distancia, pero luego limitamos nuestras fórmulas a lo menos útil. base de datos.

  Es inspirador avanzar en el TSP. Puede haber algún pensador inspirador que pueda expulsar de manera confiable más de un porcentaje total basado en la aplicación de soluciones de otro departamento. ¡Ve a las matemáticas!

  • Jon dice:

    [B2]

    • Kaz dice:

      ¡Hundiste mi acorazado!

  • C32 dice:

    En ese caso sabrás que merece la pena planificar la ruta, así que tienes que hacer el giro a la izquierda más pequeño ...
    La razón es notablemente simple: conducimos por la derecha de la carretera, por lo que al girar a la derecha, solo tiene que obtener un espacio para ingresar al tráfico desde la izquierda, mientras que girar a la izquierda necesita un lugar en ambas carreteras, lo que cuesta más tiempo ...

• chico jablonski dice:

  Recuerdo un problema similar al TSP que tuve que resolver en el
  inicio de mi carrera profesional este fue el siguiente:

  Dada una lista de objetos en el cielo (estrellas) que tenías que observar uno tras otro
  durante la noche; cuál sería el mejor orden de las observaciones para garantizar
  que cada uno se observó lo más cerca posible de una intersección de meridiano (minimizar
  efectos refractivos atmosféricos). Los objetivos se extendieron por todo cielo
  esfera. Recuerde, los objetivos se mueven con respecto al meridiano por la noche,
  mientras la Tierra está girando, y tienes que pasar un período de tiempo (decenas de minutos)
  observando cada objeto.

  Lo resolví con el mismo enfoque que alguien mencionó para el problema de enrutamiento de PCB:
  crear una figura de mérito (en mi caso, la distancia más corta a un meridiano) e intentar, por
  método de optimización de calcina simulado el "mejor" camino entre los objetivos. Delaware
  por supuesto, era una solución dinámica, en el sentido de que tenías que actualizar a la mejor
  ir cada 30 minutos aproximadamente. Funcionó bastante bien en comparación con los resultados obtenidos.
  de observadores que utilizaron solo el coraje para elegir qué próximo destino visitar.

  • Ren dice:

    ¿Te refieres al maratón más desordenado?

• MH dice:

  Creo que hay un error en la conexión con las "bacterias" que cambian de forma.
  El organismo mencionado en este artículo es Physarum polycephalum (moho viscoso, que es un protista, que son eucariotas, tienen una membrana nuclear).
  Mientras que las bacterias son procariotas, carecen de membrana nuclear.

• Un hombre viejo dice:

  "El número de partículas estimadas" ¿Cuál es la diferencia entre una partícula estimada y una normal?

  • Jon dice:

    En teoría, son en promedio 1: 1

• jafinch78 dice:

  Interesante lectura de nuevo. Han pasado una década y casi dos. https://eo.wikipedia.org/wiki/Travelling_salesman_problem

  Recuerdo haber aprendido sobre el algoritmo de Dijkstra al mismo tiempo.

  https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

• codificación posterior a la hora dice:

  Me recuerda el momento en que para un proyecto escolar intentamos contrarrestar la solución en una GPU.
  La fuerza bruta de TSP se puede hacer fácilmente porque un cálculo de cada solución posible se puede realizar de forma independiente en el núcleo de la GPU.
  Cuantos más núcleos (GPU), más caminos pueden ser difíciles por la repetición.

  Al final, cualquier algoritmo decente supera fácilmente cualquier enfoque de fuerza bruta porque reduce drásticamente el número total de rutas que debe considerar. Aprobado para aquellas personas que se acercan a lo imposible.