Zum Inhalt springen
Zurück zu den Suchergebnissen

Push-Relabel-Algorithmus

Eingeführt von
Andrew V. Goldberg and Robert E. Tarjan
Jahr
1988
Typ
algorithm
Familie
Graph Algorithms

Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen

Schriftgröße

Was leistet sie?

Der Push-Relabel-Algorithmus, entwickelt von Andrew V. Goldberg und Robert E. Tarjan im Jahr 1988, ist eine hocheffiziente Methode zur Berechnung des maximalen Flusses in Netzwerken.

Im Gegensatz zu Augmenting-Path-Methoden unterhält er einen Präfluss und nutzt lokale Push- und globale Relabeling-Operationen, um den Fluss zum Senken zu treiben, und erzielt dabei eine überlegene Worst-Case-Komplexität.

Die Intuition hinter der Methode

Der Algorithmus unterhält eine „Höhe“ oder „Distanzmarkierung“ für jeden Knoten und verwendet einen Präfluss (bei dem Knoten vorübergehend die Nachfrage des Senkenknotens überschreiten können). Er stößt überschüssigen Fluss wiederholt von Knoten mit höherer Markierung zu Nachbarn mit niedrigerer Markierung und markiert Knoten neu, um Pfade zum Senken zu schaffen. Die zentrale Erkenntnis ist, dass der Algorithmus durch die Aufrechterhaltung von Höheninvarianten und die Verwendung effizienter Datenstrukturen vermeidet, den gesamten Graphen wiederholt zu durchsuchen, wie es Augmenting-Path-Methoden tun müssen. Der Algorithmus terminiert, wenn der gesamte Präfluss den Senkenknoten erreicht hat.

Geschichte

Goldberg und Tarjan veröffentlichten 1988 ihren Push-Relabel-Algorithmus und führten ein grundlegend anderes Paradigma für die Berechnung des maximalen Flusses ein. Ihr Algorithmus erreichte eine Worst-Case-Komplexität von O(V³), eine Verbesserung gegenüber den O(VE²) von Edmonds-Karp. In den folgenden Jahrzehnten wurden zahlreiche Varianten entwickelt, darunter Gap-Heuristiken (Goldberg und Tarjan, 1990), Highest-Label-Regeln und die neuesten Varianten, die auf realen Netzwerken eine nahezu lineare empirische Leistung erzielen.

Wann wird sie eingesetzt?

Wende den Push-Relabel-Algorithmus zur Berechnung des maximalen Flusses in großen dichten Netzwerken an, in denen Augmenting-Path-Methoden ineffizient werden. Er ist besonders effektiv für Netzwerke mit Tausenden oder Millionen von Kanten. Verwende ihn, wenn du eine garantierte polynomiale Laufzeit benötigst und moderne Datenstrukturen nutzen möchtest. Für dünne Netzwerke oder zu Bildungszwecken können Augmenting-Path-Methoden einfacher zu verstehen und zu implementieren sein.

Grenzen und Hinweise

  • Komplexer zu verstehen und zu implementieren als Augmenting-Path-Methoden
  • Erfordert sorgfältige Handhabung von Datenstrukturen (Entladungslisten, Gap-Heuristiken) für optimale Leistung
  • Worst-Case-Komplexität immer noch höher als bei einigen spezialisierten Algorithmen für spezielle Graphklassen
  • Weniger intuitives Verständnis des Lösungsprozesses im Vergleich zu Augmenting Paths

Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.

Stärken

  • Überlegene Worst-Case-Zeitkomplexität: O(V³) oder O(V²√E) mit Gap-Heuristik
  • In der Praxis hochgradig effizient, insbesondere für große und dichte Netzwerke
  • Lokalität der Operationen (Push/Relabel) ermöglicht gute Cache-Performance
  • Geeignet für Parallelisierung und verteilte Implementierungen
  • Mehrere Implementierungsvarianten für unterschiedliche Problemstrukturen

