Problema del viajante
El Problema del Vendedor Viajero (a menudo llamado TSP) es un problema algorítmico clásico en el campo de la informática y la investigación operativa. Se centra en la optimización. En este contexto, una solución mejor suele significar una solución más barata, más corta o más rápida. El TSP es un problema matemático. La forma más fácil de expresarlo es como un gráfico que describe la ubicación de un conjunto de nodos.
El problema del viajante de comercio fue definido en el siglo XIX por el matemático irlandés W. R. Hamilton y por el matemático británico Thomas Kirkman. El Juego Icósico de Hamilton era un rompecabezas recreativo basado en encontrar un ciclo hamiltoniano. La forma general del TSP parece haber sido estudiada por primera vez por matemáticos durante la década de 1930 en Viena y en Harvard, especialmente por Karl Menger. Menger define el problema, considera el algoritmo obvio de fuerza bruta y observa la no optimización de la heurística del vecino más cercano:
Denotamos por problema del mensajero (ya que en la práctica esta cuestión debería ser resuelta por cada cartero, de todos modos también por muchos viajeros) la tarea de encontrar, para finitamente muchos puntos cuyas distancias entre pares son conocidas, la ruta más corta que conecta los puntos. Por supuesto, este problema se puede resolver con un número finito de pruebas. No se conocen reglas que hagan que el número de ensayos sea inferior al número de permutaciones de los puntos dados. La regla de que primero hay que ir del punto de partida al punto más cercano, luego al punto más cercano a éste, etc., en general no da la ruta más corta.
Hassler Whitney, de la Universidad de Princeton, introdujo poco después el nombre de problema del vendedor ambulante.
William Rowan Hamilton
Ruta óptima de un vendedor que visita las 15 mayores ciudades de Alemania. La ruta mostrada es la más corta de las 43.589.145.600 posibles.
Un vendedor quiere visitar todas las ciudades,A, B, C y D. ¿Cuál es la mejor manera de hacerlo (billetes de avión más baratos y tiempo de viaje mínimo)?
Planteamiento del problema
El problema del vendedor ambulante describe a un vendedor que debe viajar entre N ciudades. El orden en que lo haga es algo que no le importa, siempre que visite cada una de ellas una vez durante su viaje, y termine donde estaba al principio. Cada ciudad está conectada con otras ciudades cercanas, o nodos, por avión, o por carretera o ferrocarril. Cada uno de esos enlaces entre las ciudades tiene uno o varios pesos (o el coste) asociados. El coste describe lo "difícil" que es atravesar esta arista en el gráfico, y puede venir dado, por ejemplo, por el coste de un billete de avión o de tren, o quizás por la longitud de la arista, o el tiempo necesario para completar el recorrido. El vendedor quiere mantener tanto los costes de viaje como la distancia que recorre lo más baja posible.
El problema del viajante de comercio es uno de los problemas de optimización más difíciles que han intrigado a matemáticos e informáticos durante años. Lo más importante es que tiene aplicaciones en la ciencia y la ingeniería. Por ejemplo, en la fabricación de una placa de circuitos, es importante determinar el mejor orden en el que un láser perforará miles de agujeros. Una solución eficaz a este problema reduce los costes de producción para el fabricante.
Dificultad
En general, el problema del viajante de comercio es difícil de resolver. Si hay una manera de dividir este problema en componentes más pequeños, los componentes serán al menos tan complejos como el original. Esto es lo que los informáticos llaman problemas NP-duros.
Muchas personas han estudiado este problema. La solución más fácil (y más cara) es simplemente probar todas las posibilidades. El problema con esto es que para N ciudades tienes (N-1) posibilidades factoriales. Esto significa que para sólo 10 ciudades hay más de 180 mil combinaciones que probar (ya que la ciudad de inicio está definida, puede haber permutaciones en las nueve restantes). Sólo contamos la mitad ya que cada ruta tiene una ruta igual a la inversa con la misma longitud o coste. ¡9! / 2 = 181 440
- Se pueden encontrar soluciones exactas al problema, utilizando algoritmos de rama y límite. Esto es posible actualmente para hasta 85.900 ciudades.
- Los enfoques heurísticos utilizan un conjunto de reglas de guía para la selección del siguiente nodo. Pero como las heurísticas resultan aproximaciones, no siempre darán la solución óptima, aunque las heurísticas admisibles de alta calidad pueden encontrar una solución útil en una fracción del tiempo requerido para una fuerza bruta completa del problema. Un ejemplo de heurística para un nodo sería una suma de cuántos nodos no visitados están "cerca" de un nodo conectado. Esto podría animar al vendedor a visitar un grupo de nodos cercanos agrupados antes de pasar a otro grupo natural del grafo. Ver algoritmos de Monte Carlo y algoritmos de Las Vegas
Preguntas y respuestas
P: ¿Qué es el Problema del Vendedor Viajero?
R: El Problema del Vendedor Viajero (TSP) es un problema algorítmico clásico en el campo de la informática y la investigación operativa. Se centra en la optimización, donde mejores soluciones suelen significar soluciones más baratas, más cortas o más rápidas.
P: ¿Cómo se expresa el TSP?
R: El TSP se expresa más fácilmente como un grafo que describe las ubicaciones de un conjunto de nodos.
P: ¿Quién definió por primera vez el TSP?
R: El problema del viajante de comercio fue definido en el siglo XIX por el matemático irlandés W. R. Hamilton y por el matemático británico Thomas Kirkman.
P: ¿Quién lo estudió más a fondo durante la década de 1930?
R: Durante la década de 1930, los matemáticos Karl Menger de Viena y Harvard la estudiaron más a fondo.
P: ¿Qué introdujo Hassler Whitney poco después?
R: Hassler Whitney, de la Universidad de Princeton, introdujo el nombre de "problema del viajante de comercio" poco después de su definición.
P: ¿Qué significa "mejor solución" en este contexto?
R: En este contexto, mejor solución suele significar una solución más barata, más corta o más rápida.
P: ¿Qué algoritmo fue considerado obvio por Menger al estudiar el TSP?
R:Menger consideró obvio un algoritmo de fuerza bruta al estudiar el TSP y observó que el uso de la heurística del vecino más próximo no siempre da resultados óptimos.
