1. Notre algorithme n’est pas optimal.
L’algorithme glouton par recherche de la ville la plus proche pour résoudre notre problème du voyageur de commerce n’est pas optimal.
![](https://labodemaths.fr/WordPress3/wp-content/uploads/2020/06/plus_proche_pas_optimal_1.png)
![](https://labodemaths.fr/WordPress3/wp-content/uploads/2020/06/plus_proche_pas_optimal_2.png)
Statistiquement, notre algorithme donne un trajet dont la longueur totale est supérieure d’environ 25% à celle du trajet optimal.
2. Proposition de correction
Le script :
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):
villes_restantes=liste_villes.copy()
meilleur_trajet=[]
ville_depart=villes_restantes[0]
meilleur_trajet.append(ville_depart)
villes_restantes.remove(ville_depart)
while len(villes_restantes)>0:
ville_plus_proche=villes_restantes[0]
ville_depart=meilleur_trajet[-1]
distance_min=distance(ville_depart,ville_plus_proche)
for ville in villes_restantes:
if distance(ville_depart,ville)<distance_min:
ville_plus_proche=ville
distance_min=distance(ville_depart,ville)
villes_restantes.remove(ville_plus_proche)
meilleur_trajet.append(ville_plus_proche)
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')
Le retour :
>>>runfile('/Users/davidlaignel/Desktop/nsi_juin/voyageur.py', wdir='/Users/davidlaignel/Desktop/nsi_juin')
['Lens', 'Rennes', 'Marseille', 'Lille', 'Toulouse', 'Bordeaux', 'Caen', 'Sedan', 'Grenoble', 'Paris']
['Lens', 'Lille', 'Paris', 'Caen', 'Rennes', 'Bordeaux', 'Toulouse', 'Marseille', 'Grenoble', 'Sedan', 'Lens']
La carte obtenue dans notre répertoire :
![](https://labodemaths.fr/WordPress3/wp-content/uploads/2020/06/Capture-d’écran-2020-06-16-à-10.15.30-1024x958.png)
Rappel : Pour installer le module folium en ligne de commande :
>>> pip install folium
ou aller voir la gestion des packages sur Thonny.