Diferencia entre revisiones de «Problema del viajante»

30 bytes añadidos ,  hace 2 años
Añadido qué significan las siglas TSP
(Añadido qué significan las siglas TSP)
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 operaciones y en la [[Ciencias de la computación |ciencia 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, una gran cantidad de [[Heurística|heurísticas]] y métodos exactos son conocidos, de manera que, algunas instancias desde cien hasta miles de ciudades pueden ser resueltas.
206

ediciones