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.

    Un trajet entre dix villes. © Hervé Lehning. Tous droits réservés
    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 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 :

    Le trajet du voyageur de commerce. © Free-photos, Pixabay, DP
    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 ».

    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. 

    Acheter le livre 


    Cliquez pour acheter le livre 

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