Titre : La recherche du plus court chemin

Année : 1997

Mots-clefs : Géodésique, problème du voyageur de commerce, arbre de classification, arbre minimal.

Classification AMS : 28D05

Résumé :

Comme chacun sait, le chemin le plus court pour joindre deux points est la ligne droite... dans les cas simples ! Nous montrerons dans cette conférence qu'une ligne brisée, un arc de cercle, ou des courbes plus compliquées peuvent aussi constituer le plus court chemin d'un point à un autre. Le problème se complique encore davantage lorsqu'il s'agit de relier plus de deux points entre eux. Nous présenterons des cas où des méthodes simples existent pour trouver le plus court ``chemin'' joignant n points, et des situations où, au contraire, on ne sait pas en pratique trouver ce plus court chemin : on doit se contenter de solutions approchées, obtenues notamment par des algorithmes faisant intervenir le hasard ! Nous verrons enfin que cette recherche du plus court chemin a de nombreuses applications, qui dépassent largement le cadre des transports : on l'utilise aussi dans des problèmes de classement et de statistiques... et pour la pose économique de papiers peints !

Avertissement :

Ce texte est destiné à un public non-mathématicien, aussi avons nous réduit au minimum le vocabulaire technique et renoncé à la présentation à presque toute démonstration. Par contre, nous avons (ab-)usé de petits problèmes concrets favorisant la présentation de concepts mathématiques. Nous renvoyons tous ceux qui veulent en savoir plus à la bibliographie. Nous invitons mathématiciens amateurs ou avertis à résoudre quelques petits exercices. Ce document constitue le support écrit de la conférence donnée le 11 octobre 1997 à Caudebec-lès-Elbeuf dans le cadre des manifestations de Science en Fête qui, en Haute-Normandie avaient pour thème les transports et la logistique.