276
20 Problème du voyageur de commerce
problème NP complet. On sait démontrer que TSP est NP-complet, et on
ne connaît pas d’algorithme de résolution polynomial. Il est cependant possible de rechercher une solution approchée, par exemple avec un algorithme
stochastique générique comme l’algorithme du recuit simulé, comme expliqué
dans le chapitre 5. Contrairement à TSP, les deux autres problèmes phares
de l’optimisation combinatoire (arbre couvrant minimal et appariement euclidien minimal) sont résolubles en temps polynomial. Pour en savoir plus, on
renvoie par exemple au livre de Alfred Aho, John Hopcroft, et Jeffrey Ullman
[AHU75], au livre de Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi,
et Viggo Kann [ACG
+ 99], ainsi qu’au cours de Charles Bordenave [Bor14a].
20 Problème du voyageur de commerce
problème NP complet. On sait démontrer que TSP est NP-complet, et on
ne connaît pas d’algorithme de résolution polynomial. Il est cependant possible de rechercher une solution approchée, par exemple avec un algorithme
stochastique générique comme l’algorithme du recuit simulé, comme expliqué
dans le chapitre 5. Contrairement à TSP, les deux autres problèmes phares
de l’optimisation combinatoire (arbre couvrant minimal et appariement euclidien minimal) sont résolubles en temps polynomial. Pour en savoir plus, on
renvoie par exemple au livre de Alfred Aho, John Hopcroft, et Jeffrey Ullman
[AHU75], au livre de Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi,
et Viggo Kann [ACG
+ 99], ainsi qu’au cours de Charles Bordenave [Bor14a].