Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


33. Fluß in einem Netzwerk



Suche in Netzwerken

Das oben beschriebene Verfahren von Ford-Fulkerson kann wie folgt zusammengefaßt werden: »Beginne überall mit einem Fluß 0 und erhöhe den Fluß längs eines beliebigen Pfades von der Quelle zur Senke, der keine vollen Vorwärts-Kanten oder leeren Rückwärts-Kanten besitzt, wobei dies so lange zu wiederholen ist, bis im Netzwerk keine derartigen Pfade mehr vorhanden sind.« Doch dies ist kein Algorithmus im üblichen Sinne, da die Methode für das Auffinden der Pfade nicht angegeben ist und überhaupt jeder beliebige Pfad benutzt werden könnte. Zum Beispiel könnte man das Verfahren auf der intuitiven Annahme aufbauen, daß das Netzwerk um so gefüllter wird, je länger der Pfad ist, und daß folglich lange Pfade bevorzugt werden sollten. Doch das in Abbildung 33.3 gezeigte (klassische) Beispiel beweist, daß eine gewisse Vorsicht angebracht ist.

Abbildung 33.3
Abbildung 33.3 Ein Netzwerk, bei dem eine große Zahl von Iterationen erforderlich sein kann.

In diesem Netzwerk wird, falls der erste gewählte Pfad ABCD ist, der Fluß lediglich um eins erhöht. Danach könnte der zweite gewählte Pfad ACBD sein, wodurch der Fluß erneut um eins erhöht würde und eine Situation entstünde, die mit der Ausgangssituation identisch ist, abgesehen davon, daß die Flüsse in den äußeren Kanten um eins erhöht sind. Jeder Algorithmus, der diese beiden Pfade gewählt hat (zum Beispiel ein Algorithmus, der lange Pfade auswählt), würde mit dieser Strategie fortfahren, so daß 1000 Paare von Iterationen erforderlich wären, bis der maximale Fluß gefunden würde. Wenn die Zahlen an den Seiten eine Milliarde lauten würden, so würden zwei Milliarden Iterationen benötigt. Offensichtlich ist das eine Situation, die nicht wünschenswert ist, da die Pfade ABC und ADC in nur zwei Schritten den maximalen Fluß liefern. Damit der Algorithmus brauchbar ist, müssen wir vermeiden, daß die Laufzeit so stark von den Kapazitäten abhängt. Glücklicherweise kann dieses Problem leicht beseitigt werden:

Eigenschaft 33.2 Wenn beim Verfahren von Ford-Fulkerson der kürzeste vorhandene Pfad von der Quelle zur Senke verwendet wird, muß die Anzahl der Pfade, die in einem Netzwerk mit V Knoten und E Kanten benutzt werden, bevor der maximale Fluß gefunden wird, kleiner als VE sein.

Diese Tatsache wurde 1972 von Edmonds und Karp bewiesen. Einzelheiten des Beweises würden über den Rahmen dieses Buches hinausgehen. w.z.b.w.

Mit anderen Worten, eine gute Strategie besteht einfach darin, eine in geeigneter Weise modifizierte Variante der Breitensuche für die Bestimmung des Pfades zu benutzen. Die in Eigenschaft 33.2 angegebene Schranke ist eine Schranke für den ungünstigsten Fall; typische Netzwerke erfordern gewöhnlich wesentlich weniger Schritte.

Mit der Methode der Traversierung von Graphen nach dem Prioritäts-Prinzip aus Kapitel 31 können wir ein anderes Verfahren implementieren, das von Edmonds und Karp vorgeschlagen wurde: Finde den Pfad durch das Netzwerk, der den Fluß um den höchsten Betrag vergrößert. Dies kann einfach dadurch erreicht werden, daß bei der Prioritätssuche mittels Adjazenzliste oder Adjazenzmatrix aus Kapitel 31 eine Variable für priority (mit geeignetem Wert) verwendet wird. Für die Matrix-Darstellung bewirken die folgenden Anweisungen die Berechnung der Priorität, und der Programmabschnitt für die Listendarstellung ist ähnlich:

    if size[k,t]>0 
      then priority:=size[k,t]-flow[k,t]
      else priority:=-flow[k,t];
    if priority>val[k] then priority:=val[k];

Danach müssen wir, da wir den Knoten mit der höchsten Priorität nehmen möchten, entweder die Mechanismen der Prioritätswarteschlange in diesen Programmen umkehren, damit das Maximum statt des Minimums zurückgegeben wird, oder sie in der Weise benutzen, daß priority auf maxint-1-priority gesetzt wird (und der Prozeß umgekehrt wird, wenn der Wert entfernt wird). Außerdem modifizieren wir die Prioritätssuche dahingehend, daß die Quelle und die Senke als Parameter verwendet werden und dann jede Suche bei der Quelle begonnen und abgebrochen wird, wenn ein zur Senke führender Pfad gefunden worden ist. Wenn ein solcher Pfad nicht gefunden wird, definiert der partielle Prioritätssuchbaum einen minimalen Schnitt für das Netzwerk; andernfalls kann der Fluß erhöht werden. Schließlich sollte der Wert val für die Quelle auf maxint gesetzt werden, bevor mit der Suche begonnen wird, um anzuzeigen, daß ein beliebig großer Betrag an der Quelle ausfließen kann (obwohl dieser sofort durch die Gesamtkapazität aller direkt aus der Quelle hinausführenden Leitungen begrenzt wird).

