100, rue des maths 38610 Gières / GPS : 45.193055, 5.772076 / Directeur : Louis Funar

Autour du problème du voyageur de commerce dans le plan euclidien.

Mercredi, 29 Novembre, 2006 - 17:30
Prénom de l'orateur : 
Nicolas
Nom de l'orateur : 
JUILLET
Résumé : 

Casse-tête mathématique créé au début du 19ème siècle, le
problème du voyageur de commerce fait désormais parti du patrimoine
scientifique. Il est en outre autre célèbre pour la renumératrice et
passionnante conjecture P=NP. En marge de cette thématique, nous nous concentrerons dans cet exposé sur quelques aspects que le problème revêt lorsque le voyageur de commerce doit effectuer sa tournée dans le carré $[0,1]^2$ du plan euclidien. Dans ce cadre nous étudierons le coût du parcours optimal en fonction de la position des villes et de leur nombre.
Quelles sont les distances parcourue dans le pire des cas, ou
bien en moyenne lorsque les villes apparaissent en suivant une loi de
probabilité? Que se passe-t-il quand le nombre de ville croît?(quitte à devenir infini!) Que nous apprennent les courbes de remplissage (du type Peano)? Nous apporterons des éléments de réponse à ces questions.

Thème de recherche : 
Compréhensible
Salle : 
04
logo uga logo cnrs