Commerce

° Voyageur de commerce. – Récréation de parcours : Établissez l'itinéraire le plus court d'un voyageur de commerce qui doit se rendre dans un nombre déterminé de villes, en passant une et une seule fois dans chaque ville et de telle manière qu'il revient au point de départ. 

Malgré l'existence d'algorithmes, il n'y a pas de solution générale à ce problème. La meilleure stratégie demeure la recherche systématique. Le problème revient à trouver le cycle hamiltonien d'un graphe dont les sommets représentent les villes. 

Le problème du voyageur de commerce appartient à la classe des récréations topologiques.

© Charles-É. Jean

Index : C