L’un des problèmes d’algorithme les plus connus est lié au calcul du plus court trajet entre deux points. Une variante plus complexe de ce casse-tête consiste à faire passer la trajectoire au sein d’un réseau changeant, que ce soit un réseau routier ou le web. Pendant 40 ans, des chercheurs ont voulu concevoir un algorithme offrant une solution optimale à ce problème. Maintenant, le chercheur en informatique Christian Wulff-Nilsen, de l’Université de Copenhague, croit avoir trouvé une solution en compagnie de deux collègues.
En se rendant à une nouvelle destination, la plupart d’entre nous faisons confiance à des algorithmes informatiques pour calculer le meilleur trajet, que ce soit en utilisant un GPS dans la voiture, ou les transports publics et des applications de cartographie sur téléphone intelligent. Malgré tout, il survient des occasions où les trajets proposés ne correspondent pas tout à fait à la réalité. Cela s’explique par le fait que les réseaux routiers, ceux des transports collectifs et d’autres réseaux ne sont pas statiques. Le meilleur trajet peut soudainement devenir le plus lent, par exemple parce que les véhicules ont soudainement ralenti en raison de travaux de construction ou d’un accident.
Les gens ne pensent probablement pas aux équations mathématiques complexes sous-tendant les suggestions de chemins à emprunter dans ce genre de situations. Le logiciel utilisé tente de trouver une variante au problème algorithmique classique du « plus court trajet », c’est-à-dire le plus court trajet au sein d’un réseau dynamique.
Pendant 40 ans, des chercheurs ont tenté de trouver un algorithme qui peut résoudre ce casse-tête mathématique de façon optimale. M. Wulff-Nilsen estime y être parvenu.
« Nous avons conçu un algorithme, pour lequel nous disposons maintenant d’une preuve mathématique, qui est meilleur que tout autre algorithme développé jusqu’à maintenant, et s’avère être la chose la plus optimale qui sera jamais créée, même pour une période de 1000 ans », affirme M. Wulff-Nilsen.
L’adjectif optimal, dans ce contexte, fait référence à un algorithme qui consacre le moins de temps possible et le moins de mémoire informatique possible pour calculer le meilleur itinéraire au sein d’un réseau donné. Cela ne s’applique pas seulement aux réseaux routiers, mais aussi au web, ou à tout autre genre de réseau.
Des réseaux sous forme de graphiques
Les chercheurs représentent un réseau comme un graphique dynamique. Dans le contexte, un graphique est une représentation abstraite d’un réseau formé d’arrêtes, des routes, par exemple, ainsi que des points de convergence, qui représentent les intersections, entre autres.
Lorsqu’un graphique est dynamique, cela veut dire qu’il peut changer avec le temps. Le nouvel algorithme gère ces changements, notamment lorsqu’une arrête disparaît. Sur le terrain, cela pourrait équivaloir à une section de route rendue inaccessible en raison de travaux.
« Le grand avantage de voir un réseau comme un graphique abstrait est le fait qu’il peut être utilisé pour représenter tout type de réseau. Cela pourrait être le web, où vous voulez envoyer des données selon le plus court trajet possible, comme un cerveau humain, ou un réseau d’amis sur Facebook. Cela permet d’utiliser les algorithmes de création de graphiques dans une grande variété de contextes », explique encore M. Wulff-Nilsen.
Les algorithmes traditionnels tiennent pour acquis qu’un graphique est statique, ce qui est rarement vrai dans le monde réel. Lorsque ce genre d’algorithmes sont utilisés dans un réseau dynamique, ils doivent être relancés chaque fois qu’un changement se produit au sein du graphique, ce qui gaspille du temps.
