Quel sera le trajet le plus court ? © Geralt

Sciences

Jeu mathématique : quel est le trajet optimal d'un voyageur de commerce ?

Question/RéponseClassé sous :Mathématiques , trajet optimal , Mappy

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.

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.

Un trajet entre dix villes. © Hervé Lehning. Tous droits réservés

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 ordinateur 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 :

Le trajet du voyageur de commerce. © Free-photos, Pixabay, DP

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 ».

Abonnez-vous à la lettre d'information Mathématiques amusantes : chaque semaine, Futura traite une question de mathématique pour le plaisir des 7 à 77 ans.

!

Merci pour votre inscription.
Heureux de vous compter parmi nos lecteurs !

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. 

À découvrir également : L'univers des codes secrets de l'Antiquité à Internet paru en 2012 chez Ixelles.