Pourquoi trouver le plus court circuit passant par vingt villes est-il si difficile ?

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

En regardant un livreur de colis enchaîner ses arrêts dans mon quartier, je me suis demandé comment son application choisissait l'ordre des livraisons. J'ai découvert le « problème du voyageur de commerce », simple à énoncer et pourtant non résolu efficacement. J'ai voulu comprendre pourquoi en comptant les circuits possibles.

L'enjeu et les notions du programme

Dénombrer les circuits par les permutations, comparer factorielle et exponentielle, et justifier le recours aux heuristiques.

Le plan de l'exposé en 9,5 min

1. 1. Introduction

   1 min

   Un voyageur doit visiter $n$n villes une fois chacune et revenir à son point de départ, en parcourant la plus petite distance. Problématique : pourquoi ne peut-on pas simplement essayer tous les circuits ?

2. 2. Mathématiques : compter les circuits

   4 min

   On fixe la ville de départ. Les $n-1$n-1 autres peuvent être visitées dans $(n-1)!$(n-1)! ordres. Chaque circuit est compté deux fois (une fois dans chaque sens) : il y a $\frac{(n-1)!}{2}$((n-1)!)/2 circuits distincts.

   Pour 5 villes : $\frac{4!}{2}=12$4!/2=12. Pour 10 villes : $\frac{9!}{2}=181440$9!/2=181 440, instantané. Pour 20 villes : $\frac{19!}{2}\approx 6,1\times 10^{16}$19!/2≈6,1×10¹⁶ ; à $10^9$10⁹ circuits par seconde, environ $6\times 10^7$6×10⁷ secondes, près de deux ans. Pour 30 villes, plus de $10^{30}$10³⁰ circuits.

   La factorielle croît encore plus vite que l'exponentielle : $\frac{n!}{2^n}$n!/2ⁿ tend vers $+\infty$+∞, car à partir de $n=4$n=4, on multiplie à chaque étape par un facteur $\frac{n+1}{2}\ge 2$(n+1)/2≥2.

3. 3. NSI : des solutions approchées

   3 min

   On modélise par un graphe complet pondéré : sommets les villes, poids les distances. L'heuristique du plus proche voisin part d'une ville et va toujours à la ville non visitée la plus proche : environ $n^2$n² opérations, mais le résultat peut être de 20 à 25 % plus long que l'optimum en moyenne.

   On l'améliore ensuite localement, par exemple en échangeant deux arêtes qui se croisent (méthode 2-opt) : un circuit qui se croise n'est jamais optimal. Les logiciels de tournées combinent ces méthodes et trouvent en pratique de très bonnes solutions pour des milliers d'arrêts, sans preuve qu'elles soient les meilleures.

4. 4. Conclusion

   1,5 min

   Le voyageur de commerce est difficile parce que le nombre de circuits, $\frac{(n-1)!}{2}$((n-1)!)/2, explose plus vite qu'une exponentielle. On se contente d'heuristiques rapides et de bonne qualité. J'ouvre sur l'algorithme de Dijkstra, qui résout vite un problème voisin : le plus court chemin entre deux villes.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

Conclusion : la réponse à la question

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Les pièges qui coûtent des points

• Oublier de fixer la ville de départ et compter n! circuits.
• Croire qu'une heuristique donne toujours l'optimum.
• Confondre le voyageur de commerce et le plus court chemin entre deux points.

Revoir les notions

• Combinatoire et dénombrement (Terminale spé maths) →
• Géométrie repérée (Seconde) →

Autres questions : algorithmes et complexité

• Pourquoi trier un million de nombres peut-il prendre dix minutes ou un centième de seconde selon l'algorithme ?
• Pourquoi couper un problème en deux permet-il de le résoudre beaucoup plus vite ?
• Peut-on inventer un algorithme de tri encore plus rapide, ou existe-t-il une limite infranchissable ?
• Un ordinateur mille fois plus rapide permet-il de résoudre des problèmes mille fois plus grands ?

Toutes les questions maths-nsi →