Tai chi

Problema del viajante


Si un viajante parte de la ciudad A y las distancias a todas las demás ciudades son conocidas, ¿cuál es la ruta óptima que debe elegir para visitar todas las ciudades yvolver a la ciudad de partida?.
El problema del viajante o problema del vendedor viajero1 (en inglés T.S.P., Travelling Salesman Problem) es un ejemplo que muestra y analiza la problemática que subyacetras algunos tipos de problemas matemáticos que a priori parecen tener una solución relativamente sencilla, y que en la práctica presentan un gran problema. Es uno de los problemas más famosos en elcampo de la optimización combinatoria computacional.
Se conoce la forma de resolverlo pero sólo en teoría, en la práctica la solución no es aplicable debido al tiempo que computacionalmente se precisapara obtener su resultado (Véase también NP-completo).
Índice [ocultar]
1 Enunciado
2 Situación actual respecto de su resolución
2.1 Casuística
3 Convergencia del problema
4 Aplicaciones
5Véase también
6 Referencias
Enunciado[editar]

Sean N ciudades de un territorio. El objetivo es encontrar una ruta que, comenzando y terminando en una ciudad concreta, pase una sola vez por cada unade las ciudades y minimice la distancia recorrida por el viajante. Es decir, encontrar una permutación tal que sea mínimo. La distancia entre cada ciudad viene dada por la matriz D: NxN, donde d[x,y] representa la distancia que hay entre la ciudad X y la ciudad Y.
La solución más directa es la que aplica la fuerza bruta: evaluar todas las posibles combinaciones de recorridos y quedarse conaquella cuyo trazado utiliza la menor distancia. El problema reside en el número de posibles combinaciones que viene dado por el factorial del número de ciudades (N!), y esto hace que la solución porfuerza bruta sea impracticable para valores de N incluso moderados, con los medios computacionales actualmente a nuestro alcance. Por ejemplo, si un ordenador fuese capaz de calcular la longitud de...