Les mathématiciens connaissent le fameux “Travelling Salesman Problem” (TSP), mais pour ceux d’entre vous qui ne sont pas obsédés par les algorithmes informatiques ou la planification urbaine, disons simplement que c’est l’un des problèmes mathématiques les plus persistants jamais conçus, ainsi qu’un repère majeur utilisé pour tester la vitesse et la qualité avec lesquelles un ordinateur peut résoudre un problème. Aujourd’hui, un moule à bave unicellulaire a démontré qu’il peut trouver des solutions presque optimales à ce problème, et ce, dans des délais impressionnants.
Le problème du vendeur itinérant est généralement le suivant : un vendeur itinérant veut planifier un voyage dans, disons, 15 villes des États-Unis, mais il ne veut pas faire de kilomètres supplémentaires s’il n’en a pas besoin. Il ne veut pas non plus visiter deux fois la même ville et veut terminer le voyage de retour par où il a commencé. Parce que ces villes sont dispersées à travers les États-Unis, planifier le trajet le plus court qui les visite toutes exactement une seule fois devient un problème difficile, d’autant plus que vous devriez explorer toutes les options de trajet pour vous assurer qu’il n’y a pas un meilleur trajet que celui que vous avez manqué auparavant. Si vous ajoutez plus de villes au problème, le temps qu’il faut à un ordinateur pour “résoudre” le problème augmente exponentiellement en raison de la prolifération des routes.
Dans le jargon de l’informatique, le TSP est un problème “NP-hard”, et un défi majeur pour l’optimisation.
Mais selon une nouvelle étude publiée dans la revue Royal Society Open Science, un plasmodium, également connu sous le nom d'”amibe de moisissure vraie”, a permis de résoudre un problème de TSP impliquant quatre “villes”, puis huit. L’expérience consistait à placer de la gélose – une substance alimentaire semblable à de la gelée – à divers endroits dans une boîte de Pétri, puis à placer l’amibe au centre de tout cela. De là, c’était à l’amibe de trouver le meilleur moyen d’atteindre tous les morceaux de gélose. Ce qui est intéressant, c’est que le temps qu’il a fallu à l’amibe pour résoudre le problème des huit ” villes ” n’était pas une augmentation exponentielle par rapport au problème des quatre villes précédentes, ce qui signifie qu’elle avait trouvé une nouvelle façon plus efficace de ” résoudre ” le TST.
Selon Masashi Aono, le chercheur principal de l’étude : “Comment l’amibe maintient la qualité de la solution approximative, c’est-à-dire le court trajet, reste un mystère.”
Chris Mahon
