Overblog Suivre ce blog
Editer l'article Administration Créer mon blog
16 janvier 2014 4 16 /01 /janvier /2014 10:37

 

                                                File:Salesman.PNG


Le problème du voyageur de commerce, étudié depuis le 19e siècle, est l’un des plus connus dans le domaine de la recherche opérationnelle. Jouez à trouver le meilleur parcours possible... et découvrez différentes méthodes informatiques proposées pour résoudre ce problème.

C'est déjà sous forme de jeu que William Rowan Hamilton a posé pour la première fois ce problème, dès 1859. Sous sa forme la plus classique, son énoncé est le suivant : « Un voyageur de commerce doit visiter une et une seule fois un nombre fini de villes et revenir à son point d’origine. Trouvez l’ordre de visite des villes qui minimise la distance totale parcourue par le voyageur ». Ce problème d’optimisation combinatoire appartient à la classe des problèmes NP-Complets definition.

Les domaines d’application sont nombreux : problèmes de logistique, de transport aussi bien de marchandises que de personnes, et plus largement toutes sortes de problèmes d'ordonnancement. Certains problèmes rencontrés dans l'industrie se modélisent sous la forme d’un problème de voyageur de commerce, comme l'optimisation de trajectoires de machines outils : comment percer plusieurs points sur une carte électronique le plus vite possible ?

Comme illustration de ce problème, nous vous proposons le jeu ci-dessous. Le but ? Trouver le parcours du voyageur pour qu'il visite toutes les villes de France affichées, en respectant la durée maximale du voyage, exprimée en heures. Le nombre de villes à visiter dépend de la difficulté choisie. En mode deux joueurs, si les parcours trouvés ont la même durée, le gagnant sera celui qui aura trouvé la solution le plus rapidement.

Partager cet article

MS XibniY : LE BLOG DE MOHAMED SALEH IBNI OUMAR - dans INFORMATIQUE
commenter cet article

commentaires

  • : XibniY : BLOG DE MOHAMED SALEH IBNI OUMAR
  • XibniY : BLOG DE MOHAMED SALEH IBNI OUMAR
  • : Blog dédié à l'Histoire, à la Beauté et à l'Enseignement des Mathématiques. Contact: ioms001@yahoo.fr
  • Contact


PLAQUEIBNI.jpg

"Le Professeur Ibni est un mathématicien tchadien de renom, Ancien Directeur du CNAR (CNRS tchadien), Ancien Recteur et Ancien Ministre de l'Enseignement Supérieur et de la Recherche, il avait initié plusieurs jumelages avec des Universités Etrangères, au service de l’enseignement des sciences dans son pays et en Afrique plus généralement"

PRIXIBNI.jpg
Candidature au Prix Ibni