Traveling salesman problem (TSP)

Le TSP (travelling salesman problem) est une énigme algorithmique qui vise à trouver le chemin le plus rapide à partir d'un certain nombre de lieux et de points. Les points représentent les villes possibles qu'un vendeur pourrait visiter. Les vendeurs souhaitent réduire autant que possible les frais de déplacement et la distance. Axée sur l'optimisation, la TSP est souvent utilisée en informatique pour trouver l'itinéraire le plus efficace pour le déplacement des données entre différents nœuds. Les applications comprennent l'identification des méthodes d'optimisation des réseaux ou du matériel. Elle a été décrite pour la première fois par le mathématicien irlandais W.R. Hamilton et le mathématicien britannique Thomas Kirkman dans les années 1800 par la création d'un jeu qui pouvait être résolu en trouvant un cycle de Hamilton, qui est un chemin sans chevauchement entre tous les nœuds.

Plutôt que de se concentrer sur la recherche de l'itinéraire le plus efficace, les TSP se préoccupent souvent de trouver la solution la moins chère. Dans les TSP, la grande quantité de variables crée un défi lors de la recherche du chemin le plus court, ce qui rend les solutions approximatives, rapides et bon marché d'autant plus intéressantes.

TSP a été étudié pendant des décennies et plusieurs solutions ont été théorisées. La solution la plus simple consiste à essayer toutes les possibilités, mais c'est aussi la méthode la plus longue et la plus coûteuse. De nombreuses solutions font appel à l'heuristique, qui fournit des résultats probabilistes. Cependant, les résultats sont approximatifs et ne sont pas toujours optimaux. Parmi les autres solutions, citons les algorithmes de branchement et de limitation, de Monte Carlo et de Las Vegas.