Voyageur de commerce : correction

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.

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 :

Rappel : Pour installer le module folium en ligne de commande :

>>> pip install folium

ou aller voir la gestion des packages sur Thonny.