Superbe algorithme pour trouver le chemin le plus court –

Lorsque nous nous dirigeons vers une nouvelle destination, la plupart d’entre nous laissons le soin aux algorithmes informatiques de nous aider à trouver le meilleur itinéraire, que ce soit en utilisant le GPS d’une voiture ou en utilisant les transports en commun et les applications cartographiques sur leur téléphone. Pourtant, il y a des moments où un itinéraire proposé ne correspond pas tout à fait à la réalité. En effet, les réseaux routiers, les réseaux de transports publics et autres réseaux ne sont pas statiques. Le meilleur itinéraire peut soudainement être le plus lent, par exemple parce qu’une file d’attente s’est formée en raison de travaux routiers ou d’un accident.

Les gens ne pensent probablement pas aux calculs compliqués derrière les suggestions de routage dans ces types de situations. Le logiciel utilisé tente de résoudre une variante du problème algorithmique classique du “chemin le plus court”, le chemin le plus court dans un réseau dynamique. Depuis 40 ans, les chercheurs s’efforcent de trouver un algorithme capable de résoudre de manière optimale cette énigme mathématique. Aujourd’hui, Christian Wulff-Nilsen du département d’informatique de l’Université de Copenhague a réussi à casser la noix avec deux collègues.

“Nous avons développé un algorithme, pour lequel nous avons maintenant la preuve mathématique, qu’il est meilleur que tous les autres algorithmes jusqu’à présent – et ce qui se rapproche le plus de l’optimal qui le sera jamais, même si nous regardons 1000 ans dans le futur”, dit le professeur agrégé Wulff-Nilsen. Les résultats ont été présentés lors de la conférence FOCS 2020.

De manière optimale, dans ce contexte, fait référence à un algorithme qui consacre le moins de temps et le moins de mémoire possible à l’ordinateur pour calculer le meilleur itinéraire dans un réseau donné. Cela ne vaut pas seulement pour les réseaux routiers et de transport, mais aussi pour Internet ou tout autre type de réseau.

Réseaux sous forme de graphiques

Les chercheurs représentent un réseau sous la forme d’un graphe dit dynamique. “Dans ce contexte, un graphe est une représentation abstraite d’un réseau constitué d’arêtes, de routes par exemple et de nœuds, représentant des intersections, par exemple. Lorsqu’un graphe est dynamique, cela signifie qu’il peut changer au fil du temps. Le nouvel algorithme gère les changements consistant en des arêtes supprimées – par exemple, si l’équivalent d’un tronçon de route devient soudainement inaccessible en raison de travaux routiers.

«L’énorme avantage de voir un réseau comme un graphe abstrait est qu’il peut être utilisé pour représenter n’importe quel type de réseau. Il peut s’agir d’Internet, où vous souhaitez envoyer des données par une voie aussi courte que possible, d’un cerveau humain ou du réseau de relations d’amitié sur Facebook. Cela rend les algorithmes de graphes applicables dans une grande variété de contextes », explique Christian Wulff-Nilsen.

Les algorithmes traditionnels supposent qu’un graphique est statique, ce qui est rarement vrai dans le monde réel. Lorsque ces types d’algorithmes sont utilisés dans un réseau dynamique, ils doivent être réexécutés chaque fois qu’un petit changement se produit dans le graphique – ce qui fait perdre du temps.

Plus de données nécessitent de meilleurs algorithmes

Trouver de meilleurs algorithmes n’est pas seulement utile lorsque vous voyagez. Elle est nécessaire dans pratiquement tous les domaines où des données sont produites, comme le souligne Christian Wulff-Nilsen:

«Nous vivons à une époque où les volumes de données augmentent à un rythme effréné et où le développement du matériel ne peut tout simplement pas suivre. Afin de gérer toutes les données que nous produisons, nous devons développer des logiciels plus intelligents qui nécessitent moins de temps d’exécution. et de la mémoire. C’est pourquoi nous avons besoin d’algorithmes plus intelligents », dit-il.

Il espère qu’il sera possible d’utiliser cet algorithme ou certaines des techniques qui le sous-tendent dans la pratique, mais souligne qu’il s’agit d’une preuve théorique et nécessite d’abord une expérimentation.

Fond

• L’article de recherche “Near-Optimal Decremental SSSP in Dense Weighted Digraphs” a été présenté lors de la prestigieuse conférence FOCS 2020.
• L’article a été écrit par Christian Wulff-Nilsen, du Département d’informatique de l’Université de Copenhague, et l’ancien doctorant du Département d’informatique Maximillian Probst Gutenberg et le professeur assistant Aaron Bernstein de l’Université Rutgers.
• La version du problème du «chemin le plus court» que les chercheurs ont résolu s’appelle «le problème du chemin le plus court décrémental à source unique». Il s’agit essentiellement de maintenir les chemins les plus courts dans un réseau dynamique changeant d’un point de départ à tous les autres nœuds d’un graphe. Les modifications apportées à un réseau consistent en des suppressions de bord.
• L’article donne une preuve mathématique que l’algorithme est essentiellement le meilleur pour les réseaux dynamiques. En moyenne, les utilisateurs pourront changer d’itinéraires en fonction de calculs effectués en temps constant.