C16.1 : Algorithmes gloutons (rappel)

Exemple du voyageur de commerce

Présentation du problème à résoudre

Un voyageur souhaite visiter les cinq préfectures des cinq départements des Hauts-de-France : Lille, Arras, Laon, Beauvais et Amiens. Dans un soucis écologique, il souhaite, lors de son voyage, parcourir la plus petit distance possible.

Carte des Hauts-de-France avec les cinq préfectures de département

Il a relevé sur le site openstreetmap.org les distances entre chaque préfecture en km et les a consignées dans un tableau à double entrée.

  Lille Arras Laon Beauvais Amiens
Lille 0 54 156 195 142
Arras 54 0 129 154 62
Laon 156 129 0 134 125
Beauvais 195 154 134 0 62
Amiens 142 62 125 62 0

Résolution exhaustive

Première approche

🖊️ Proposer et mettre en œuvre une démarche pour résoudre le problème du voyageur : c'est-à-dire lui trouver, avec certitude, le voyage le plus court.

Généralisation de l'approche exhaustive

On souhaite généraliser le problème avec un voyage où le nombre de villes à visiter est N.

🖊️ 1) Combien de voyages différents sont possibles pour visiter N villes ?

🖊️ 2) La résolution exhaustive, à la main, pour un voyage de 10 villes vous semble-t-elle possible ?

🖊️ 3) La résolution exhaustive, à l'ordinateur, pour un voyage de 100 villes vous semble-t-elle possible ?

Résolution approchée avec l'algorithme glouton

Lorsqu'il y a beaucoup de villes, une approche simplifiée consiste, pour le voyageur, a adopter la démarche suivante : à chaque ville, il choisit comme ville suivante, la ville la plus proche parmi toutes celles qu'il n'a pas encore visité.

💻 Proposer un programme qui réponde au problème posé.

Aide sur les variables à utiliser

On pourra utiliser deux variables globales :

  • • Une liste L_villes avec les chaines de caractères correspondant aux noms des villes. Dans ce cas, chaque ville sera caractérisée par un numéro correspondant à sa position dans cette liste.
  • • Une liste de liste LL_distances correspondant aux distances entres les villes.

On pourra envisager les fonctions suivantes :

• Une fonction supprime_ville(num_ville, liste_num_villes) qui supprime num_ville de liste_num_villes ;

• Une fonction distance(num_ville1, num_ville2) qui renvoie la distance entre les villes dont les numéros sont num_ville1 et num_ville2 ;

• Une fonction ville_suivante(num_ville, liste_num_villes_restantes) qui détermine, parmi les villes de la liste liste_num_villes_restantes, le numéro de la ville la plus proche de num_ville ;

• La fonction meilleur_voyage(num_ville_depart, liste_num_villes).
Cette fonction pourra utiliser les variables locales suivantes :

  • - un entier pour la ville actuellement visitée
  • - une liste pour les villes qu'il reste à visiter
  • - une liste pour les villes déjà visités

Les algorithmes gloutons

L'optimisation combinatoire consiste à trouver, parmi un ensemble fini de combinaisons, la (les) combinaison(s) qui répond(ent) de façon optimale à un critère donné.

• Une façon de résoudre exactement ce problème consiste à appliquer de façon exhaustive le critère à toutes les combinaisons pour ne garder que la combinaison dont le résultat est optimal. Cette méthode peut, dans de nombreux cas, prendre un temps trop long.

• Les algorithmes gloutons permettent de trouver une solution satisfaisante (mais pas forcément la solution optimale) en appliquant le critère localement, de proche en proche.