Problema del viajante

Este es un problema NP-Hard dentro en la optimización combinatoria, muy importante en investigación operativa y en ciencias de la computación.Aunque el problema es computacionalmente complejo, se conoce gran cantidad de heurísticas y métodos exactos, así que es posible resolver planteamientos concretos del problema desde cien hasta miles de ciudades.El TSP tiene diversas aplicaciones aún en su formulación más simple, tales como: la planificación, la logística y la fabricación de circuitos electrónicos.[2]​ Todo parece indicar que la forma general del TSP fue estudiada, por primera vez por matemáticos en Viena y Harvard, durante los años 1930s.En la práctica, para un problema del viajante con 5 ciudades hay (5-1)!/2=12 rutas diferentes y no necesitamos un ordenador para encontrar la mejor ruta, pero apenas aumentamos el número de ciudades las posibilidades crece factorialmente: Puede comprobarse que por cada ciudad nueva que incorporemos, el número de rutas se multiplica por el factor N y crece factorialmente.En el ‘’’TSP simétrico’’’, la distancia entre un par de ciudades es la misma en cada dirección opuesta, formando un grafo no dirigido.En el ‘’’TSP asimétrico’’’, pueden no existir caminos en ambas direcciones o las distancias pueden ser diferentes, formando un grafo dirigido.Por ejemplo, no ha sido determinado si existe un algoritmo para el TSP que corra en un tiempo de orden[18]​ Otras aproximaciones incluyen: Una solución exacta para 15,112 pueblos alemanes desde TSPLIB fue encontrada en 2001 usando el método de planos cortantes propuesto por George Dantzig, Ray Fulkerson, y Selmer M. Johnson en 1954, basados en la programación lineal.En abril de 2006, una instancia con 85,900 puntos fue resuelta usando ´´Concorde TSP Solver´´, tomando 136 años- CPU, vea Applegate et al.Varios algoritmos heurísticos y aproximados que retornan rápidamente buenas soluciones han sido creados.Métodos modernos pueden encontrar soluciones para problema extremadamente largos (millones de ciudades) en un tiempo razonable.[5]​ Varias categorías de heurísticas son reconocidas: El Algoritmo del vecino más próximo (NN por sus siglas en inglés) o también llamado algoritmo voraz (greedy) permite al viajante elegir la ciudad no visitada más cercana como próximo movimiento.[20]​ Sin embargo, existen muchos casos donde la distribución de las ciudades dada hace que el algoritmo NN devuelva el peor camino (Gutin, Yeo, and Zverovich, 2002).Match Twice and Stitch (MTS) (Kahng, Reda 2004[22]​), es otra heurística constructiva, que realiza dos comparaciones secuenciales (matchings), donde el segundo macheo es ejecutado después de eliminar todas las aristas del primer macheo, retornando un conjunto de ciclos.ACS envía un gran número de hormigas (agentes virtuales) para explorar las posibles rutas en el mapa.En el “TSP métrico”, también conocido como delta-TSP o Δ-TSP, las distancias entre las ciudades satisfacen la Desigualdad triangular.La métrica Manhattan corresponde a la máquina que ajusta a una máquina que ajusta en primer lugar, la primera coordenada y luego la otra, así el tiempo de movimiento al nuevo punto es la suma de ambos movimientos.El primer ejemplo publicado (y el más simple) es el siguiente: Es fácil probar que el último paso funciona.Como un hecho importante se tiene que, el término "algorithm" no fue comúnmente extendido a algoritmos de aproximación hasta más adelante el algoritmo Christofides fue inicialmente referido como la Heurística Christofides.En general, para cualquier c > 0, donde d es el número de dimensiones en el espacio Euclidiano, existe un algoritmo polinomial que encuentra un camino de longitud a lo sumo (1 + 1/c), el óptimo para instancia geométricas del TSP se da en tiempo; este es llamado un esquema de aproximación a tiempo polinomial (PTAS por sus siglas en inglés).Sanjeev Arora y Joseph S. B. Mitchell se adjudicaron el Premio Gödel en 2010 por el descubrimiento de un PTAS para el TSP Euclidiano.En la mayoría de los casos, la distancia entre dos nodos en red del TSP es la misma en ambas direcciones.Evaluando la versión simétrica de 6×6, el mismo problema ahora produce más caminos, incluyendo A-A′-B-B′-C-C′-A, A-B′-C-A′-A, A-A′-B-C′-A [todos los costos 9 – ∞].En los dos ejemplos anteriores, no existen caminos entre los nodos, estos son mostrados con el espacio en blanco.El RSP, en particular la variante Euclidiana del problema, atrae la atención de los investigadores en Psicología cognitiva.Estos observan que los humanos son capaces de producir rápidamente buenas soluciones.Es un límite inferior obtenido por asumir iun punto en la secuencia e i tiene como próximo vecino el último en el camino.Este es un problema análogo en la teoría de las medidas geométricas la cual presenta la siguiente interrogante: ¿Bajo qué condiciones puede un subconjunto E del espacio Euclidiano contener en una curva rectificable (esto es, cuando una curva con longitud finita visita todos los puntos en “E”)?