Nous verrons deux techniques générales appliquées au problème du voyageur de commerce. La première, le branch and bound, est une approche classique de l'optimisation combinatoire utilisée pour divers problèmes. Elle peut être considérée comme une amélioration de la recherche par force brute : nous essayons de construire une permutation morceau par morceau, mais à chaque étape, nous vérifions s'il est toujours utile de continuer à construire la permutation (si ce n'est pas le cas, nous coupons simplement la branche en cours). La seconde, la programmation dynamique, est sans doute la technique algorithmique la plus populaire. Elle permet de résoudre un problème en passant par un ensemble de sous-problèmes plus petits.

Comme nous l'avons vu dans les modules précédents, il est difficile de résoudre exactement le problème du voyageur de commerce. En fait, nous ne nous attendons même pas à trouver une solution efficace dans un avenir proche. C'est pourquoi il est logique de se poser la question suivante : est-il possible de trouver efficacement une solution qui est probablement sous-optimale, mais qui est en même temps proche de l'optimum ? Il s'avère que la réponse est oui ! Nous allons apprendre deux algorithmes. Le premier garantit de trouver rapidement une solution qui est au plus deux fois plus longue que la solution optimale. Le second algorithme n'a pas de telles garanties, mais il est connu pour fonctionner assez bien en pratique.