Algorithme glouton – Labodemaths.fr

1. Algorithme glouton

En informatique, un algorithme glouton (greedy algorithm en anglais, parfois appelé aussi algorithme gourmand) est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local. Dans certains cas cette approche permet d’arriver à un optimum global, mais dans le cas général c’est une heuristique
https://fr.wikipedia.org/

Au sens étroit, plus fréquent, une heuristique est une méthode de calcul qui fournit rapidement une solution réalisable, pas nécessairement optimale ou exacte, pour un problème d’optimisation difficile
https://fr.wikipedia.org/wiki/Heuristique_(math%C3%A9matiques)

2. Un exemple : le problème du voyageur de commerce.

Un voyageur de commerce doit effectuer un trajet pour visiter 20 villes et revenir ensuite à son point de départ.
Il cherche à minimiser le chemin à parcourir.
Un algorithme simple pour répondre à ce problème serait de déterminer tous les trajets possibles et la distance parcourue associée puis de déterminer le trajet le plus court.
Le problème de cet algorithme est qu’il y a en tous : 20×19×18×……×2×1= 20! ( se lit factorielle de 20 ) trajets possibles.

Exercice 1

Ecrire un script python permettant de calculer la factorielle d’un nombre entier positif.

Pour résoudre le problème du voyageur de commerce, on va préférer mettre en place un algorithme permettant de déterminer pour chaque ville la ville la plus proche, puis de construire ainsi un trajet qui minimise la distance entre deux villes successives.
Pas à pas, cet algorithme va apporter une solution locale au problème à défaut d’apporter la meilleure solution.

3. Mise en place

Créer un dossier « voyageur » et y télécharger le fichier .csv ci-dessous :

donnes_villes Télécharger

Créer dans le même dossier un fichier python « voyageur » et y insérer le code suivant permettant de lire les données du fichier .csv

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

Tester les commandes :

>>>donnees=donnees()
>>>donnees

Quelle est la nature de la variable donnees ?

Exercice 2

Pour faciliter la lecture des données, on va construire deux dictionnaires permettant de déterminer l’indice associé à une ville et réciproquement.
L’indice d’une ville correspond à l’indice de la ligne du tableau concernant les données de cette ville.
La première ville « Annecy » a ainsi pour indice 0, et la ville d’indice 22 correspond à « Toulouse »

Complétant les deux fonctions permettant de construire ces deux dictionnaires.

def transcription_ville_indice(donnees):
    

def transcription_indice_ville(donnees):

Les fonctions correctement définies doivent permettre le retour des commandes ci-dessous

>>> ville_indice=transcription_ville_indice(donnees)
>>> ville_indice["Lille"]
10
>>> indice_ville=transcription_indice_ville(donnees)
>>> indice_ville[0]
'Annecy'
>>> indice_ville[10]
'Lille'
>>> ville_indice["Toulouse"]
22

Exercice 3

Ecrire une fonction distance(ville1,ville2) permettant de déterminer la distance entre 2 villes en utilisant le contenu de la variable donnees.
Cette fonction devra permettre le retour des commandes ci-dessous.

>>> distance("Lille","Lens")
37
>>> distance("Lens","Lille")
37
>>> distance("Lens","Lens")
0
>>> distance("Toulouse","Annecy")
648
>>> distance("Annecy","Toulouse")
648

Exercice 4

Ecrire une fonction meilleur_trajet() permettant de déterminer pour une liste de villes données, le chemin qui minimise la distance entre 2 villes consécutives.
La première ville de la liste sera considérée comme la ville de départ.
On n’oubliera pas de boucler le chemin sur la ville de départ.
On pourra utiliser le module folium pour voir le bon déroulement de l’algorithme.

Module folium

Pour mieux voir le fonctionnement de votre algorithme, il peut être intéressant d’utiliser le module folium que l’on a déjà utilisé pour placer les stations de vélos ayant des vélos disponibles dans un précédent tp.

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 Paris
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
    '''
    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).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="blue", weight=2.5, opacity=0.8).add_to(carte)
    return

villes=["Lens","Marseille","Lille","Toulouse","Bordeaux","Caen","Rennes","Sedan","Grenoble","Paris"]
# affiche les marqueurs des villes
affichage_villes(villes) 
# relie les villes
affichage_trajet(villes)
# la carte est un fichier html sauvegardé dans le dossier contenant votre script
carte.save(outfile='carte.html')

Pour en savoir plus sur folium :

https://iut-info.univ-reims.fr/users/nocent/python/?section=9