El Problema del Viajante

 

    El problema del Viajante (conocido a menudo por sus siglas inglesas: TSP, Traveling Salesman Problem), es un claro problema NP-Completo. Es decir, es un problema para el que no tenemos una solución algorítmica, y para el que ni siquiera sabemos si existe un método que nos dé la solución óptima.

   EL PROBLEMA DEL VIAJANTE

   El problema del viajante se describe como la búsqueda del camino más corto para recorrer N ciudades, partiendo de una de ellas y volviendo una vez hemos llegado al final.

   La forma de encontrar la solución óptima es probar todas las posibles combinaciones y quedarse con la que nos dé un camino más corto. Como todo problema de combinatoria, esta solución es ineficaz en cuanto el número de ciudades que queremos visitar aumenta un poco.

   Las redes neuronales, mediante mapas de Kohonen, obtienen una solución subóptima aceptable para el problema.

   ARQUITECTURA

   Para solucionar este problema del viajante, hemos elegido la misma arquitectura SOM que en el caso de las redes elásticas. Dos neuronas de entrada nos servirán para enseñar a la red la posición (x,y) de cada ciudad.

   N neuronas de salida irán marcando el camino a tomar. Estas neuronas están ordenadas según la topología 1D que se vio en las redes elásticas, que es más útil y flexible para este problema. El número N depende del número de ciudades que queramos visitar. Esencialmente, N debe ser mayor o igual que este número de ciudades. Para agilizar el aprendizaje, se utiliza N=3*(número de ciudades)

   ENTRENAMIENTO

    Con cada iteración, mostramos a la red la posición de una de las ciudades. Se muestra el mismo número de veces cada ciudad. Para 10-20 ciudades, son necesarias alrededor de 3000 iteraciones.

 

       

            A partir de esta solución, se puede configurar cualquier tipo de mapa para soluciones concretas. Aquí encontramos un applet adaptado para un viajante que tuviera que recorrer distintas ciudades de Castilla y León: