Grundlegende Computerprobleme, das Maximum-Flow-Problem hat bahnbrechende Fortschritte gemacht: Der neue Algorithmus ist „lächerlich schnell“

Dieses Problem ist in der Netzwerkflusstheorie sehr grundlegend. „Der neue Algorithmus ist lächerlich schnell. Tatsächlich war ich überzeugt, dass es für dieses Problem keinen so effizienten Algorithmus gab“, sagte Daniel Spielman von der Yale University.

Maximalflüsse werden seit den 1950er Jahren untersucht, als sie zur Modellierung sowjetischer Eisenbahnsysteme untersucht wurden. „Die Erforschung dieser Materie ist noch älter als die Theorie der Informatik“, sagt Edith Cohen vom Google-Forschungszentrum Mountain View, Kalifornien.

Diese Frage führt zu vielen Anwendungen: Internet-Datenstreaming, Flugplanung, sogar Matching von Arbeitssuchenden mit offenen Stellen. Dieses neue Papier befasst sich sowohl mit dem Problem des maximalen Durchflusses als auch mit dem allgemeineren Problem der Bewältigung des maximalen Durchflusses und möchte gleichzeitig die Kosten minimieren. Diese beiden Fragen haben im Laufe der Jahre zu vielen bedeutenden Fortschritten in der algorithmischen Technologie geführt. „Das ist so ziemlich der Grund, warum wir weiter an Algorithmen arbeiten“, sagte Spielman. Der neue Algorithmus löst beide Probleme in „annähernd linearer“ Zeit, was bedeutet, dass die Laufzeit des Algorithmus im Wesentlichen der Zeit entspricht, die erforderlich ist. Kein anderer Algorithmus zur Lösung dieser Probleme kann diese Geschwindigkeit für alle möglichen Netzwerke erreichen. Satish Rao von der University of California in Berkeley sagte, dass ihn dieses Ergebnis überrascht habe: „Es ist einfach unglaublich.“

Spielman glaubt, dass wir einen so schnellen Algorithmus gefunden haben, und jetzt ist es an der Zeit, über Lösungen nachzudenken An verschiedene Anwendungsprobleme haben wir noch nicht gedacht.

Derzeit handelt es sich bei der neuen Methode hauptsächlich um eine theoretische Verbesserung, da die Verbesserung der Algorithmusgeschwindigkeit nur auf viel größere Netzwerke anwendbar ist als in der realen Welt, für die das Problem des maximalen Datenverkehrs bereits sehr schnell gelöst werden kann Antwort (zumindest ohne Berücksichtigung der Kostenminimierung). Richard Peng von der University of Waterloo in Kanada, einer von sechs Entwicklern des neuen Algorithmus, geht davon aus, dass er innerhalb eines Jahres in der Praxis eingesetzt werden könnte.

Einige Forscher glauben, dass Informatiker in den nächsten Jahren Wege finden könnten, es praktischer und vielleicht sogar schneller zu machen.

Aleksander Mądry vom MIT sagte, dass dieser neue Artikel „der aufregendste Dunk im Slam-Dunk-Wettbewerb“ sei, selbst wenn es in der Zukunft Verbesserungen gebe. Er sagte, es sei im Grunde das Beste.

Ein Weg nach dem anderen

Richard Peng sagte, dass viele Informatiker sich mit dem Maximum-Flow-Problem befassen, und zwar so sehr, dass die Diskussion früherer Arbeiten auf einer Konferenz so ist, als würde man den Abspann eines Films durchgehen. Die meisten sind sich jedoch einig, dass der erste formale Algorithmus die Anwendung eines Greedy-Algorithmus für maximalen Fluss von Lester Ford und Delbert Fulkerson aus dem Jahr 1956 war, der bei jedem Schritt das am leichtesten verfügbare Objekt verwendet.

Sie können sich diesen Ansatz folgendermaßen vorstellen: Stellen Sie sich zunächst ein Autobahnnetz vor und Sie möchten in einer bestimmten Zeit so viele Lieferwagen wie möglich von Los Angeles nach New York City bewegen. Der Algorithmus von Ford und Fulkerson wählt zunächst einen Weg von Los Angeles nach New York und leitet so viele Lastwagen wie möglich auf diesem Weg. Diese Methode nutzt normalerweise nicht die volle Kapazität aller Straßen auf dieser bestimmten Straße: Wenn es sich bei der Straße um eine fünfspurige Autobahn handelt, die aber über eine zweispurige Brücke führt, können sich jeweils nur zwei LKWs bewegen.