Wenn matrixpfs so implementiert wird, wie es im vorigen Absatz beschrieben wurde, ist die Bestimmung des maximalen Flusses tatsächlich recht einfach, wie das folgende Programm zeigt:

    repeat
      matrixpfs(1,V);
      y:=V; x:=dad[V];
      while x<>0 do
        begin
        flow[x,y]:=flow[x,y]+val[V];
        flow[y,x]:=-flow[x,y];
        y:=x; x:=dad[y]
        end
    until val[V]=1-maxint

Bei diesem Programm wird vorausgesetzt, daß für das Netzwerk eine Darstellung mittels Adjazenzmatrix verwendet wird. Solange matrixpfs einen Pfad finden kann, der den Fluß erhöht (um den maximalen Betrag), verfolgen wir den Pfad zurück (unter Benutzung des durch matrixpfs erzeugten Feldes dad) und erhöhen den Fluß in der angegebenen Weise. Falls V nach einem Aufruf von matrixpfs unsichtbar bleibt, so ist ein minimaler Schnitt gefunden worden, und der Algorithmus bricht ab.

Wie wir gesehen haben, erhöht der Algorithmus zuerst den Fluß längs des Pfades ABDF, dann längs ACEF, dann längs ACDBEF. Wir sehen schließlich auch, warum bei diesem Verfahren als dritter Pfad nicht ACDF gewählt wird: Dies würde den Fluß nur um eine Einheit erhöhen, nicht um drei Einheiten, wie dies bei dem längeren Pfad möglich ist. (Wir bemerken, daß die in Eigenschaft 33.2 angegebene Breitensuche des »kürzesten Pfades zuerst« diese Wahl treffen würde. Dann würde der maximale Fluß nach einer zusätzlichen Iteration gefunden.)

Obwohl sich dieser Algorithmus leicht implementieren läßt und für in der Praxis auftretende Netzwerke gewöhnlich ein gutes Verhalten zeigt, ist seine Analyse sehr kompliziert. Zunächst erfordert matrixpfs wie gewöhnlich V2 Schritte im ungünstigsten Fall; eine andere Möglichkeit wäre, listpfs zu benutzen, das in einer zu (E + V) log V proportionalen Zeit pro Iteration abläuft (obwohl der Algorithmus sicher etwas schneller abläuft, da er abbricht, wenn die Senke erreicht ist). Doch wie viele Iterationen werden benötigt?

Eigenschaft 33.3 Falls bei dem Verfahren von Ford-Fulkerson der Pfad von der Quelle zur Senke benutzt wird, der den Fluß um den größten Betrag erhöht, so ist die Anzahl der Pfade, die vor dem Auffinden des maximalen Flusses in einem Netzwerk benutzt werden, kleiner als 1 + logM/M-1 f*, wobei f* die Kosten des Flusses und M die maximale Anzahl der Kanten in einem Schnitt des Netzwerks bezeichnet.

Der Beweis dieser Tatsache wurde ebenfalls zuerst von Edmonds und Karp angegeben und würde weit über den Rahmen dieses Buches hinausgehen. Die Berechnung dieser Größe ist sicher kompliziert, doch für reale Netzwerke ist sie gewöhnlich nicht groß. w.z.b.w.

Wir erwähnen diese Eigenschaft nicht, um anzugeben, wieviel Zeit der Algorithmus für ein reales Netzwerk benötigen würde, sondern um die Komplexität der Analyse zu verdeutlichen. Im übrigen ist dieses Problem sehr gründlich untersucht worden, und es wurden komplizierte Algorithmen mit wesentlich besseren Schranken für den ungünstigsten Fall entwickelt. Bei Netzwerken, die in praktischen Anwendungen auftreten, dürfte der Algorithmus von Edmonds-Karp in der oben implementierten Form jedoch schwer zu übertreffen sein. Abbildung 33.4 zeigt die Arbeitsweise des Algorithmus bei Anwendung auf ein umfangreicheres Netzwerk.

Abbildung 33.4
Abbildung 33.4 Bestimmung des maximalen Flusses in einem größeren Netzwerk.

Das Problem des Flusses in einem Netzwerk kann in verschiedenen Richtungen verallgemeinert werden, und viele Varianten wurden recht eingehend untersucht, da sie für reale Anwendungen von Bedeutung sind. Zum Beispiel erfordert das Flußproblem für mehrere Medien (multicommodity flow problem) die Einführung von mehreren Quellen, Senken und Materien. Dadurch wird das Problem erheblich komplizierter, und es sind schwierigere Algorithmen als die hier betrachteten erforderlich; beispielsweise ist kein Analogon zu dem Satz über den maximalen Fluß und den minimalen Schnitt bekannt, das für den allgemeinen Fall gelten würde. Andere Verallgemeinerungen des Problems des Flusses in einem Netzwerk betreffen die Vorgabe von Beschränkungen der Kapazität für Knoten (was sich leicht modellieren läßt, indem künstliche Kanten zur Berücksichtigung dieser Kapazitäten eingeführt werden), die Zulassung von ungerichteten Kanten (was sich ebenfalls leicht modellieren läßt, indem ungerichtete Kanten durch Paare von gerichteten Kanten ersetzt werden) und die Einführung von unteren Schranken für die Werte des Flusses durch die Kanten (was sich nicht so einfach berücksichtigen läßt). Falls wir von der realistischen Annahme ausgehen, daß mit den Leitungen neben den Kapazitäten auch Kosten verknüpft sind, so liegt das Problem des Flusses mit minimalen Kosten vor, ein sehr kompliziertes Problem aus dem Bereich des Operations Research.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]