Problèmes informatiques de base, le problème du débit maximum a fait des progrès décisifs : le nouvel algorithme est « ridiculement rapide »

Ce problème est très basique dans la théorie des flux de réseau. "Le nouvel algorithme est ridiculement rapide. En fait, j'étais convaincu qu'il n'existait pas d'algorithme aussi efficace pour résoudre ce problème", a déclaré Daniel Spielman de l'Université de Yale.

Les débits maximaux sont étudiés depuis les années 1950, lorsqu'ils étaient étudiés pour modéliser les systèmes ferroviaires soviétiques. "L'étude de ce sujet est encore plus ancienne que la théorie informatique", déclare Edith Cohen du centre de recherche de Google à Mountain View, en Californie.

Cette question mène à de nombreuses applications : streaming de données sur Internet, planification des compagnies aériennes, voire mise en relation entre demandeurs d'emploi et postes vacants. Ce nouvel article traite à la fois du problème du débit maximum et du problème plus général de la gestion du débit maximum tout en souhaitant également minimiser les coûts. Ces deux questions ont inspiré de nombreuses avancées significatives dans la technologie algorithmique au fil des ans. "C'est à peu près la raison pour laquelle nous continuons à travailler sur des algorithmes", a déclaré Spielman. Le nouvel algorithme résout les deux problèmes en un temps "approximativement linéaire", ce qui signifie que le temps d'exécution de l'algorithme est fondamentalement le même que celui de l'enregistrement des détails du réseau. Aucun autre algorithme permettant de résoudre ces problèmes ne peut atteindre cette vitesse pour tous les réseaux possibles. Satish Rao, de l'Université de Californie à Berkeley, a déclaré que ce résultat l'a fait sursauter : "C'est tout simplement incroyable."

Spielman pense que nous avons trouvé un algorithme si rapide, et il est maintenant temps de commencer à réfléchir à des solutions qui nous n'avons pas pensé auparavant à divers problèmes d'application.

À l'heure actuelle, la nouvelle méthode est principalement une amélioration théorique, car l'amélioration de la vitesse des algorithmes n'est applicable qu'à des réseaux beaucoup plus grands que ceux rencontrés dans le monde réel, pour lesquels le problème du débit maximum peut déjà être résolu très rapidement. réponse (du moins sans considérer la minimisation des coûts). Richard Peng, de l'Université de Waterloo au Canada, l'un des six créateurs du nouvel algorithme, s'attend à ce qu'il puisse être utilisé en pratique d'ici un an.

Certains chercheurs pensent que dans les prochaines années, les informaticiens pourraient trouver des moyens de le rendre plus pratique, et peut-être même plus rapide.

Aleksander Mądry du MIT a déclaré que même s'il y a des améliorations à l'avenir, ce nouvel article est "le dunk le plus excitant du concours de slam dunk". Il a dit que c'était fondamentalement le meilleur."

Un chemin à la fois

Richard Peng a déclaré que de nombreux informaticiens étudient le problème du débit maximal, à tel point que discuter de travaux antérieurs lors d'une conférence revient à passer le générique final d'un film. Mais la plupart conviennent que le premier algorithme formel était l'application en 1956 d'un algorithme glouton pour le débit maximum par Lester Ford et Delbert Fulkerson, qui utilise l'objet le plus facilement disponible à chaque étape.

Vous pouvez penser à cette approche comme ceci : tout d'abord, imaginez un réseau autoroutier et vous souhaitez déplacer autant de camions de livraison que possible de Los Angeles à New York dans un temps donné. L'algorithme de Ford et Fulkerson commence par choisir un chemin de Los Angeles à New York et acheminer autant de camions que possible le long de ce chemin. Cette méthode n'utilise généralement pas la pleine capacité de toutes les routes sur cette route particulière : si la route est une autoroute à cinq voies mais qu'elle traverse un pont à deux voies, vous ne pouvez faire circuler que deux camions à la fois.

Ensuite, l'algorithme modifie la capacité de ces segments pour refléter qu'une partie de la capacité du segment est désormais utilisée : il soustrait le nombre de camions envoyés de la capacité du segment, de sorte que l'autoroute à cinq voies a désormais une capacité de 3 , alors que la capacité du pont à deux voies est nulle. Dans le même temps, l'algorithme ajoute 2 à la capacité de ces routes en sens inverse, ce qui nous permet de retirer une partie du trafic plus tard si nous le souhaitons.

L'algorithme trouve ensuite un nouveau chemin de Los Angeles à New York pouvant accueillir certains camions, envoie autant de camions que possible le long du chemin et met à jour à nouveau la capacité. Après un nombre limité de ces étapes, la route de Los Angeles à New York ne pourra plus accueillir de camions, et à ce stade l'algorithme est complet : on combine simplement tous les flux construits pour obtenir le flux maximum possible de le réseau.