Als nächstes ändert der Algorithmus die Kapazität dieser Segmente, um widerzuspiegeln, dass ein Teil der Kapazität des Segments jetzt genutzt wird: Er subtrahiert die Anzahl der gesendeten LKWs von der Kapazität des Segments, sodass die fünfspurige Autobahn jetzt eine Kapazität von 3 hat , während die Kapazität der zweispurigen Brücke Null ist. Gleichzeitig erhöht der Algorithmus die Kapazität dieser Straßen in umgekehrter Richtung um 2, sodass wir bei Bedarf später einen Teil des Verkehrs zurückziehen können.

Der Algorithmus findet dann einen neuen Weg von Los Angeles nach New York, der einige LKWs aufnehmen kann, schickt so viele LKWs wie möglich entlang des Weges und aktualisiert die Kapazität erneut. Nach einer begrenzten Anzahl dieser Schritte kann die Straße von Los Angeles nach New York keine weiteren Lkw mehr aufnehmen, und an diesem Punkt ist der Algorithmus vollständig: Wir kombinieren einfach alle konstruierten Flüsse, um den maximal möglichen Verkehr zu erhalten das Netzwerk.

Der Algorithmus von Ford und Fulkerson versucht nicht, unterwegs kluge Entscheidungen zu treffen. Wenn ein Pfad ausgewählt wird, der andere nützliche Pfade abschneidet, stellt dies ein Problem dar, mit dem sich der Algorithmus später befassen muss. In den Jahrzehnten seit der Veröffentlichung des Algorithmus haben Forscher versucht, die Laufzeiten zu verkürzen, indem sie den Algorithmus intelligentere Entscheidungen treffen ließen, beispielsweise immer den kürzesten verfügbaren Pfad oder den Pfad mit der größten verfügbaren Kapazität verwenden. 1970 entdeckte Yefim Dinitz eine effiziente Möglichkeit, alle kürzesten Wege in einem Netzwerk in einem Schritt zu nutzen. Shimon Even und Robert Tarjan haben nachgewiesen, dass die Laufzeit dieses Algorithmus in Netzwerken mit geringer Kapazität m^1,5 beträgt (m: die Anzahl der Verbindungen im Netzwerk. Im Gegensatz dazu erfordert der Ford-Fulkerson-Algorithmus in Netzwerken mit geringer Kapazität mehrere m Netzwerke. ^2).

Fast 30 Jahre später kamen Rao und Andrew Goldberg zu ähnlichen Ergebnissen für Hochleistungsnetze. Aber niemand kann den Index m^1,5 schlagen. „Auf dem Weg ins 21. Jahrhundert ... sind die Hindernisse für m^1,5 tief verwurzelt“, sagte Sushant Sachdeva von der University of Toronto, einer der Autoren des neuen Papiers, um weitere Fortschritte zu erzielen Verschiedene Methoden.

Von der Kombination zum Kalkül

Bisher haben alle diese Algorithmen einen kombinatorischen Ansatz verfolgt, d. h. sie suchen bei jedem Schritt nach einer Art Struktur und verwenden diese Struktur, um den Stream zu aktualisieren. Doch im Jahr 2003 öffneten Spielman und ShangHua Teng von der University of Southern California die Tür zu einem völlig anderen Ansatz der „Optimierung“, bei dem Kalkültechniken als Leitfaden für die Suche nach optimalen Lösungen verwendet werden.

Spielman und Teng haben einen schnellen Optimierungsalgorithmus entwickelt, der nicht das Problem des maximalen Durchflusses löst, sondern das eng damit verbundene Problem, den niedrigsten Energiestrom durch jedes Drahtnetzwerk mit einem gegebenen Widerstand zu finden. Sachdeva sagte, die Fortschritte von Spielman und Teng seien „kritische Momente“.

Teammitglieder, die den ultraschnellen Algorithmus zur Bestimmung des maximalen Datenverkehrs und der minimalen Kosten eines Netzwerks erstellt haben (im Uhrzeigersinn von der oberen linken Ecke): Yang Liu, Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg, Richard Peng, Sushant Sachdeva.

