Diferencia entre revisiones de «Problema del viajante»

41 bytes eliminados ,  hace 1 año
Refraseo
m (PR:CW: Eliminando errores de sintaxis)
(Refraseo)
El '''problema del vendedor viajero''', '''problema del vendedor ambulante''', '''problema del agente viajero''' o '''problema del viajante''' ('''''TSP''''' por sus siglas en inglés (Travelling Salesman Problem)), responde a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen? Este es un problema [[NP-hard|NP-Hard]] dentro en la [[optimización combinatoria]], muy importante en la [[investigación de operacionesoperativa]] y en la [[Ciencias de la computación |cienciaciencias de la computación]].
 
El problema fue formulado por primera vez en 1930 y es uno de los problemas de optimización más estudiados. Es usado como prueba para muchos métodos de optimización. Aunque el problema es computacionalmente complejo, unase conoce gran cantidad de [[Heurística|heurísticas]] y métodos exactos, sonasí conocidos,que dees maneraposible que,resover planteamientos concretos algunasdel instanciasproblema desde cien hasta miles de ciudades pueden ser resueltas.
 
El TSP tiene diversas aplicaciones aún en su formulación más simple, tales como: la [[Planeamiento|planificación]], la [[logística]] y en la fabricación de [[circuitos electrónicos]]. Un poco modificado, aparece como: un sub-problemasubproblema en muchasmuchos áreas,campos como en la [[secuencia de ADN|secuenciación de ADN]]. En esta aplicación, el concepto de “ciudad” representa, por ejemplo: clientes, puntos de soldadura o fragmentos de ADN y el concepto de “distancia” representa el tiempo de viaje o costo, o una medida de similitud entre los fragmentos de ADN. En muchas aplicaciones, restricciones adicionales como el límite de recurso o las ventanas de tiempo hacen el problema considerablemente difícil. El TSP es un caso especial de los Problemas del Comprador Viajante (travelling purchaser problem).
 
En la [[teoría de la complejidad computacional]], la versión de decisión del TSP (donde, dadodada ununa largolongitud “L”, lael tareaobjetivo es decidir cuálqué grafo tiene un camino menor que L) pertenece a la clase de los problemas [[NP-completo|NP-completos]]. Por tanto, es probable que en el caso peor el tiempo de ejecución para cualquier algoritmo que resuelva el TSP aumente de forma [[EXPTIME|exponencial]] con respecto al número de ciudades.
 
== Historia ==
 
El origen de los problemas del agente viajeroviajante no está claro. Una guía para agentes viajerosviajantes de 1832 menciona el problema e incluye ejemplos de viajes a través de Alemania y Suiza, pero no contiene un tratamiento matemático del mismo.<ref> "Der Handlungsreisende – wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur" (El viajante — cómo debe ser y lo que debería hacer para obtener comisiones y asegurar el feliz éxito en sus negocios — por una antigua ruta comercial) </ref>
 
[[Archivo:William Rowan Hamilton painting.jpg|miniatura|William Rowan Hamilton]]
 
El problema del agente viajeroviajante fue definido en los años 1800s por el matemático irlandés [[William Rowan Hamilton | W. R. Hamilton]] y por el matemático británico [[Thomas Kirkman]]. El [[Juego Icosian]] de Hamilton fue un puzle recreativo basado en encontrar un [[Problema del ciclo hamiltoniano | ciclo de Hamilton]].<ref> Una discusión del temprano trabajo de Hamilton y Kirkman puede ser encontrado en Graph Theory 1736-1936</ref> 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. Destacándose [[Karl Menger]], quien definió los problemas, considerando el obvio algoritmo de fuerza bruta, y observando la no optimalidad de la heurística de vecinos más cercanos:
{{Quotation|
Denotamos por “Problema del Mensajero” (dado que en la práctica esta pregunta puede resolverse por cada cartero, aunque puede ser resuelta por varios viajeros) la pregunta es encontrar, para un conjunto finito de puntos de los cuales se conocen las distancias entre cada par, el camino más corto entre estos puntos. Por supuesto, el problema es resuelto por un conjunto finito de intentos. La regla que se debe seguir es que desde el punto inicial se va al punto más cercano a este, de ahí a su más cercano y así sucesivamente, en general este algoritmo no retorna la ruta más corta.<ref>Citado y traducido al Inglés en {{harvtxt|Schrijver|2005}}. Original en Alemán: "Wir bezeichnen als ''Botenproblem'' (weil diese Frage in der Praxis von jedem Postboten, übrigens auch von vielen Reisenden zu lösen ist) die Aufgabe, für endlich viele Punkte, deren paarweise Abstände bekannt sind, den kürzesten die Punkte verbindenden Weg zu finden. Dieses Problem ist natürlich stets durch endlich viele Versuche lösbar. Regeln, welche die Anzahl der Versuche unter die Anzahl der Permutationen der gegebenen Punkte herunterdrücken würden, sind nicht bekannt. Die Regel, man solle vom Ausgangspunkt erst zum nächstgelegenen Punkt, dann zu dem diesem nächstgelegenen Punkt gehen usw., liefert im allgemeinen nicht den kürzesten Weg."</ref>}}
* Las restricciones de retorno a la ciudad de comienzo no cambia la [[Teoria de la complejidad computacional | complejidad computacional]] del problema, vea [[ Problema del camino Hamiltoniano]].
 
* Otro problema relacionado es el Problema del agente viajeroviajante con cuello de botella (bottleneck TSP): Encontrar un ciclo de Hamilton en un grafo ponderado con el mínimo peso de las aristas más pesadas. El problema es de una considerable importancia en la práctica, en las áreas de la transportación y la logística. Un ejemplo clásico es en la fabricación de circuitos impresos: planificando una ruta de la máquina perforadora para perforar los huecos en un PCB. Otras son, las aplicaciones de perforado o maquinado en la robótica: las “ciudades” son los huecos de diferentes tamaños a perforar y el “costo de viaje” incluye el tiempo para reequipar el robot (problema del secuenciado del trabajo de una máquina simple).<ref>{{Citation
| last1 = Behzad| first1 = Arash| last2 = Modarres
| first2 = Mohammad| year = 2002
1803

ediciones