El problema del Vendedor Viajero

El problema del agente viajero, consiste en un agente de ventas que tiene que visitar n ciudades, comenzando y terminando en una misma ciudad, visitando solamente una vez cada ciudad, excepto el origen y realizar el recorrido mínimo, este recorrido puede estar en función del tiempo o de la distancia, es decir, recorrer el mínimo de kilómetros o realizar el menor tiempo posible.

El problema del agente viajero se puede modelar fácilmente como un grafo completo dirigido, en donde los vértices del grafo son las ciudades y las aristas son los caminos, dichas aristas deben tener un peso, y este peso representa la distancia que hay entre dos vértices que están conectados por medio de dicha arista, las aristas tendrán valores entre 1 y 100 Km.

Una solución del problema del agente viajero, se puede representar como una secuencia de n+1 ciudades, en donde se comienza y se termina con la misma ciudad:

Solución = 0, 1, 2, 3, 0

La anterior es una de las posibles soluciones que hay para una instancia del problema con 4 ciudades.

A continuación se presenta un problema ejemplo:

Como se podrá apreciar en el grafo anterior existen 4 ciudades, y los caminos entre cualquier par de ciudades son bidireccionales, sin embargo, los caminos no tiene la misma distancia en ambos sentidos, tomemos como ejemplo las ciudades 3 y 2, etiquetadas con un 5/9, el primer digito corresponde a la distancia de ir de la ciudad 2 a la 3, es decir, 5 kilómetros; y el segundo digito corresponde a la distancia de ir de la ciudad 3 a la 2, es decir, 9 kilómetros.

Dicho de otra manera, los pares de distancias que marcan las aristas en el grafo están asignados de la siguiente manera:

• El primer número del par correspondiente a la distancia de ir de la ciudad menor a la ciudad mayor.
• El segundo número corresponde a la distancia de ir de la ciudad mayor a la ciudad menor.

El problema de entrada estará dado en forma de una matriz de adyacencia, es decir:

• No existe un camino entre una ciudad y ella misma, y se marca con un cero.
• La columna 1 son las ciudades de origen.
• La fila 1 son las ciudades de destino.
• La intersección entre ciudad origen y destino es la distancia de ir de la ciudad origen a la ciudad destino.
• La ciudad inicial-final siempre será la ciudad cero, en ella se iniciará y se terminará el recorrido total.

La solución al ejemplo anterior es: Camino: 0 – 1 – 3 – 2 – 0 Recorrido: 38 Km