Circuit le plus court (ou voyageur de commerce)

Objectif : Ce problème permet d’introduire la notion de complexité pour classer les problèmes, et la recherche de solution optimale ou approchée.

Résumé : Comment trouver le circuit le plus court ? Ce problème d’optimisation aux applications innombrables nous permet d’introduire la notion de complexité pour classer les problèmes, et la recherche de solution optimale ou approchée.

Déroulé de l’activité : Sur une planche à clous, on fait passer un fil une fois et une seule par chaque clou avant de revenir au point de départ. Comment trouver le circuit le plus court possible ? Ce problème d’optimisation aux applications innombrables nous permet d’introduire la notion de complexité pour classer les problèmes, et la recherche de solution optimale ou approchée.

Il faut bien distinguer ce problème dit du voyageur de commerce dont la complexité explose avec la taille du problème et celle du plus court chemin dont la complexité augmente de manière seulement polynomiale.

La vidéo Pause ta science
Jouer en ligne (une applet en Scrach grâce à fmasseglia)
Une démonstration logicielle (une applet en Scrach grâce à fmasseglia)
On y montre l’explosion combinatoire, pour faire prendre conscience des milliards d’années de calculs qui rendent impossible de connaître LE meilleur passage de la ficelle, on peut vraiment voir les chemins très clairement pour 4 ou 5 points, puis cela devient «intractable».
Documentation : https://github.com/downloads/jcb/CSIRL/tsp.pdf (voir aussi le manuel complet)