Forscher begannen bald zu erforschen, wie sich dieser Fortschritt auf das Problem des maximalen Durchflusses anwenden ließe. Stellen Sie sich das Straßennetz als ein Netzwerk aus Drähten vor, die den Widerstand auf Straßen erhöhen, auf denen nicht viel Kapazität zur Verfügung steht, und so verhindern, dass Elektronen darüber wandern. Dank der Arbeit von Spielman und Teng können wir den Strom durch diese Leitungen schnell berechnen, und dieses Modell verfügt über grobe Eigenschaften für den maximalen Fahrzeugfluss durch die Autobahn. (Sie werden nicht genau gleich sein, da das aktuelle Problem der Kapazität des Kabels keine feste Grenze setzt.)

Dann, nachdem wir diesen anfänglichen Fluss erzeugt haben, können wir die Kapazität wie bei Ford und Fulkerson neu skalieren kombinierter Algorithmus. Als nächstes kann der Widerstand jedes Drahtes zurückgesetzt werden, um diese sich ändernden Werte widerzuspiegeln und die neu entstandenen Schaltungsprobleme zu lösen.

Im Gegensatz zur kombinatorischen Methode, bei der jeweils ein Netzwerkblock geändert wird, führt die Optimierungsmethode von Spielman und Teng jedes Mal den Scan des gesamten Netzwerks durch. Dadurch wird jeder Schritt effizienter, sodass insgesamt weniger Schritte erforderlich sind, um das Maximum zu erreichen. Im Jahr 2008 nutzten Samuel Daitch und Spielman von Google diese Methode, die im Wesentlichen der bisherigen Grenze des maximalen Datenverkehrs von m^1,5 entsprach. Im Jahr 2013 hat Mądry den Ansatz weiter weiterentwickelt, um m^1,5 für Netzwerke mit geringer Kapazität zu überschreiten und die Laufzeiten auf etwa ein Vielfaches von m^1,43 zu verbessern. „Es ist schockierend“, sagte Rao.

In den nächsten Jahren haben Forscher diese Methode weiter ausgebaut, ihre Ergebnisse blieben jedoch bei m^1,33 stecken. Sie begannen sich zu fragen, ob dieser Index eine grundlegende Grenze darstellte.

Für den Max-Flow-Algorithmus sollte die schnellste vorstellbare Laufzeit m-mal sein (d. h. m^1,0), da das Aufschreiben eines Netzwerks ein Vielfaches von m Schritten erfordert. Dies nennt man lineare Zeit. Doch für viele Forscher schien ein solch extrem schneller Algorithmus undenkbar. „Es gibt keinen guten Grund zu der Annahme, dass wir das schaffen können“, sagte Spielman.

Minimieren, wiederverwenden, recyceln

Die Autoren dieses neuen Papiers glauben, dass der Ansatz von Daitch und Spielman weitere Vorteile hat. Mądry hatte es verwendet, um die Anzahl der Schritte zu reduzieren, die zur Lösung des Maximum-Flow-Problems erforderlich waren. Diese Reduzierung hatte jedoch ihren Preis: Bei jedem Schritt musste das gesamte Netzwerk neu geschrieben und das Leistungsflussproblem von Grund auf gelöst werden.

Dieser Ansatz behandelt den Algorithmus von Spielman und Teng als Blackbox – unabhängig davon, was im Algorithmus vor sich geht. Sechs Forscher beschlossen, sich mit dem Kern des Algorithmus zu befassen und seine Komponenten an das Problem des maximalen Durchflusses anzupassen. Sie vermuten, dass diese Komponenten es ihnen sogar ermöglichen könnten, das schwierigere „Minimalkostenproblem“ zu lösen, bei dem es darum geht, den günstigsten Weg zum Transport einer bestimmten Materialmenge zu finden. Informatiker wissen seit langem, dass jeder Minimalkostenalgorithmus das lösen kann Problem des maximalen Flusses.

Wie andere Optimierungsmethoden schlugen die Forscher das Konzept der Flussenergie als Funktion der Verbindungskosten und -kapazität vor. Die Verlagerung des Datenverkehrs von teuren Verbindungen mit geringer Kapazität auf billige Verbindungen mit hoher Kapazität verringert die Gesamtenergie des Systems.