L’algorithme de Ford et Fulkerson ne tente pas de faire des choix intelligents en cours de route. S'il choisit un chemin qui coupe d'autres chemins utiles, c'est un problème que l'algorithme devra résoudre plus tard. Au cours des décennies qui ont suivi la publication de l'algorithme, les chercheurs ont tenté d'accélérer les temps d'exécution en permettant à l'algorithme de faire des choix plus intelligents, comme toujours utiliser le chemin disponible le plus court ou celui ayant la plus grande capacité disponible. En 1970, Yefim Dinitz a découvert un moyen efficace d'utiliser tous les chemins les plus courts d'un réseau en une seule étape. Le temps d'exécution de cet algorithme dans les réseaux de faible capacité a été prouvé par Shimon Even et Robert Tarjan comme étant m ^ 1,5 (m : le nombre de liens dans le réseau. En revanche, l'algorithme de Ford-Fulkerson nécessite plusieurs m dans les réseaux de faible capacité. réseaux. ^2).

Près de 30 ans plus tard, Rao et Andrew Goldberg sont parvenus à des résultats similaires pour les réseaux à haute capacité. Mais personne ne peut battre l’indice m^1,5. "À l'aube du 21e siècle... les obstacles à l'accès à m^1,5 sont profondément ancrés", a déclaré Sushant Sachdeva de l'Université de Toronto, l'un des auteurs du nouvel article. Pour progresser davantage, les informaticiens doivent trouver des moyens d'y parvenir complètement. Différentes méthodes.

De la combinaison au calcul

Jusqu'à présent, tous ces algorithmes ont adopté une approche combinatoire, c'est-à-dire rechercher un certain type de structure à chaque étape et utiliser cette structure pour mettre à jour le flux. Mais en 2003, Spielman et ShangHua Teng de l'Université de Californie du Sud ont ouvert la porte à une approche totalement différente de « l'optimisation », dans laquelle les techniques de calcul sont utilisées comme guide pour trouver des solutions optimales.

Spielman et Teng ont développé un algorithme d'optimisation rapide qui résout non pas le problème du débit maximal, mais le problème étroitement lié de la recherche du courant d'énergie le plus faible à travers chaque réseau de fils avec une résistance donnée. Sachdeva a déclaré que les progrès de Spielman et Teng étaient des « moments critiques ».

Membres de l'équipe qui ont créé l'algorithme ultra-rapide pour déterminer le trafic maximum et le coût minimum d'un réseau (dans le sens des aiguilles d'une montre à partir du coin supérieur gauche) : Yang Liu, Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg, Richard Peng, Sushant Sachdeva.

Les chercheurs ont rapidement commencé à explorer comment appliquer ces progrès au problème du débit maximal. Considérez le réseau routier comme un réseau de câbles qui ajoutent de la résistance sur les routes qui n'ont pas beaucoup de capacité disponible, empêchant ainsi les électrons de les traverser. Grâce aux travaux de Spielman et Teng, nous pouvons calculer rapidement le courant traversant ces fils, et ce modèle possède des propriétés approximatives pour un débit maximal des véhicules sur l'autoroute. (Ils ne seront pas exactement les mêmes, puisque le problème actuel ne met aucune limite stricte à la capacité du fil.)

Ensuite, après avoir généré ce flux initial, nous pouvons redimensionner la capacité comme celle de Ford et Fulkerson. algorithme combiné. Ensuite, la résistance de chaque fil peut être réinitialisée pour refléter ces changements et résoudre les problèmes de circuit nouvellement créés.

Contrairement à la méthode combinatoire qui modifie un bloc de réseau à la fois, la méthode d'optimisation de Spielman et Teng complète à chaque fois l'analyse de l'ensemble du réseau. Cela rend chaque étape plus efficace, donc moins d'étapes au total sont nécessaires pour atteindre le maximum. En 2008, Samuel Daitch et Spielman de Google ont utilisé cette méthode, qui correspondait essentiellement à la limite précédente de trafic maximum de m^1,5. En 2013, Mądry a encore avancé l'approche pour dépasser m^1,5 pour les réseaux de faible capacité, améliorant ainsi les durées d'exécution à environ un multiple de m^1,43. "C'est choquant", a déclaré Rao.

Au cours des années suivantes, les chercheurs ont encore étendu cette méthode, mais leurs résultats sont restés bloqués à m^1,33. Ils ont commencé à se demander si cet indice constituait une limite fondamentale.

