Problème du voyageur de commerce
Période historique : 1930
Recherche du plus court circuit fermé passant exactement une fois par chaque ville d'une liste donnée.
Contenu & Formulation mathématique
Genèse & Portée historique
Le Traveling Salesperson Problem (TSP) est le problème d'optimisation combinatoire NP-difficile le plus célèbre. Pour n villes, il existe (n-1)! / 2 tournées possibles, rendant la recherche exhaustive impossible au-delà de quelques dizaines de villes. Il sert de banc d'essai universel pour les métaheuristiques (recuit simulé, algorithmes génétiques) et les méthodes par séparation et évaluation (Branch and Cut).
La première mention mathématique du problème remonte à Karl Menger à Vienne en 1930 sous le nom de Das Botenproblem (problème du messager), avant d'être popularisé par Merrill Flood à la RAND Corporation.
Filiations & Relations conceptuelles (1)
Objet de collection MathTCG
Problème du voyageur de commerce
Recherche du plus court circuit fermé passant exactement une fois par chaque ville d'une liste donnée.
Dans l'édition physique et numérique de MathTCG, cette carte appartient à l'extension Space, Chance & Computation.