Um herauszufinden, wie sich die Strömung schnell in einen energieärmeren Zustand bewegen lässt, kombinierten die Forscher diesen Optimierungsansatz mit einer alten Kombinationsansicht. Letzteres ändert jeweils nur einen Teil des Netzwerks und bietet die Möglichkeit, einen Teil der Arbeit aus vorherigen Schritten wiederzuverwenden.

Bei jedem Schritt sucht der Algorithmus nach einem Zyklus, der Energie reduzieren kann, also einem Weg, der am gleichen Punkt beginnt und endet. Die Grundidee ist einfach: Angenommen, Sie bauen eine mautpflichtige Straße von Chicago nach New York und stellen dann fest, dass es eine günstigere Autobahn gibt. Wenn man an diesem Punkt New York zum Ring hinzufügt, indem man auf der teuren Straße nach Chicago und dann auf der günstigeren Route zurückfährt, entsteht ein Ring, der den teuren Weg ersetzt und so die Gesamtkosten des Verkehrs senkt. Valerie King von der University of Victoria in Kanada sagt, dass diese Methode viel mehr Schritte erfordert als die „elektrische Methode“, daher klingt es auf den ersten Blick „wie ein Rückschritt“. Um dies zu kompensieren, muss der Algorithmus bei jedem Schritt unglaublich schnell gute Schleifen finden, schneller als es nötig wäre, das gesamte Netzwerk zu untersuchen.

So funktioniert der Algorithmus von Spielman und Teng. Ihr Algorithmus bietet eine neue Möglichkeit, „Low-Stretch Spanning Trees“ zu verwenden, die für den Algorithmus von entscheidender Bedeutung sind und viele der wichtigsten Merkmale eines Netzwerks erfassen können. Bei einem solchen Baum ist es immer möglich, mindestens einen guten Zyklus zu konstruieren, indem man einen Link außerhalb des Baums hinzufügt. Daher kann ein Spannbaum mit geringer Skalierung die Anzahl der zu berücksichtigenden Zyklen erheblich reduzieren.

Dennoch konnte das Team nicht bei jedem Schritt einen neuen Spanning Tree erstellen, um den Algorithmus schnell laufen zu lassen. Stattdessen müssen sie sicherstellen, dass jeder neue Zyklus nur einen kleinen Welleneffekt im Spanning Tree erzeugt, sodass die meisten vorherigen Berechnungen wiederverwendet werden. Dieses Maß an Kontrolle zu erreichen sei „die Kernschwierigkeit“, sagte Yang Liu, ein Doktorand an der Stanford University und einer der Autoren des Papiers.

Letztendlich haben die Forscher einen Algorithmus erstellt, der in „fast linearer“ Zeit läuft, was bedeutet, dass seine Laufzeit bei Verwendung größerer Netzwerke umso näher an m liegt.

Der Algorithmus leiht sich viele Ideen von Spielman und Teng und kombiniert sie zu etwas völlig Neuem. Wenn Sie bisher nur einen Pferdewagen gesehen haben, sind die heutigen Algorithmen wie Autos, sagte Spielman. „Ich sehe, es hat einen Platz zum Sitzen, ich sehe, es hat Räder, ich sehe, es hat etwas, um es zu bewegen. Aber sie haben die Pferde durch Motoren ersetzt.“ 🎜🎜#Rao spekulierte, dass die Analyse des Teams langwierig und komplex sei, andere Forscher sich jedoch bald damit befassen würden, das Problem zu vereinfachen. „Ich habe das Gefühl, dass in den nächsten Jahren alles sauberer und besser werden wird“, sagte er, sobald der Algorithmus vereinfacht sei, sagte Spielman, man könne ihn als Unterprogramm eines Algorithmus verwenden, der verschiedene Probleme löst. „Jetzt, da wir wissen, dass wir dies sehr schnell tun können, werden die Leute alle Arten von Anwendungen entdecken, an die sie noch nie gedacht haben.“ Das Maximum-Flow-Problem gab Spielman Hoffnung auf andere Kernfragen der Algorithmustheorie: „Was können wir sonst noch tun?“

Das obige ist der detaillierte Inhalt vonGrundlegende Computerprobleme, das Maximum-Flow-Problem hat bahnbrechende Fortschritte gemacht: Der neue Algorithmus ist „lächerlich schnell“. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!