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