<jupyter_start><jupyter_text>El problema del viajanteDada una lista de ciudades y las distancias entre cada par de ciudades determinar la ruta más pequeña posible que visite cada ciudad y regrese a la ciudad de origen.El problema en esta situación consiste en ser un problema de combinatoria donde el costo computacional de evaluar todas las combinaciones posibles aumenta mientras se incrementa la cantidad de ciudades.Para obtener lo datos para la resolución y la heurística puede utilizarse la herramienta Google Maps.  Primera parteResolver el problema utilizando un método de fuerza bruta para los siguientes destinos:- San Rafael- El sosneado- <NAME>- Gral. AlvearMostrar el costo de todas las rutas<jupyter_code>import itertools
kms = {
    'sr-es': 137,
    'es-sr': 137,
    'sr-jp': 70.1,
    'jp-sr': 70.1,
    'sr-ga': 84.8,
    'ga-sr': 84.8,
    'es-jp':200,
    'jp-es':200,
    'es-ga':214,
    'ga-es':214,
    'jp-ga':15,
    'ga-jp':15
}
    
min_km = 999999
for item in itertools.permutations(['es','jp','ga']):
    total = kms[f"sr-{item[0]}"] + kms[f"{item[0]}-{item[1]}"] + kms[f"{item[1]}-{item[2]}"] + kms[f"{item[2]}-sr"] 
    if total < min_km:
        rute = f"sr-{item[0]}-{item[1]}-{item[2]}-sr"
        min_km = total
print(min_km, rute)<jupyter_output>436.1 sr-es-ga-jp-sr<jupyter_text>Distancias SR - ES:137 km SR - JP: 70,1km SR - GA: 84,8 km ES - JP: 214 km JP - GA: 15 km  Segunda parteResolver el problema agregando heurística para los siguientes destinos:- San Rafael (sr)- El Nihuil (en)- El sosneado (es)- Villa Atuel (va)- J<NAME> (jp)- Las Malvinas (lm)- Salto de las Rosas (sdr)- Rama caída (rc)- Monte Coman (mc)- Gral. Alvear (ga)- Rincón del Atuel (ra)Responder:- ¿Qué heurística se utilizó?Partiendo de San Rafael, se elige la ciudad que se encuentre más cerca de la primera. Esto se repite para las demás ciudades sin tener en cuenta por las ciudades que ya han sido recorridas.<jupyter_code>from copy import deepcopy



if __name__ == "__main__":
    kms = [
    [0, 72.7, 137, 59.1, 70.1, 36.6, 18.9, 8.7, 50.7, 84.8, 37.6],
    [72.5, 0, 107.8, 108, 120, 135, 97.4, 84, 69.7, 122, 35],
    [137, 108, 0, 184, 200, 162, 148, 134, 186, 214, 99.1],
    [54.3, 120, 184, 0, 16.7, 45.2, 35.6, 54.5, 47.1, 31.4, 84.7], 
    [70.1, 136, 200, 16.9, 0, 60.8, 51.3, 70.2, 41.2, 15, 64.6], 
    [36, 97.7, 162, 45.6, 60.8, 0, 18.8, 29.7, 57.8, 75.4, 62.6], 
    [18.7, 84.2, 148, 36, 51.2, 18.8, 0, 18.9, 43, 65.8, 49.1], 
    [8.7, 69.8, 134, 54.9, 73.5, 29.6, 18.8, 0, 56.4, 84.7, 34.7], 
    [50.5, 122, 186, 47.2, 41.3, 52.8, 43, 56.3, 0, 48, 86.5], 
    [84.8, 122, 214, 31.4, 15, 75.4, 65.8, 84.7, 48, 0, 115], 
    [37.6, 35.2, 99.1, 85.1, 100, 62.5, 49.1, 34.7, 86.6, 115, 0]
]

    cities = [
        "San Rafael",
        "El Nihuil",
        "El sosneado",
        "<NAME>",
        "<NAME>",
        "<NAME>",
        "<NAME>",
        "<NAME>",
        "<NAME>",
        "<NAME>",
        "<NAME>",
    ]
    kms_aux = deepcopy(kms)
    rute = [0]
    kms_history = []
    total_km = 0
    count = 0
    for i in range(len(kms)):
        kms[i][0] = 9999
    while count < 10:
        minimum = 9999
        for column in kms[rute[-1]]:
            if column < minimum and (column != 0 or column != 9999):
                minimum = column
        total_km += minimum
        print(minimum, total_km)
        index = kms[rute[-1]].index(minimum)
        rute.append(index)
        for i in range(len(kms)):
            kms[i][index] = 9999
        count+=1
        print("Count:", count)
        print("Index:", index)
        for c in kms:
            print(c)
    rute.append(0) #volvemos a San Rafael
    print(rute)
    total_km += kms_aux[index][0]
    print("El trayecto óptimo obtenido es:")
    for i in rute:
        print(cities[i])
    print(f"Total kilometros recorridos: {total_km}")<jupyter_output>8.7 8.7
Count: 1
Index: 7
[9999, 72.7, 137, 59.1, 70.1, 36.6, 18.9, 9999, 50.7, 84.8, 37.6]
[9999, 0, 107.8, 108, 120, 135, 97.4, 9999, 69.7, 122, 35]
[9999, 108, 0, 184, 200, 162, 148, 9999, 186, 214, 99.1]
[9999, 120, 184, 0, 16.7, 45.2, 35.6, 9999, 47.1, 31.4, 84.7]
[9999, 136, 200, 16.9, 0, 60.8, 51.3, 9999, 41.2, 15, 64.6]
[9999, 97.7, 162, 45.6, 60.8, 0, 18.8, 9999, 57.8, 75.4, 62.6]
[9999, 84.2, 148, 36, 51.2, 18.8, 0, 9999, 43, 65.8, 49.1]
[9999, 69.8, 134, 54.9, 73.5, 29.6, 18.8, 9999, 56.4, 84.7, 34.7]
[9999, 122, 186, 47.2, 41.3, 52.8, 43, 9999, 0, 48, 86.5]
[9999, 122, 214, 31.4, 15, 75.4, 65.8, 9999, 48, 0, 115]
[9999, 35.2, 99.1, 85.1, 100, 62.5, 49.1, 9999, 86.6, 115, 0]
18.8 27.5
Count: 2
Index: 6
[9999, 72.7, 137, 59.1, 70.1, 36.6, 9999, 9999, 50.7, 84.8, 37.6]
[9999, 0, 107.8, 108, 120, 135, 9999, 9999, 69.7, 122, 35]
[9999, 108, 0, 184, 200, 162, 9999, 9999, 186, 214, 99.1]
[9999, 120, 184, 0, 16.7, 45.2, 9999, 9999, 47.1, 31.4, 84.7]
[9999, 136, 200, 16.9, 0, 60.8, [...]
{'fraction_non_alphanumeric': 0.18463750256726227, 'fraction_numerical': 0.19593345656192238, 'mean_word_length': 2.6074074074074076, 'pattern_counts': {'":': 1, '<': 20, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '451662', 'license': 'Apache-2.0', 'n_tokens_mistral': 2879, 'n_tokens_neox': 2135, 'n_words': 651, 'path': 'tp4/Ejercicio 1.ipynb', 'repo_name': 'xRUIZxMATIASx/inteligencia-artificial', 'size': '4933'}