🚚 Le commercial qui ne dort jamais
Un commercial doit visiter 50 villes, exactement une fois chacune, puis revenir au point de départ. Question : dans quel ordre les visiter pour minimiser la distance totale parcourue ?
Pour 5 villes, c'est facile : il y a 4!/2 = 12 trajets possibles, on les essaie tous, on prend le plus court. Pour 10 villes : 9!/2 = 181 440 trajets. Encore gérable pour un ordinateur.
Pour 50 villes : 49!/2 ≈ 3 × 10⁶² trajets possibles. Un nombre plus grand que le nombre d'atomes dans la Voie Lactée. Aucun ordinateur, même en utilisant tous les ordinateurs de la planète, ne peut les énumérer en temps raisonnable.
🎛️ Joue avec le problème
Clique pour ajouter des villes. Compare l'algorithme glouton (rapide mais sous-optimal) avec une vraie optimisation par recherche locale (lente mais meilleure).
🎛️ TSP interactif
Clique sur le canvas pour ajouter une ville. Compare glouton vs recherche locale.
Villes
0
Distance totale
—
📐 Complexité algorithmique
- Force brute : O((n−1)!/2) — explose vite (50 villes = 3·10⁶² trajets)
- Programmation dynamique : O(n² · 2ⁿ) — meilleur, mais limite à ~25 villes en pratique
- Glouton (plus proche voisin) : O(n²) — très rapide, mais peut donner un résultat jusqu'à 25% plus long que l'optimum
- 2-opt (recherche locale) : O(n³) par itération — bon compromis
- Algorithmes modernes (LKH, Concorde) : peuvent résoudre des instances de plusieurs milliers de villes en quelques heures
💰 P vs NP : le problème à 1 million de dollars
Le voyageur de commerce appartient à une famille de problèmes appelés NP-complets. Caractéristique commune :
- Vérifier qu'une solution donnée est correcte est rapide (temps polynomial)
- Trouver une solution optimale semble exiger un temps exponentiel
La question fondamentale : existe-t-il un algorithme polynomial pour résoudre les problèmes NP-complets ? En notation théorique : P = NP ?
🚀 Heuristiques modernes
Même sans solution exacte, on a des techniques pour s'approcher de l'optimum :
- Recuit simulé : inspiré du refroidissement des métaux. Accepte des solutions parfois moins bonnes pour échapper aux optima locaux.
- Algorithmes génétiques : mime l'évolution biologique. Croisement et mutation de « tournées ».
- Colonies de fourmis : simule le dépôt de phéromones par des fourmis virtuelles.
- Branch and bound : élague intelligemment l'arbre des possibilités.
🌍 Applications réelles
Le voyageur de commerce n'est pas qu'un casse-tête théorique. Sous des formes diverses, on le retrouve partout :
- Logistique : tournées d'Amazon, La Poste, livreurs Uber Eats
- Industrie : optimisation de chaînes de production, perçage de circuits imprimés
- Robotique : planification de trajectoires d'aspirateurs robots, drones de surveillance
- Biologie : séquençage ADN (problème de l'assembly des fragments)
- Astronomie : ordre d'observation des cibles d'un télescope
🎓 Lien avec le programme
TSP n'est pas au programme BAC SM, mais les notions sont accessibles :
- Dénombrement (concept Atlas « Dénombrement ») : (n−1)!/2 trajets possibles pour n villes
- Suites factorielles : croissance plus rapide qu'exponentielle
- Graphes : les villes sont les sommets, les routes sont les arêtes pondérées
- Optimisation : chercher un minimum d'une fonction (la distance totale) sur un ensemble fini mais énorme
🧠 Réflexion finale
Le voyageur de commerce nous enseigne une chose importante : certains problèmes mathématiques résistent à la puissance brute. On peut avoir des supercalculateurs surpuissants, des IA gigantesques — il reste des questions où la complexité combinatoire écrase tout.
C'est aussi une magnifique introduction à la pensée informatique moderne : au lieu de chercher la solution parfaite, on cherche des compromis intelligents. Bon résultat + temps raisonnable > résultat parfait + temps infini.