C21.3 : Problème du voyageur
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.
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 du problème "à la main"
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 ?
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é.