NSI: le probleme du voyageur de commerce

TP :
1. Télécharger le fichier csv suivant

2. Copier et coller le code python suivant dans un fichier voyageur_commerce.py situé dans le même dossier que le précédent fichier csv

3. Compléter la fonction meilleur_trajet

import folium # module permettant d'afficher des cartes avec OpenStreetMap

latitude_Paris=48.65829086
longitude_Paris=2.086790085
# on crée une carte centrée sur Lille
carte = folium.Map(location=(latitude_Paris,longitude_Paris), tiles='OpenStreetMap', zoom_start=6)

def affichage_villes(villes):
    '''
    affiche sur une carte les différentes villes présentes dans la liste villes
    return : carte avec marqueurs des stations
    '''
    # on met un marqueur différent pour la première ville
    indice=ville_indice[villes[0]]
    latitude=float(donnees[indice][2])
    longitude=float(donnees[indice][1])
    localisation=(latitude,longitude)
    folium.Circle(
      location=localisation,
      popup='depart',
      radius=15000,
      color='crimson',
      fill=True,
      fill_color='crimson'
   ).add_to(carte)
    # on place des marqueurs pour les villes
    for ville in villes:
        indice=ville_indice[ville]
        latitude=float(donnees[indice][2])
        longitude=float(donnees[indice][1])
        localisation=(latitude,longitude)
        legende=ville+" lat : "+str(latitude)+" long : "+str(longitude)
        folium.Marker(location=localisation, popup = legende,color="red").add_to(carte)
    return

def affichage_trajet(chemin):
    '''
    affiche sur une carte les différentes villes présentes dans la liste villes
    return : carte avec marqueurs des stations
    '''
    trajet=[]
    for ville in chemin:
        indice=ville_indice[ville]
        latitude=donnees[indice][2]
        longitude=donnees[indice][1]
        localisation=(float(latitude),float(longitude))
        trajet.append(localisation)
    folium.PolyLine(trajet, color="red", weight=2.5, opacity=0.8).add_to(carte)
    return



def donnees():
    fichier = open("donnes_villes.csv", "r")
    donnees = fichier.read()
    donnees = donnees.replace (",", ".").split("\n")
    donnees=[ t.strip ("\r\n ").split (";") for t in donnees ]
    fichier.close()
    return donnees

def transcription_ville_indice(donnees):
    ville_indice=dict()
    for i in range(len(donnees)):
        ville_indice[donnees[i][0]]=i
    return ville_indice

def transcription_indice_ville(donnees):
    indice_ville={}
    for i in range(len(donnees)):
        indice_ville[i]=donnees[i][0]
    return indice_ville

def distance(ville1,ville2):
    i1=ville_indice[ville1]
    i2=ville_indice[ville2]
    imin=min(i1,i2)
    imax=max(i1,i2)
    return int(donnees[imax][imin+3])

def meilleur_trajet(liste_villes):
    # on definit les villes_restantes comme une copie de la liste des villes
    villes_restantes=..........
    # on définit le meilleur trajet comme une liste vide
    meilleur_trajet=..........
    # on définit la ville de départ comme la première ville des villes_restantes
    ville_depart=.....................
    # on ajoute la ville_depart au meilleur trajet
    .................
    # on enleve la ville_depart au villes_restantes
    ....................
    # tant que la liste des villes_restantes n'est pas vide
    while len(villes_restantes)........... :
        # la ville la plus proche est la premiere des villes_restantes
        ville_plus_proche=.....................
        # la ville_depart est la derniere du meilleur_trajet
        ville_depart=........................
        distance_min=distance(ville_depart,ville_plus_proche)
        # on parcourt les villes_restantes
        for ville in ...................:
            # si ville est plus proche de la ville_depart
            if distance(ville_depart,ville)<...............:
                # elle devient la nouvelle ville_plus_proche
                ville_plus_proche=..............
                # on modifie alors la distance_min
                distance_min=distance(ville_depart,ville)
        # on enleve la ville_plus_proche des villes restantes
        ...................
        # on l'ajoute au meilleur_trajet
        ......................
    # on ajoute au final la ville de depart pour boucler le trajet
    meilleur_trajet.append(meilleur_trajet[0])
    return meilleur_trajet

donnees=donnees()
ville_indice=transcription_ville_indice(donnees)
indice_ville=transcription_indice_ville(donnees)
villes=["Lens","Rennes","Marseille","Lille","Toulouse","Bordeaux","Caen","Sedan","Grenoble","Paris"]
print(villes)
print(meilleur_trajet(villes))
affichage_villes(villes)
affichage_trajet(meilleur_trajet(villes))
carte.save(outfile='carte.html')

proposition de correction

def meilleur_trajet(liste_villes):
    # on definit les villes_restantes comme une copie de la liste des villes
    villes_restantes=liste_villes.copy()
    # on définit le meilleur trajet comme une liste vide
    meilleur_trajet=[]
    # on définit la ville de départ comme la première ville des villes_restantes
    ville_depart=villes_restantes[0]
    # on ajoute la ville_depart au meilleur trajet
    meilleur_trajet.append(ville_depart)
    # on enleve la ville_depart au villes_restantes
    villes_restantes.remove(ville_depart)
    # tant que la liste des villes_restantes n'est pas vide
    while len(villes_restantes)>0 :
        # la ville la plus proche est la premiere des villes_restantes
        ville_plus_proche=villes_restantes[0]
        # la ville_depart est la derniere du meilleur_trajet
        ville_depart= meilleur_trajet[-1]
        distance_min=distance(ville_depart,ville_plus_proche)
        # on parcourt les villes_restantes
        for ville in villes_restantes:
            # si ville est plus proche de la ville_depart
            if distance(ville_depart,ville)<distance_min:
                # elle devient la nouvelle ville_plus_proche
                ville_plus_proche=ville
                # on modifie alors la distance_min
                distance_min=distance(ville_depart,ville)
        # on enleve la ville_plus_proche des villes restantes
        villes_restantes.remove(ville_plus_proche)
        # on l'ajoute au meilleur_trajet
        meilleur_trajet.append(ville_plus_proche)
    # on ajoute au final la ville de depart pour boucler le trajet
    meilleur_trajet.append(meilleur_trajet[0])
    return meilleur_trajet