¿Has usado un algoritmo de vendedor ambulante para resolver un problema?

Question

Estudié TSP en la universidad en el contexto de NP Completeness. Nunca he tenido una situación en la que se aplique a un problema práctico. Un poco de investigación muestra que se ha utilizado para elegir el camino más barato para mover un taladro, es decir, hacer agujeros en las placas de circuito. Eso es todo lo que pude encontrar.

¿Lo está usando? ¿Qué otras aplicaciones prácticas tiene la TSA?

Answer 1

Como con otros en este hilo, construí una solución para un problema completo de NP en la universidad (era un proyecto paralelo para un amigo): un programa de programación. En el momento en que acepté trabajar en su problema, no sabía qué era NP completo. Más tarde me di cuenta de que había encontrado algunas heurísticas bastante buenas para resolver el problema, pero, por supuesto, el verdadero truco era saber cuándo decirle al usuario que no había solución y que habían sobrecargado el problema.

Fue una gran manera de reunir mis eventuales clases teóricas y el mundo real.

De nuevo, la heurística y "lo suficientemente cerca" generalmente son buenas para usos del mundo real donde se prefieren soluciones casi óptimas debido al costo de encontrar e implementar la solución ideal.

Answer 2

Nunca lo he usado personalmente, pero otra aplicación además de taladrar placas de circuitos es si desea ir a una serie de lugares diferentes, por ejemplo para vender aspiradoras. Podría utilizar una solución del problema para decidir la manera más económica de visitar todas partes exactamente una vez.

Answer 3

Saber cuándo un problema es NP-hard es útil para excluir las soluciones que implican la solución de ese problema. Cada vez que vea que TSP (o cualquier otro problema de NP-hard) está detrás de su cabeza fea para problemas de tamaño no trivial, sepa que se está dirigiendo por el camino equivocado. No solo lo sabe, sino que sabe por qué, y puede decirle con confianza a su jefe/compañero de equipo/a cualquier persona.

Dicho http://en.wikipedia.org/wiki/CONCORDE revela que:

Concorde se ha aplicado a problemas de mapeo de genes, [1] la función de proteínas predicción, [2] de rutas para vehículos, [3] conversión de imágenes de mapa de bits a dibujos lineales continuos, [4] programación de movimientos de embarcaciones para estudios sísmicos , [5] y al estudiar las propiedades de escalamiento de los problemas combinatorios de optimización . [6]

Answer 4

Sí, lo uso en la aplicación Geocaching para la planificación de rutas.

Actualmente utiliza una distancia en línea recta entre los puntos, pero debería hacerlo correctamente (cuando lo encuentre) utilizar las carreteras para calcular las distancias entre los puntos.

http://code.google.com/p/gpsturbo/

Answer 5

Muchos tipos de pedidos optimizado, tales como recogida piscina del coche, entrega de paquetes de UPS, etc. donde los requisitos de recorrido de nodos puede ser expresada en una dimensión de esfuerzo, tales como el tiempo o la distancia.

Answer 6

Una vez me dieron la tarea de escribir un programa para rellenar un área rectangular bastante uniformemente con un "garabato", una línea curva que no se interseca por sí misma. Mi primer intento fue generar puntos aleatorios dentro del rectángulo y tratar de encontrar un recorrido por ellos (no necesariamente el más corto absoluto). Desafortunadamente, este enfoque no funcionó muy bien y lo abandoné.

hice resolver el problema en el final, sin embargo:

Mi método exitoso no estaba relacionada con el TSP, pero para los curiosos Lo resumiré:

de inicio con una sola línea segmento. Ahora bucle: si una línea es "demasiado larga", divídala en dos. Mueva cada punto un poco al azar, pero haga que los puntos se repelan entre sí. Termine el ciclo cuando se puede hacer poco progreso. Hay detalles, pero espero que entiendas la idea.

Por supuesto, esto produce una trayectoria angular (que hubiera sido aceptable) pero es fácil convertir las esquinas en arcos suaves.

Y sí, guardé el código.

Answer 7

¿No utilizaría Google Maps (y cualquier otro software de enrutamiento basado en mapas) algún tipo de vendedor ambulante para resolver las instrucciones de manejo?

Answer 8

