Le problème du voyageur de commerce (Travelling Salesman Problem) est un célèbre problème d'algorithmique. Un voyageur de commerce résidant dans une ville V0 part faire la tourné de ses clients. Supposons qu'il doive rencontrer n clients c1,...,cn résidant dans n villes v1,....,vn telles que ci habite à vi pour i = 1...n. On suppose que quels qe soient i et j tels que 0 <= i < j <= n, vi et vj sont distinctes et il existe une route reliant vi et vj (Le graphe v0,...,vn est complet). Le voyageur part de sa ville de résidence v0, réalise la tournée de ses clients puis reviens à v0. Pour optimiser le trajet total parcouru, le voyageur ne parcourt jamais deux fois la même route.
Quel itinéraire doit-il emprunter pour minimiser la distance totale parcourue ?
Ce problème n'a, dans le cas général, pas de solution de complexité polynomiale connue. En effet, le seul algorithme exact connu consiste à évaluer les n!/2 itinéraires possibles. Cette solution n'est pas réaliste pour n grand (10!/2 > 10^6)
Remarque: Tout chemin fermé passant exactement une seul fois par chaque sommet v0,...,vn est dit circuit hamiltonien du graphe complet(v0,...,vn)