problème du voyageur de commerce
Sommaire
Ce que vous allez apprendre
- Relier le TSP à un cycle hamiltonien de poids minimal dans un graphe complet pondéré.
- Recalculer un circuit optimal sur cinq villes et constater que l’optimum peut ne pas être unique.
- Distinguer la version de décision NP-complète de la version d’optimisation NP-difficile.
- Choisir entre méthode exacte, heuristique et modèle de tournées de véhicules selon les contraintes.
En clair
Définition
Un exemple, pas à pas
AB = 4, AC = 7, AD = 6, AE = 8 ;
BC = 5, BD = 3, BE = 6 ;
CD = 4, CE = 3, DE = 5.
2. Choisir le circuit A–B–D–C–E–A, qui visite chaque autre ville une fois.
3. Additionner les cinq distances de ce circuit :
En pratique
À ne pas confondre
Limites et pièges
Pour aller plus loin
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres




