Deux mathématiciens ont annoncé avoir trouvé le plus court chemin pour visiter deux millions d’étoiles, selon New Scientist le 23 octobre. Les Pr Cook, de l’université canadienne de Waterloo, et Helsgaun, de l’université danoise de Roskilde, ont ainsi résolu un casse-tête mathématique à une échelle sans précédent : celle de toute la galaxie.
Le problème du commis voyageur est un casse-tête mathématique dont le but est de trouver le chemin le plus court entre plusieurs endroits, en ne passant qu’une seule fois dans chaque endroit et en revenant à la fin au point initial. Ce problème, qui semble pourtant simple, n’a encore jamais trouvé d’algorithme général permettant de le résoudre.
Son énoncé classique est le suivant : « Un voyageur de commerce doit visiter une et une seule fois un nombre fini de villes et revenir à son point d’origine. Trouvez l’ordre de visite des villes qui minimise la distance totale parcourue par le voyageur. » Non seulement le duo de mathématiciens a trouvé comment résoudre le problème, mais ils y sont parvenus à l’échelle de la galaxie.
Ils ont ainsi créé une carte tridimensionnelle qui trace un parcours entre 2 079 471 étoiles qui sera certainement très utile pour les voyageurs de commerce interstellaire du futur. Sa longueur totale est estimée à 94 208 157,5 années-lumière. Et selon Cook et Roskilde, leur parcours est sans conteste le plus rapide sur cette distance.
Pour calculer le plus court circuit possible à travers les positions 3D de ces deux millions d’étoiles individuelles, il leur a fallu deux ans de travail, entre octobre 2017 et 2019. Il ont aussi utilisé un ensemble de techniques de recherches, des programmations linéaires par plan de coupe ainsi que divers calculs garantissant la qualité de leur découverte.
Source : New Scientist
