ETH-Forschende entwickeln den schnellstmöglichen Fluss-Algorithmus

Dieser Durchbruch klingt fast nach Lucky Luke, dem Mann, der schneller schiesst als sein Schatten. Rasmus Kyng und sein Team haben einen superschnellen Algorithmus entwickelt, der ein ganzes Forschungsgebiet ver?ndern d¨¹rfte. Genau genommen hat Kyngs Team einen so genannten Netzwerkfluss-Algorithmus geschrieben, der die Frage beantwortet: ?Wie l?sst sich in einem Netzwerk ein maximaler Verkehrsfluss bei zugleich minimalen Transportkosten erreichen??

Stellen Sie sich vor, Sie benutzen das europ?ische Verkehrsnetz und wollen den schnellsten und billigsten Weg finden, um m?glichst viele G¨¹ter von Kopenhagen nach Mailand zu transportieren. F¨¹r solche F?lle berechnet Kyngs Algorithmus den optimalen und kosteng¨¹nstigsten Verkehrsfluss, und zwar f¨¹r jede Art von Netzwerk, egal, ob Schiene, Strasse, Wasser oder Internet. Sein Algorithmus rechnet nun so schnell, dass er bereits im selben Moment, in dem ein Computer ¨¹berhaupt erst die Daten gelesen hat, die das Netzwerk beschreiben, auch schon die L?sung pr?sentiert.

Er rechnet so schnell wie ein Netz gross ist

Das hat vor Rasmus Kyng noch niemand geschafft. Obwohl seit rund 90 Jahren an diesem Problem geforscht wird. Bislang dauerte die Berechnung des optimalen Verkehrsflusses immer deutlich l?nger als die Verarbeitung der Netzwerkdaten. Es war sogar so, dass die ben?tigte Rechenzeit mit zunehmender Gr?sse und Komplexit?t eines Netzwerks vergleichsweise noch viel st?rker anwuchs als die eigentliche Gr?sse des jeweiligen Rechenproblems. Deshalb gibt es auch Flussprobleme in Netzwerken, die zu gross sind, als dass sie ein Computer ¨¹berhaupt berechnen k?nnte.

Bei Rasmus Kyng ist das nicht so: bei seinem Algorithmus w?chst die Rechenzeit im selben Mass an, wie die Gr?sse des Netzwerks zunimmt ¨C das ist etwa so, wie wenn Sie sich auf eine Bergwanderung begeben und ihr Schritttempo l?sst keine Minute nach, selbst wenn der Wanderweg immer steiler wird! Diese Leistung spiegelt sich in den nackten Zahlen: Bis zur Jahrtausendwende schaffte es kein Algorithmus schneller zu rechnen als m^1,5, wobei m f¨¹r die Anzahl Verbindungen in einem Netz steht, die der Computer berechnen muss ¨C und nur schon die Netzwerkdaten einmal zu lesen, nimmt m Zeit in Anspruch. Ab 2004 gelang es, die zur Probleml?sung ben?tigte Rechenzeit auf m^1,33 zu senken. Mit dem Algorithmus von Kyng ist nun die ?zus?tzliche? erforderliche Rechenzeit, um nach dem Lesen der Netzdaten eine L?sung zu erhalten, schlicht vernachl?ssigbar.   

Wie ein Porsche gegen Pferdekutschen

Damit haben die ETH-Forschenden den theoretisch schnellstm?glichen Netzwerkfluss-Algorithmus entwickelt. Den mathematischen Beweis daf¨¹r haben Rasmus Kyng und sein Team vor zwei Jahren in einem bahnbrechenden Paper erbracht. In der Fachsprache heissen die neuartigen, nahezu optimal schnellen Algorithmen auch ?fast-linearzeitliche Algorithmen?. Die Gemeinschaft der theoretischen Informatiker:innen jedenfalls hat positiv ¨¹berrascht und begeistert auf Kyngs Durchbruch reagiert.

Kyngs Doktorvater Daniel A. Spielman, Mathematik- und Informatikprofessor in Yale und selbst ein Pionier und Doyen auf diesem Gebiet, verglich den ?absurd schnellen? Algorithmus mit einem Porsche, der Pferdekutschen ¨¹berholt. Ihre Arbeit wurde 2022 am ?Annual IEEE Symposium on Foundations of Computer Science? als das beste Paper ausgezeichnet sowie vom Informatik-Journal ?Communications of the ACM? als Highlight gew¨¹rdigt, und das popul?rwissenschaftliche ?Quanta Magazine? z?hlte Kyngs Algorithmus zu den externe Seite zehn gr?ssten Entdeckungen des Jahres 2022 in der Informatik.

Seither haben die ETH-Forschenden ihren Ansatz verfeinert und weitere fast-linearzeitliche Algorithmen entwickelt. Zum Beispiel bezog sich der erste Algorithmus noch auf unver?nderliche, statische Netze, deren Verbindungen gerichtet sind, also wie Einbahnstrassen in st?dtischen Strassennetzen funktionieren. Die in diesem Jahr ver?ffentlichten Algorithmen k?nnen nun auch optimale Fl¨¹sse f¨¹r Netzwerke berechnen, die sich schrittweise mit der Zeit ver?ndern. Namentlich f¨¹r sehr komplexe und sehr datenreiche Netzwerke, die sich ¨C wie in der Biologie etwa Molek¨¹le oder das Hirn oder wie menschliche Freundschaftsbeziehungen ¨C dynamisch und sehr schnell ver?ndern, wird eine blitzschnelle Berechnung ein wichtiger Schritt.

Blitzschnelle Algorithmen f¨¹r wandelbare Netzwerke

Am Donnerstag nun hat Simon Meierhans aus Kyngs Team in Vancouver am ?Annual ACM Symposium on Theory of Computing (STOC)? einen neuen fast-linearzeitlichen Algorithmen vorgestellt. Dieser l?st das Minimum-Cost-Maximum-Flow-Problem auch f¨¹r Netzwerke, die sich schrittweise ver?ndern, indem neue Verbindungen dazukommen. In einem zweiten Paper, das das ?IEEE Symposium on Foundations of Computer Science (FOCS)? vom n?chsten Oktober angenommen hat, haben die ETH-Forscher zudem einen weiteren Algorithmus entwickelt, der auch das Entfernen von Verbindungen ber¨¹cksichtigt.

Diese Algorithmen ermitteln die k¨¹rzesten Routen namentlich in Netzen, in denen Verbindungen hinzugef¨¹gt oder entfernt werden. In realen Verkehrsnetzen treten solche Ver?nderungen zum Beispiel dann auf, wenn wie seit dem Sommer 2023 der Gotthard-Basistunnel zun?chst ganz und dann teilweise gesperrt ist oder wenn aktuell ein Erdrutsch einen Teil der Nationalstrasse A13 zerst?rt, welche die wichtigste Alternativroute zum Gotthard-Strassentunnel ist.

Wie berechnet in solchen F?llen ein Computer, ein Online-Kartendienst oder Verkehrsroutenplaner die schnellste und g¨¹nstigste Verbindung zwischen Mailand und Kopenhagen? Kyngs neue Algorithmen berechnen die optimale Route f¨¹r diese schrittweise sich ver?ndernden Netzwerke ebenfalls in fast linearer Zeit, also so schnell, dass die Rechenzeit f¨¹r jede neu ¨C durch Umleitung oder Neubau ¨C hinzukommende Verbindung wiederum vernachl?ssigbar ist.

Was genau macht nun Kyngs Berechnungsmethode so viel schneller als alle anderen Netzwerkfluss-Algorithmen? Im Prinzip kennen alle Berechnungsans?tze die Herausforderung, dass sie das Netzwerk in mehreren Iterationen durchrechnen m¨¹ssen, um den optimalen Fluss und die g¨¹nstigste Route zu finden. Dabei rechnen sie jeweils die verschiedenen Varianten durch, welche Verbindungen offen, gesperrt oder verstopft sind, wenn sie ihre Kapazit?tsgrenze erreicht haben.

Was berechnen? Das Ganze oder seine Teile?

Vor Rasmus Kyng gab es haupts?chlich zwei L?sungsstrategien: die eine orientierte sich am Eisenbahnnetz und berechnete jeweils pro Iteration eine ganze Teilstrecke mit ver?ndertem Verkehrsfluss. Die andere war vom elektrischen Fluss im Stromnetz inspiriert. Sie berechnete pro Iteration jeweils das gesamte Netzwerk, verwendete jedoch f¨¹r den ver?nderten Fluss einer Teilstrecke jeweils statistische Mittelwerte, um schneller zu rechnen.

Rasmus Kyngs Team ber¨¹cksichtigt nun die jeweiligen Vorz¨¹ge von beiden Vorgehensweisen und verbindet sie zu einem radikal neuen Ansatz. ?Unser Ansatz beruht auf sehr vielen kleinen, effizienten und g¨¹nstigen Rechenschritten, die insgesamt viel schneller sind als wenige grosse?, sagt Maximilian Probst Gutenberg, Dozent und Mitarbeiter in Kyngs Gruppe, der massgeblich zur Entwicklung der fast-linearzeitlichen Algorithmen beigetragen hat.

Der Blick in die Fachgeschichte offenbart zus?tzliche Dimensionen der Tragweite von Rasmus Kyngs Durchbruch:  Immerhin z?hlten Flussprobleme in Netzwerken zu den ersten, die in den 1950er-Jahren mit Hilfe von Algorithmen systematisch gel?st wurden, und Fluss-Algorithmen spielten eine wichtige Rolle, dass sich die theoretische Informatik als eigenes Forschungsgebiet etablierte. Aus dieser Zeit stammt der bekannte Algorithmus der Mathematiker Lester R. Ford Jr. und Delbert R. Fulkerson, der das Problem des maximalen Flusses effizient l?st, d.h. wie sich m?glichst viele G¨¹ter durch ein Netzwerk transportieren lassen, ohne die Kapazit?tsgrenzen der einzelnen Routen zu ¨¹berschreiten.

