• 15 hours
  • Easy

Free online content available in this course.

Videos available in this course

Certificate of achievement available at the end this course

Got it!

Last updated on 7/11/17

Quel est le problème du voyageur de commerce ?

Log in or subscribe for free to enjoy all this course has to offer!

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.

Example of certificate of achievement
Example of certificate of achievement