Problema del viajante.

LA BASE DEL PROBLEMA:

El problema del viajante es un ejemplo que muestra y analiza la problemática que subyace tras algunos tipos de problemas matemáticos que a priori parecen tener una solución relativamente fácil, y en la práctica presentan un gran problema.

La respuesta al problema es conocida, es decir 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 precisa para obtener su resultado.

El problema del viajante o también conocido como problema del viajante de comercio o por sus siglas TSP: Travelling Salesman Problem. es uno de los problemas mas famosos en el campo de la optimización combinatoria computacional.

A pesar de su aparente sencillez del planteamiento , este es uno de los mas complejos desde hace siglos.

ENUNCIADO:

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 una de las ciudades y minimice la distancia recorridad por el viajante. Es decir, encontar una permutación P={ C₀, C₂,...,Cn-₁} tal que...

sea mínimo. La distancia entre cada ciudad viene dada por la matríz D: NxN, donde d [x, y] representa la distancia que hay entre la ciudad X y la ciudad Y.