Anwendungen

  • Netzwerk-Routing: Berechnung des maximalen Durchsatzes in großen Kommunikationsnetzwerken
  • Bildverarbeitung: Verwendung von Max-Flow für Bildsegmentierungs- und Matting-Anwendungen
  • Fluglinienoptimierung: Bestimmung des maximalen Passagierflusses durch komplexe Routing-Netzwerke
  • Stromnetzanalyse: Berechnung der maximalen Stromübertragungskapazität in elektrischen Netzwerken
  • Lieferkettenmanagement: Optimierung des Produktflusses durch mehrstufige Distributionsnetzwerke
  • Biologische Netzwerke: Analyse des maximalen Flusses in Stoffwechsel- und Proteininteraktionsnetzwerken

So funktioniert es

So funktioniert es

1

Setze die Höhe des Quellknotens auf die Anzahl der Knoten, alle anderen Höhen auf null. Sättige alle vom Quellknoten ausgehenden Kanten, wodurch ein anfänglicher Präfluss entsteht (Überschuss an benachbarten Knoten).

2

Wähle wiederholt einen aktiven Knoten (mit überschüssigem Fluss) aus und entweder stoße den Überschuss zu einem Nachbarn mit niedrigerer Höhe oder markiere den Knoten neu, um seine Höhe zu erhöhen. Verwende effiziente Auswahlstrategien und Entladungsvorgänge (discharge operations), um die Iterationen zu minimieren.

3

Fahre fort, bis keine aktiven Knoten mehr vorhanden sind. Zu diesem Zeitpunkt wurde der gesamte Präfluss in einen maximalen Fluss vom Quell- zum Senkenknoten aufgelöst.

Häufige Fallstricke

  • Falsche Implementierung von Höhenaktualisierungen oder Push-Operationen, die zu nicht-maximalen Flüssen führen
  • Vernachlässigung der Gap-Heuristiken und effizienter Knotenauswahl, was zu schlechter praktischer Leistung führt
  • Fehlende ordnungsgemäße Aufrechterhaltung der Präfluss-Invariante (Überschuss an Knoten und Kapazitätsbeschränkungen an Kanten)

Häufig gestellte Fragen

Was ist der Unterschied zwischen Präfluss und Fluss?

Präfluss erlaubt vorübergehend, dass Knoten überschüssigen Fluss halten (Fluss rein minus Fluss raus kann positiv sein), während ein echter Fluss an allen Knoten außer Quell- und Senkenknoten erhalten bleiben muss. Der Algorithmus terminiert, wenn der Präfluss zu einem gültigen Fluss wird.

Was ist der Zweck der Höhenfunktion?

Höhen schaffen ein Quasi-Distanzmaß: Fluss kann nur bergab (von höheren zu niedrigeren Höhen) gedrückt werden, was unnötige Zyklen verhindert und die Terminierung sicherstellt. Höhen werden durch Neumarkierung erhöht, um bei Bedarf neue Pfade zu schaffen.

Was ist die Gap-Heuristik und warum ist sie wichtig?

Die Gap-Heuristik erkennt, wenn kein Knoten eine Höhe in einem bestimmten Bereich hat, was darauf hindeutet, dass einige Knoten den Senkenknoten nicht erreichen können. Diese Knoten und ihr Überschuss werden schnell identifiziert und verarbeitet, was die praktische Leistung erheblich verbessert.

Wie schneidet Push-Relabel in der Praxis im Vergleich zu Edmonds-Karp ab?

Push-Relabel hat eine bessere Worst-Case-Komplexität und übertrifft Edmonds-Karp typischerweise bei großen Netzwerken, aber für kleine Netzwerke oder dünne Graphen kann Edmonds-Karp einfacher zu implementieren sein und eine wettbewerbsfähige Leistung erzielen.

Verwandte Methoden

Quellen

  1. Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum flow problem. Journal of the ACM, 35(4), 921-940.

    DOI-Referenz öffnen
    Kopiert.
  2. Goldberg, A. V. (1998). Recent advances in maximum flow and minimum-cost flow algorithms. In Algorithm Theory (pp. 1-10). Springer, Berlin.

    Publikationsreferenz öffnen
    Kopiert.