algorithm - problemas - sudoku con operaciones matematicas
¿Has usado un algoritmo de vendedor ambulante para resolver un problema? (14)
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ás usando? ¿Qué otras aplicaciones prácticas tiene la TSA?
Esta compañía se basó en un algoritmo TSP mejorado.
Enrutan instaladores y reparadores de televisión por cable alrededor de Nueva York, entre otros problemas.
¿No utilizaría Google Maps (y cualquier otro software de enrutamiento basado en mapas) algún tipo de vendedor ambulante para resolver las indicaciones de manejo?
Muchos tipos de pedidos optimizados, como la recogida de grupos de automóviles, la entrega de paquetes de UPS, etc. donde los requisitos de cruce de nodos se pueden expresar en una dimensión de esfuerzo, como el tiempo o la distancia.
Nunca lo he usado personalmente, pero otra aplicación además de taladrar placas de circuitos es si quieres ir a una cantidad 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.
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) usar carreteras para calcular las distancias entre los puntos.
Saber cuándo un problema es NP-hard es útil para excluir soluciones que impliquen resolver ese problema. Cada vez que vea que el TSP (o cualquier otro problema NP-duro) tiene su cabeza fea para problemas de tamaño no trivial, sabe 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 esto, http://en.wikipedia.org/wiki/CONCORDE revela que:
Concorde se ha aplicado a problemas de mapeo de genes, [1] predicción de función de proteínas, [2] enrutamiento de vehículos, [3] conversión de imágenes de mapas de bits a dibujos lineales continuos, [4] programación de movimientos de barcos para estudios sísmicos, [5] y en estudiando las propiedades de escala de los problemas de optimización combinatoria. [6]
Al igual que 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.
Nuevamente, la heurística y "lo suficientemente cerca" generalmente son adecuadas para usos en el mundo real donde se prefieren soluciones casi óptimas debido al costo de encontrar e implementar la solución ideal.
La mayoría de las veces no desea usar un algoritmo que resuelva el problema NP-Completo / Difícil. Solo quieres un algoritmo que sea "lo suficientemente bueno". Por lo general, se basan en la heurística y proporcionan aproximaciones razonables.
Tenía 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 que tuvo un tiempo de ejecución eficiente.
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 tiempos de configuración dependientes de la secuencia . 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 la cristalografía de rayos X en las que debe orientar algunas muestras de un cristal en diferentes ángulos.
No he usado TSP hasta donde yo 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.
Debido a que los humanos normalmente 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 de 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 juego de viajero móvil para iPhone . 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.
En mi primer trabajo, construimos una aplicación de programación de atención domiciliaria.
Solucionamos el problema de TSP con algunas restricciones de tiempo no lineales y con una función de costo no lineal adicional.
Usamos un solucionador no óptimo para resolver el problema.
Una vez me dieron la tarea de escribir un programa para rellenar un área rectangular de forma bastante uniforme 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é.
Al final resolví el problema:
Mi método exitoso no estaba relacionado con el TSP, pero para los curiosos lo resumiré:
Comience con un solo segmento de línea. 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 habría sido aceptable), pero es fácil convertir las esquinas en arcos suaves.
Y sí, guardé el código.
TSP es el mundo de los problemas completos de NP. En su forma puramente canónica, no lo encontrará en la naturaleza a menudo ( demos como este no incluidas ), pero un gran subconjunto de problemas completos NP están relacionados o incluso se basan en TSP, tales como:
- Enrutamiento del vehículo (incluye el enrutamiento del camión de suministro)
- Enrutamiento de aerolínea / vuelo
- Enrutamiento de trenes
- Ski slope arado enrutamiento de la máquina
Cada uno de estos tiene restricciones adicionales, específicas del dominio, que hacen que sea más difícil de resolver. Entonces TSP es una buena introducción a los problemas completos de NP, para comprender su naturaleza.