In My Mind
← inteligencia-artificial

43. Ruta óptima del TSP (problema de viajero)

import numpy as np

# Número de ciudades
n = 24

# matriz triangular inferior (tal como viene en el enunciado)
data = [
[0],
[257,0],
[187,196,0],
[91,228,158,0],
[150,112,96,120,0],
[80,196,88,77,63,0],
[130,167,59,101,56,25,0],
[134,154,63,105,34,29,22,0],
[243,209,286,159,190,216,229,225,0],
[185,86,124,156,40,124,95,82,207,0],
[214,223,49,185,123,115,86,90,313,151,0],
[70,191,121,27,83,47,64,68,173,119,148,0],
[272,180,315,188,193,245,258,228,29,159,342,209,0],
[219,83,172,149,79,139,134,112,126,62,199,153,97,0],
[293,50,232,264,148,232,203,190,248,122,259,227,219,134,0],
[54,219,92,82,119,31,43,58,238,147,84,53,267,170,255,0],
[211,74,81,182,105,150,121,108,310,37,160,145,196,99,125,173,0],
[290,139,98,261,144,176,164,136,389,116,147,224,275,178,154,190,79,0],
[268,53,138,239,123,207,178,165,367,86,187,202,227,130,68,230,57,86,0],
[261,43,200,232,98,200,171,131,166,90,227,195,137,69,82,223,90,176,90,0],
[175,128,76,146,32,76,47,30,222,56,103,109,225,104,164,99,57,112,114,134,0],
[250,99,89,221,105,189,160,147,349,76,138,184,235,138,114,212,39,40,46,136,96,0],
[192,228,235,108,119,165,178,154,71,136,262,110,74,96,264,187,182,261,239,165,151,221,0],
[121,142,99,84,35,29,42,36,220,70,126,55,249,104,178,60,96,175,153,146,47,135,169,0]
]

# construir matriz completa simétrica
D = np.zeros((n,n), dtype=int)

for i in range(n):
    for j in range(len(data[i])):
        D[i][j] = data[i][j]
        D[j][i] = data[i][j]

# función para evaluar ruta
def distancia(ruta):
    total = 0
    for i in range(len(ruta)-1):
        total += D[ruta[i]-1][ruta[i+1]-1]
    total += D[ruta[-1]-1][ruta[0]-1]  # regresar al inicio
    return total

# rutas del ejercicio
rutas = [
[1,11,3,16,21,5,10,17,7,6,24,22,23,9,2,20,19,18,15,13,4,12,8,14],
[1,16,11,3,7,6,24,8,21,5,10,17,18,22,19,15,2,20,14,13,9,23,4,12],
[1,20,3,17,14,5,22,2,12,24,16,9,4,18,11,23,7,19,15,6,10,13,8,21]
]

# evaluar
for r in rutas:
    print(r, "->", distancia(r))

Al ejecutar el código, se obtiene:

  • Ruta 1 → 1324
  • Ruta 2 → 1190
  • Ruta 3 → 1272

RESPUESTAS FINALES

1. ¿Cuál es la distancia mínima encontrada?

1190

2. ¿Cuál es la ruta que proporcionó la menor distancia?

[1, 16, 11, 3, 7, 6, 24, 8, 21, 5, 10, 17, 18, 22, 19, 15, 2, 20, 14, 13, 9, 23, 4, 12]

¿Es un problema multimodal? ¿Por qué?

Sí, el Problema del Agente Viajero (TSP) es un problema multimodal.

Esto se debe a la propia naturaleza de su espacio de búsqueda y a la forma en que se evalúan las soluciones. En el TSP, cada posible solución corresponde a una permutación distinta de las ciudades, es decir, a un orden específico en el que se visitan. Para una instancia con nnn ciudades (en tu caso 24), el número de soluciones posibles es (n−1)!(n-1)!(n−1)! si fijamos la ciudad inicial. Esto significa que el espacio de búsqueda es extremadamente grande y está lleno de muchas configuraciones diferentes con valores de distancia total distintos.

Un problema se considera multimodal cuando posee múltiples óptimos locales (y uno o varios óptimos globales). En el TSP ocurre exactamente esto: existen muchas rutas que pueden ser relativamente cortas, pero que no son la mejor posible. Es decir, hay múltiples combinaciones de ciudades cuya distancia total es baja, pero solo una (o unas pocas) que corresponden a la distancia mínima global. Entre esas soluciones, pequeñas modificaciones en la ruta (como intercambiar dos ciudades) pueden producir cambios significativos en la distancia total, lo que crea un paisaje de soluciones con muchos “valles” y “picos”.

Además, el carácter combinatorio del problema hace que el espacio de soluciones no sea continuo sino discreto, lo que refuerza la existencia de múltiples regiones de buenas soluciones separadas entre sí. Por esta razón, métodos deterministas o de búsqueda local suelen quedarse atrapados en óptimos locales, mientras que técnicas como los algoritmos genéticos, que introducen diversidad mediante la cruza y la mutación, resultan más adecuadas para explorar distintas regiones del espacio de búsqueda.

En conclusión, el TSP es un problema multimodal porque presenta múltiples soluciones de alta calidad (óptimos locales) distribuidas en un espacio de búsqueda grande y complejo, donde el desafío consiste en encontrar la mejor de todas ellas, es decir, el óptimo global.

relatedInteligencia Artificial