Trouver le meilleur itinéraire posait un problème qui n’avait pas été résolu depuis 70 ans. Un algorithme a trouvé la solution en le temps qu'il vous faut pour cligner des yeux

Dans les années 1950, les informaticiens ont réalisé quelque chose. À mesure que la société progressait, devenait plus grande et plus dense, ainsi que ses réseaux de transport, les ralentissements de la circulation, les agglomérations ou les congestions de toutes sortes devenaient plus palpables. Depuis, les idées et les propositions n'ont cessé de chercher à résoudre le problème des « embouteillages » et à rendre leurs flux plus efficaces. La solution était un algorithme « absurdement rapide ».

La publicité. Une équipe de chercheurs de l'ETH Zurich a présenté ce qui est, en théorie, l'algorithme de flux de réseau le plus rapide possible lors du symposium annuel de l'ACM sur la théorie de l'informatique. Les travaux pionniers de l’équipe dirigée par le chercheur Rasmus Kyng abordent la question longtemps débattue de savoir comment atteindre un débit maximal dans un réseau tout en minimisant les coûts de transport.

Un exemple avant de l'expliquer plus en détail. Imaginez que vous utilisez un réseau de transport européen à la recherche de l'itinéraire le plus rapide et le moins cher pour transporter la plus grande quantité possible de marchandises de Madrid à Londres. L'algorithme de Kyng peut être appliqué dans ces cas pour calculer le flux de trafic optimal et le moins coûteux pour tout type de réseau, qu'il soit ferroviaire, routier, fluvial ou Internet. Et il le fait si vite que cela fait peur : il peut apporter la solution au moment même où un ordinateur lit les données décrivant le réseau.

Contexte. Comme nous l’avons dit au début, l’ampleur de ce que l’équipe Kyng a réalisé constitue une étape importante. Une réalisation qui offre une solution sans précédent à un problème qui tourmente les chercheurs depuis 70 ans : le flux maximum, ou comment obtenir le flux d'informations le plus rapide à travers un système aux capacités limitées.

Histoire d'un problème non résolu. Le problème du débit maximal a été formalisé dans les années 1950 par Lester R. Ford et Delbert Fulkerson, qui ont introduit un célèbre algorithme, connu sous le nom d'algorithme de Ford-Fulkerson, pour le résoudre. Le problème s'est posé dans le contexte de la planification des infrastructures, telles que les réseaux de transport, l'approvisionnement en eau et les télécommunications. Dans celui-ci, nous avons un réseau dirigé où chaque bord a une capacité qui indique la quantité maximale de flux qui peut le traverser.

La proposition Ford-Fulkerson a été l’une des premières méthodes proposées pour résoudre le casse-tête grâce à ce qu’ils ont appelé la « solution gourmande ». Il fonctionne en recherchant des chemins croissants, c'est-à-dire des chemins allant de la source au puits où le débit peut être augmenté. Une fois qu'une route avec une capacité disponible est trouvée, le flux sur cette route est augmenté et le processus est répété jusqu'à ce qu'une route disponible ne puisse plus être trouvée.

L'exemple. Pour le comprendre, rien de mieux que la question qu’ils ont posée. Imaginez le problème de l'optimisation du trafic se déplaçant d'un point A à un point B le long de plusieurs itinéraires possibles, un itinéraire composé d'un premier segment qui est une autoroute à six voies et le dernier d'une autoroute à trois voies. Pour le résoudre, l'algorithme glouton projette autant de trafic que possible (trois voies de voitures) le long de l'itinéraire, ajustant sa capacité et répétant les mêmes étapes pour les autres itinéraires jusqu'à ce que tous les itinéraires possibles soient à pleine capacité.

Et oui, la vérité est que la proposition des chercheurs était efficace, mais elle présentait un problème : elle ne produisait souvent pas le meilleur flux possible. Si d’autres itinéraires étaient coupés et que des embouteillages non optimaux survenaient, l’algorithme décidait de laisser les choses ainsi. Depuis 70 ans, des contributions ont été apportées au problème en essayant d'affiner cet aspect de la solution, en atténuant les ralentissements inutiles en intégrant une meilleure prise de décision dans l'algorithme.

Petites améliorations. Par exemple, l'algorithme a ensuite été affiné avec des implémentations plus efficaces, telles que l'algorithme d'Edmonds-Karp, qui utilise la recherche en largeur pour trouver le chemin croissant le plus court. Cet ajustement et d'autres ont modifié la durée d'exécution de l'algorithme d'un multiple de m ^ 2 (où m est le nombre de nœuds du réseau) à un multiple de m ^ 1,33 en 2004, mais les progrès ont ensuite stagné.

L’algorithme « absurdement rapide ». Et nous arrivons à l'annonce révolutionnaire de ces jours-ci. Pour ce faire, Kyng et son équipe ont combiné les précédentes : la solution originale qui traitait les réseaux comme du trafic ; et un plus récent qui, au contraire, les considérait comme un réseau électrique. Contrairement aux voitures ou aux trains, le flux d’électrons peut être partiellement détourné pour rejoindre le courant le long d’un autre itinéraire, ce qui permet aux informaticiens de tracer le meilleur flux à travers l’ensemble du réseau avant d’appliquer l’approche du trafic segment par segment.

Cette combinaison a donné un résultat qui ressemble à un algorithme hybride, « absurdement rapide », selon la déclaration de Daniel A. Spielman, professeur de mathématiques appliquées et d'informatique à l'Université de Yale qui a supervisé le programme de doctorat de l'un des chercheurs. En fait, Spielman a comparé la nouvelle solution aux précédentes, comme s'il s'agissait d'une « Porsche dépassant des calèches ».

Une comparaison précise et une avancée qui promet de révolutionner de nombreux domaines, depuis les données Internet, les itinéraires de trafic et de transport, la planification des vols sur le réseau, jusqu'à l'amélioration de l'efficacité du marché.

Images | Domaine public, YouTube

À Simseo | Le MIT a découvert un problème mathématique impossible. Et c'est dans tous les jeux Mario 2D

À Simseo | Un ancien problème de géométrie inquiète les mathématiciens depuis des décennies. Ils l'ont finalement résolu