Nicht nur schnell, sondern auch umfassend

Seit damals ist bekannt, dass die wichtigen Netzwerkflussprobleme wie das Maximalfluss-Problem, das Minimalkosten-Problem (sog. Umlade- oder Transportproblem) und weitere im Prinzip Spezialf?lle des umfassenden Minimum-cost flow-Problems darstellen. Vor Rasmus Kyng schafften es die meisten Algorithmen nur, eines dieser Teilprobleme effizient zu l?sen. Sie waren jedoch weder besonders schnell noch liessen sie sich auf das umfassendere Min-Cost-Flow-Problem ausweiten. Das gilt auch f¨¹r die wegweisenden Flussalgorithmen der 1970er-Jahre, f¨¹r die die theoretischen Informatiker John Edward Hopcroft, Richard Manning Karp und Robert Endre Tarjan 1985 und 1986 den Turing-Award gewannen, der als Nobelpreis der Informatik gilt.

Perspektivenwechsel von der Schiene zum Strom

Erst 2004 gelang es den Mathematikern und Informatikern Daniel Spielman und Shang-Hua Teng sowie sp?ter Samuel Daitch solche Algorithmen zu schreiben, die auch das Minimum-Cost Flow Problem schnell und effizient l?sten. Sie waren es auch, die sich am elektrischen Fluss im Stromnetz orientierten. Ihr Perspektivenwechsel von der Schiene zum Strom f¨¹hrte mathematisch zu einem erheblichen Unterschied: Wird im Eisenbahnnetz ein Zug umgeleitet, weil eine Strecke ausf?llt, kann es vorkommen, dass die n?chstbeste Strecke laut Fahrplan bereits von einem anderen Zug belegt ist. Im Stromnetz hingegen ist es m?glich, dass die Elektronen, die den Stromfluss bilden, teilweise auf eine Netzverbindung umgeleitet werden, durch die bereits anderer Strom fliesst. Im Unterschied zu den Z¨¹gen l?sst sich der Strom somit mathematisch ?teilweise? auf eine neue Verbindung verlegen.

Diese partielle Umleitung erm?glichte es Spielman und seinen Kollegen, solche Strecken?nderungen viel schneller zu berechnen und zugleich bei jeder ?nderung auch das ganze Netzwerk zu rechnen. ?Wir verwarfen Spielmans Ansatz, m?glichst leistungsstarke Algorithmen f¨¹r das ganze Netzwerk zu entwerfen?, sagt Rasmus Kyng, ?vielmehr ¨¹bertrugen wir seine Idee der teilweisen Streckenberechnung auf die fr¨¹heren Ans?tze von Hopcroft und Karp.? Diese partielle Streckenberechnung pro Iteration trug viel dazu bei, die Gesamtflussberechnung zu beschleunigen.

Am Wendepunkt der theoretischen Grundlagen

Entscheidend f¨¹r den Fortschritt der ETH-Forschenden ist, dass er sich nicht auf die Entwicklung neuer Algorithmen beschr?nkt. Vielmehr nutzen und entwerfen sie auch neue mathematische Tools, die ihre Algorithmen zus?tzlich beschleunigen. Namentlich entwickelten sie eine neue Datenstruktur, die die Netzwerkdaten so organisiert, dass sich jede ?nderung einer Verbindung im Netzwerk extrem schnell finden l?sst und so zu der superschnellen algorithmischen L?sung beitr?gt. Da es f¨¹r die fast-linearzeitlichen Algorithmen und f¨¹r Tools wie die neue Datenstruktur viele Anwendungen gibt, d¨¹rfte sich die Innovationsspirale auch insgesamt schon bald viel schneller drehen als bisher.

Die deutlich schnelleren Fluss-Algorithmen legen jedenfalls nicht nur den Grund, um auch sehr grosse, bislang oft nicht effizient berechenbare Probleme zu l?sen, sondern sie ver?ndern auch die Art und Weise, wie Computer ¨¹berhaupt komplexe Aufgaben berechnen. ?In den letzten zehn Jahren gab es eine Revolution in den theoretischen Grundlagen f¨¹r erwiesenermassen schnelle Algorithmen f¨¹r grundlegende Probleme der theoretischen Informatik?, externe Seite schreibt dazu eine internationale Gruppe von Forschenden der Berkeley Universit?t, der auch Rasmus Kyng und Deeksha Adil, Forscherin am Institut f¨¹r Theoretische Studien der ETH Z¨¹rich, angeh?ren.