Problema del viajante

2. Desarrollo del tema
2.1. Introducción
El Problema del Viajante, también conocido como Tavelling Salesman Problem
(TSP) es uno de los más famosos problemas en el campo de la optimizacióncombinatoria computacional y ha habido numerosos estudios sobre él. El primero de
estos estudios, realizado por el matemático irlandés Sir William Rowan Hamilton en el
siglo XIX junto con el británicoThomas Penyngton Kirkman, buscaba la solución de un
juego planteado por el señor Hamilton en el que se buscaba encontrar ciclos completos
entre 20 puntos usando unas aristas indicadas. Tuvo que pasarmás de un siglo para que
se empezara a buscar la solución general del problema del viajante, concretamente, el
primer estudio se realizo en la década de los 30 por Karl Menger, y, desde entonces,otros muchos matemáticos han intentado su resolución sin éxito.
El enunciado del problema tratado es el siguiente: “Un viajante de comercio ha de
visitar n ciudades, comenzando y finalizando en supropia ciudad. Conociendo el
coste de ir de cada ciudad a otra, determinar el recorrido de coste mínimo.”
Podemos plantearlo en términos de grafos de manera que debemos hallar el ciclo
hamiltoniano delgrafo completo ponderado (con pesos en las aristas) Kn. Entenderemos
por ciclo hamiltoniano aquel que debe pasar contener a todos los vértices del grafo
exactamente una vez y por ciclo euleriano elque contiene todos los vértices
exactamente una.
Una de las soluciones es la denominada Fuerza bruta que consiste en probar
todos los ciclos posibles y quedarse con el de menor peso. Es fácil decalcular el número
de las diferentes formas posibles de recorrer n ciudades: Dado una ciudad de partida,
tenemos n-1 elecciones para la segunda ciudad, n-2 elecciones para la tercera, etc.Multiplicando estas juntas, obtenemos (n-1)! = n-1·n-2·n-3·....3·2·1. Ahora bien
nuestros gastos en viajes no dependen de la dirección que tomemos en la ruta, luego
debemos dividir este número entre 2, de...