Pour l'algorithme de débit maximum, le temps d'exécution le plus rapide imaginable devrait être de m fois (c'est-à-dire m^1,0), car l'écriture d'un réseau nécessite un multiple de m étapes. C'est ce qu'on appelle le temps linéaire. Mais pour de nombreux chercheurs, un algorithme aussi extrêmement rapide semblait impensable. "Il n'y a aucune bonne raison de croire que nous pouvons faire cela", a déclaré Spielman.

Réduire, réutiliser, recycler

Les auteurs de ce nouvel article estiment que l’approche de Daitch et Spielman présente d’autres avantages. Mądry l'avait utilisé pour réduire le nombre d'étapes nécessaires pour résoudre le problème du débit maximal, mais cette réduction avait un coût : à chaque étape, l'ensemble du réseau devait être réécrit et le problème du flux d'énergie devait être résolu à partir de zéro.

Cette approche traite l’algorithme de Spielman et Teng comme une boîte noire – peu importe ce qui se passe à l’intérieur de l’algorithme. Six chercheurs ont décidé de plonger au cœur de l'algorithme et d'adapter ses composants au problème du débit maximal. Ils soupçonnent que ces composants pourraient même leur permettre de résoudre le problème plus difficile du « coût minimum », dans lequel il s’agit de trouver le moyen le moins coûteux de transporter une quantité donnée de matériau. Les informaticiens savent depuis longtemps que n’importe quel algorithme de coût minimum peut résoudre le problème. problème de débit maximum. Question.

Comme pour d'autres méthodes d'optimisation, les chercheurs ont proposé le concept de flux « énergie » en fonction du coût et de la capacité de la liaison. Le déplacement du trafic de liaisons coûteuses de faible capacité vers des liaisons bon marché de grande capacité réduit l’énergie totale du système.

Pour comprendre comment déplacer rapidement le flux vers un état de plus faible énergie, les chercheurs ont combiné cette approche d'optimisation avec une ancienne vue combinatoire. Ce dernier ne modifie qu'une partie du réseau à la fois, offrant la possibilité de réutiliser une partie du travail des étapes précédentes.

A chaque étape, l'algorithme recherche un cycle qui peut réduire l'énergie, c'est-à-dire un chemin qui commence et se termine au même point. L’idée de base est simple : supposons que vous créiez une route à péage entre Chicago et New York, puis que vous découvriez qu’il existe une autoroute moins chère. À ce stade, ajouter New York à la boucle, en empruntant la route coûteuse jusqu'à Chicago, puis en revenant sur la route la moins chère, crée une boucle qui remplace la route coûteuse, réduisant ainsi le coût global du trafic.

Valerie King de l'Université de Victoria au Canada a déclaré que cette méthode utilise beaucoup plus d'étapes que la "méthode électrique", donc cela ressemble "à un pas en arrière" à première vue. Pour compenser, l’algorithme doit trouver les bonnes boucles à chaque étape incroyablement rapidement, plus rapidement qu’il ne le faudrait pour examiner l’ensemble du réseau.

C’est ainsi que fonctionne l’algorithme de Spielman et Teng. Leur algorithme fournit une nouvelle façon d'utiliser les « arbres couvrants à faible étirement », qui sont la clé de l'algorithme et peuvent capturer bon nombre des caractéristiques les plus importantes d'un réseau. Etant donné un tel arbre, il est toujours possible de construire au moins un bon cycle en ajoutant un lien en dehors de l'arbre. Par conséquent, disposer d’un arbre couvrant à faible échelle peut réduire considérablement le nombre de cycles à prendre en compte.

Même ainsi, afin que l'algorithme s'exécute rapidement, l'équipe ne peut pas construire un nouvel arbre couvrant à chaque étape. Au lieu de cela, ils doivent s’assurer que chaque nouveau cycle ne crée qu’un petit effet d’entraînement dans l’arbre couvrant afin que la plupart des calculs précédents soient réutilisés. Atteindre ce niveau de contrôle est « la principale difficulté », a déclaré Yang Liu, étudiant diplômé à l'Université de Stanford et l'un des auteurs de l'article.

En fin de compte, les chercheurs ont créé un algorithme qui s'exécute dans un temps « presque linéaire », ce qui signifie que lors de l'utilisation de réseaux plus grands, sa durée d'exécution se rapproche de m.

Cet algorithme emprunte de nombreuses idées à Spielman et Teng et les combine en quelque chose de complètement nouveau. Si vous n'avez jamais vu qu'une charrette tirée par des chevaux, a déclaré Spielman, les algorithmes d'aujourd'hui sont comme des voitures. "Je vois qu'il a une place pour s'asseoir, je vois qu'il a des roues, je vois qu'il a quelque chose pour le déplacer. Mais ils ont remplacé les chevaux par des moteurs."

Rao spécule que l'analyse de l'équipe a été longue. et complexe, mais d'autres chercheurs se sont rapidement penchés sur le sujet pour simplifier le problème. "Mon sentiment est que dans les prochaines années, tout deviendra plus propre et meilleur", a-t-il déclaré. Une fois l'algorithme simplifié, les informaticiens pourraient commencer à l'utiliser comme algorithme pour résoudre différents problèmes, a déclaré Spielman. "Maintenant que nous savons que nous pouvons le faire très rapidement, les gens trouveront toutes sortes d'applications auxquelles ils n'avaient pas pensé auparavant."

De plus, l'accélération vertigineuse de l'algorithme pour le problème du débit maximum, ce qui a fait attendre Spielman avec impatience. d'autres questions fondamentales en théorie des algorithmes, "Que pouvons-nous faire d'autre ?"

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!