Robert Sedgewick: Algorithmen

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


33. Fluß in einem Netzwerk



Gewichtete gerichtete Graphen sind nützliche Modelle für verschiedene Anwendungsarten, die Güter betreffen, welche durch ein Verbundnetz fließen. Betrachten wir zum Beispiel ein Netz von Ölleitungen unterschiedlicher Abmessungen, die auf komplexe Weise untereinander verbunden sind, mit Schiebern, die die Richtung des Flusses an den Verzweigungen steuern. Nehmen wir weiterhin an, daß das Netz eine einzige Quelle hat (zum Beispiel ein Ölfeld), und einen einzigen Bestimmungsort (zum Beispiel eine große Raffinerie), zu der letzten Endes alle Leitungen führen. Welche Schieberstellungen gewährleisten eine Maximierung des Ölflusses von der Quelle zum Bestimmungsort? Komplexe Wechselwirkungen, die den Materialfluß an den Verzweigungsstellen betreffen, bewirken, daß die Lösung dieses Problems nicht trivial ist.

Der gleiche allgemeine Ansatz kann verwendet werden, um den Verkehrsfluß auf Autostraßen, den Materialfluß durch Betriebe usw. zu beschreiben. Viele verschiedene Varianten des Problems wurden untersucht, die vielen unterschiedlichen praktischen Situationen entsprechen. Daher ist es natürlich sehr wünschenswert, einen effizienten Algorithmus für diese Probleme zu finden.

Diese Art von Problemen liegt im Grenzbereich zwischen der Informatik und dem Operations Research (Unternehmensforschung). Die Spezialisten auf diesem Gebiet beschäftigen sich allgemein mit der mathematischen Modellierung komplexer Systeme zum Zwecke der (nach Möglichkeit optimalen) Entscheidungsfindung. Der Fluß in einem Netzwerk ist ein typisches Problem des Operations Research; in den Kapiteln 42 - 45 werden wir noch einige andere kurz streifen.

In Kapitel 43 betrachten wir Fragen der linearen Optimierung, eines allgemeinen Ansatzes zur Lösung der komplexen mathematischen Gleichungen, die sich gewöhnlich aus Modellen des Operations Research ergeben. Für spezielle Probleme, wie das des Flusses in einem Netzwerk, sind bessere Algorithmen möglich. Tatsächlich werden wir feststellen, daß die klassische Lösung für das Problem des Flusses in einem Netzwerk in enger Beziehung zu den von uns betrachteten Algorithmen für Graphen steht, und daß es recht einfach ist, unter Benutzung der entwickelten algorithmischen Werkzeuge ein Programm zur Lösung des Problems zu erstellen. Dieses Problem gehört jedoch zu denen, die noch aktiv bearbeitet werden; im Gegensatz zu vielen der von uns betrachteten Probleme ist die »beste« Lösung noch nicht gefunden worden, und noch immer werden neue Algorithmen entdeckt.


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