Le problème du voyageur de commerce est bien connu des étudiants en informatique : “étant donné n points (des « villes ») et les distances séparant chaque point, trouver un chemin de longueur totale minimale qui passe exactement une fois par chaque point et revienne au point de départ“.
La caractéristique de ce problème est qu’il n’a pas de solution simple, d’où l’utilisation d’algorithmes informatiques pour s’approcher le plus possible d’une solution satisfaisante, avec un temps de calcul raisonnable. Sa résolution est d’ailleurs l’objet de challenges chez les étudiants.
C’est en utilisant un des ces algorithmes que le mathématicien allemand Robert Bosch a réalisé une représentation de Mona Lisa, la célèbre Joconde de Léonard de Vinci à partir d’un seul trait, passant par 100 000 points sans jamais se couper :
). Cette compétition regroupe des chercheurs du monde entier sur ce thème, et le premier prix cette année est cette vidéo qui défie l’entendement :
