Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Problème du voyageur de commerce
Résumé
vignette|Le problème de voyageur de commerce : calculer un plus court circuit qui passe une et une seule fois par toutes les villes (ici 15 villes).
En informatique, le problème du voyageur de commerce, ou problème du commis voyageur, est un problème d'optimisation qui consiste à déterminer, étant donné un ensemble de villes, le plus court circuit passant par chaque ville une seule fois.
C'est un problème algorithmique célèbre, qui a donné lieu à de nombreuses recherches et qui est souvent utilisé comme introduction à l'algorithmique ou à la théorie de la complexité. Il présente de nombreuses applications, que ce soit en planification, en logistique ou dans des domaines éloignés, comme la génétique, les gènes étant les villes par des gènes et la similarité la distance.
Étant donné n villes et leurs distances par paire, il s'agit de déterminer le chemin le plus petit qui passe exactement une fois par chaque ville et revienne à la ville de départ. On modélise le problème du voyageur de commerce comme un problème sur un graphe non orienté pondéré. Les villes sont les sommets du graphe. Le voyageur emprunte les arêtes du graphe. Le coût d'une arête entre deux sommets est la distance entre les deux villes correspondantes. Souvent, on considère un graphe complet, i.e. il y a une arête entre toutes paires de sommets : avec un ensemble de sommets, un ensemble d'arêtes, et une fonction de coût sur les arêtes. Le problème est de trouver le plus court cycle hamiltonien dans le graphe G.
On considère la liste des villes A, B, C, D et les distances données par le dessin ci-dessous à gauche. Un premier chemin qui part de A, revient en A et qui visite toutes les villes est ABDCA. Un chemin plus court est ACBDA. Ce dernier est optimal. (Attention, les distances dans l'exemple ne respectent pas l'inégalité triangulaire : d(A,B) < d(A,D) +d(D,B))
Ce problème est plus compliqué qu'il n'y paraît ; on ne connaît pas de méthode de résolution permettant d'obtenir des solutions exactes en un temps raisonnable pour de grandes instances (grand nombre de villes) du problème.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.