Le problème du voyageur de commerce est simple à formuler. Il doit visiter un certain nombre de villes, disons dix, en partant d’une ville et en y revenant après avoir visité toutes les autres. Il connaît les distances entre les villes prises deux à deux.
au sommaire
Quel trajet doit suivre le voyageur de commerce pour minimiser la distance parcourue ? On peut déterminer le nombre de trajets possibles assez facilement. Pour cela, on choisit une ville que l'on considère comme la ville de départ. Ensuite, on a neuf choix possibles pour continuer, huit une fois ce choix fait, etc. On obtient ainsi 9 x 8 x 7 x... x 1 trajets possibles.
Comme le sens de parcours ne compte pas, le nombre de trajets possibles est 9 x 8 x 7 x 6 x 5 x 4 x 3 = 181.440. Comparer leurs longueurs est donc faisable à l'aide d'un ordinateurordinateur dans le cas de dix villes.
Question :
L’algorithme résolvant le problème du voyageur de commerce présenté ci-dessus est considéré comme inefficace. Pourquoi ?
Réponse :
Cet algorithme est inefficace car, quand le nombre de villes augmente, il devient vite inapplicable. Par exemple, pour 20 villes, le nombre de trajets à comparer est égal à 60.822.550.204.416.000 ! Si chaque trajet est engendré en une nanoseconde, il faut 60 millions de secondes pour tous les générer tous, ce qui fait environ deux ans. Ainsi, pour 21 villes, il faudra 42 ans, et pour 22, presqu'un millénaire !
Ce problème du voyageur de commerce fait partie d'une classe de problèmes qui pourraient être résolus si l'un des problèmes à un million de dollars de l'Institut Clay était résolu par l'affirmative. Il s'agit de la conjecture « P = NP ».
Hervé Lehning
En savoir plus sur Hervé Lehning
Normalien et agrégé de mathématiques, Hervé Lehning a enseigné sa discipline une bonne quarantaine d'années. Fou de cryptographie, membre de l'Association des réservistes du chiffre et de la sécurité de l'information, il a en particulier percé les secrets de la boîte à chiffrer d'Henri II.
- Son blog MATH'MONDE sur Futura
- Le dernier livre d'Hervé Lehning :
À découvrir également : L'univers des codes secrets de l'Antiquité à Internet paru en 2012 chez Ixelles.