Mis à jour le 11/07/2017
  • 15 heures
  • Facile

Ce cours est visible gratuitement en ligne.

Ce cours est en vidéo.

Vous pouvez obtenir un certificat de réussite à l'issue de ce cours.

J'ai tout compris !

Quel est le problème du voyageur de commerce ?

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

On sait qu'il peut exister plusieurs algorithmes pour un même problème. Mais peut-on toujours utiliser un algorithme pour résoudre un problème ? Eh bien… La réponse pourrait bien vous surprendre !

Le problème du voyageur de commerce

En effet, parfois, on sait écrire un algorithme correct mais qui n'apportera jamais la solution. Oui, dit comme ça, on peut trouver que c'est étrange… Et pourtant ! Pour être plus précis, disons que l'algorithme est effectivement correct mais qu’on n'obtiendra pas la solution en un temps raisonnable. Il s'agit là d'un aspect fondamental de l'algorithmique. Pour mieux comprendre cela, nous allons nous pencher sur un problème très célèbre qui s'appelle « le problème du voyageur de commerce ». Il s'agit de trouver, pour un ensemble de villes dans lesquelles doit se rendre un voyageur de commerce, l'ordre dans lequel visiter ces villes de façon à passer le moins de temps possible sur la route. C'est à dire qu'il faut que la somme des distances parcourues lors des trajets soit la plus petite possible.

  • Avec deux villes, c'est plutôt facile, il n'y a que deux possibilités pour les visiter. Nommons ces villes a et b. Alors le premier voyage possible, qu'on notera (a,b), consiste à visiter la ville a puis la ville b, et le deuxième voyage possible, qu'on notera (b,a), consiste à visiter la ville b puis la ville a. Peu importe par laquelle on commence, la distance parcourue sera la même.

  • Avec trois villes cela devient un tout petit peu plus compliqué. Il y a six possibilités de voyages qui sont (a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b) et enfin (c,b,a). On peut visiter les villes selon ces 6 différentes possibilités, mais à nouveau la somme des distances parcourues sera toujours la même (car on réalise le même triangle).

  • Par contre avec quatre villes, on aura 24 possibilités et 3 sommes de distances différentes. L’ordre choisi aura donc un impact important sur le temps que mettra le voyageur de commerce, il a donc tout intérêt à définir à l’avance son trajet. Faites le test !

  • Et plus on augmente le nombre de villes, plus le nombre de possibilités est grand...

Il s'agit du même problème que celui des convives à disposer autour de la table. Avec deux invités, que l'on nommera aussi a et b, on peut choisir de les faire s’asseoir dans l'ordre (a,b) ou (b,a). Avec trois invités on retrouve les mêmes possibilités que pour l'ordre des villes. Ce problème se retrouve dans de nombreuses applications comme la tournée du facteur (dans quel ordre placer les rues dans lesquelles il faut passer). C'est encore le même problème dans les usines où des bras articulés (des robots) doivent visser des boulons sur un plaque à différents endroits (dans quel ordre visser les boulons pour minimiser les déplacements et donc économiser de l'énergie et la durée du vie du robot ?).

Quand le nombre « d'objets » (nombre d'invités, nombre d'équipes, nombre de classes, etc.) augmente alors le nombre de possibilités explose. On parle d'explosion combinatoire ou de croissance exponentielle. Nous allons essayer de mieux comprendre cela dans la suite.

Exemple de certificat de réussite
Exemple de certificat de réussite