No he usado TSP hasta donde sé, pero he trabajado en varios robots autónomos para atravesar un laberinto. Entonces me pregunto si TSP podría aplicarse a la resolución de laberintos.

Answer 9

La mayoría de las veces no desea utilizar un algoritmo que resuelva el problema NP-Complete/Hard. Solo quieres un algoritmo que sea "lo suficientemente bueno". Por lo general, se basan en la heurística y proporcionan aproximaciones razonables.

Tuve un problema que era una instancia de Independent-Set (NP-Complete), pero encontré un algoritmo codicioso que dio muy buenos resultados en la gran mayoría de los casos, y tuvo un tiempo de ejecución eficiente.

Answer 10

Pocos problemas en la vida real coinciden con las cosas que aprendes en la clase de matemáticas. Los problemas se simplifican y abstraen para que pueda ver las matemáticas y no distraerse con los detalles. El mejor ejemplo de la vida real de grandes TSP, como usted mencionó, en realidad no involucra a ningún vendedor ambulante: se trata de máquinas de programación que tienen trabajos para realizar con sequence-dependent setup times. Eso incluye máquinas donde un brazo mueve una herramienta alrededor de diferentes sitios, y también algunas aplicaciones de pintura (rojo-> naranja-> amarillo es más fácil que rojo-> amarillo-> naranja). También hay algunas aplicaciones en x-ray crystallography donde tiene que orientar algunas muestras de un cristal en diferentes ángulos.

Answer 11

Esta empresa se basó en un algoritmo TSP mejorado.

http://www.pointserve.com/

Ellos cable ruta instaladores y reparadores de televisión por Nueva York, entre otros problemas.

Answer 12

Debido a que los humanos pueden resolver problemas de TSP a la par o mejor que la mayoría de los algoritmos para mapas con 20-60 nodos, no es muy común que una computadora resuelva el problema. Cuando el costo es lo suficientemente alto, lograr que la computadora obtenga una mejora del 1-2% sobre un humano puede valer la pena el costo de realizar el cálculo. Si la ruta no cambia, entonces uno puede justificar pasar algún tiempo optimizándola. Esto es común en el diseño de circuitos integrados.

Los sitios web de viajes en aerolíneas usan una versión especializada del problema TSP cuando le muestran una lista de aerolíneas y los precios de cada ruta. La diferencia es en lugar de la distancia, optimizan el costo, ¡y ciertamente no es necesario visitar cada ciudad una vez! Digamos que quiere volar de LGA a LAX.Hay aproximadamente media docena de rutas directas, y una cantidad infinita de otras rutas. Puede sugerir LGA-> ORD-> LAX o LGA-> DWF-> LAX. Los seres humanos, que pueden establecer manualmente precios de rutas, a veces pueden encontrar tarifas más bajas que las que buscan los sitios de viajes. Normalmente, las personas no desean más de dos conexiones, pero no existe un límite superior para la cantidad de conexiones para un vuelo determinado.

Lo he usado para resolver rutas para mi Travelling Salesman iPhone Game. Lo interesante es que las personas son muy buenas para resolver la ruta más corta, pero no para resolver la ruta más larga. Las rutas más largas y más cortas tienen la misma complejidad, pero las personas parecen estar capacitadas para poder encontrar las rutas más cortas, a menudo más rápidas y mejores que las que puede hacer una computadora.

Answer 13

En mi primer trabajo creamos una aplicación de programación de atención domiciliaria.
Resolvimos el problema TSP con algunas restricciones de tiempo no lineales y con una función de costo no lineal adicional.
Utilizamos un solucionador no óptimo para resolver el problema.

Answer 14

TSP es el hello world de problemas completos de NP. En su forma canónica pura, que no lo encontrará en la naturaleza a menudo (demos like this one not included), pero un gran subconjunto de NP problemas completas están relacionados o incluso sobre la base de TSP, tales como:

• Vehicle routing (incluye camión de suministro enrutamiento)
• aerolínea/Vuelo de enrutamiento
• tren de enrutamiento
• esquí máquina de arado pendiente de enrutamiento

Cada uno de ellos tiene, limitaciones específicas de dominio adicionales, que les hacen h para resolver Por lo tanto, TSP es una buena introducción a los problemas completos de NP, para comprender su naturaleza.