Algorithmen in einer Kurzfassung, 2.

Kapitel 8. Netzwerkfluss-Algorithmen

Diese Arbeit wurde mithilfe von KI übersetzt. Wir freuen uns über dein Feedback und deine Kommentare: [e-mail]

Viele Probleme lassen sich als ein Netzwerk aus Knoten und Kanten darstellen, wobei jeder Kante, über die Waren fließen, eine Kapazität zugeordnet ist. Die Algorithmen in diesem Kapitel sind aus der Notwendigkeit entstanden, diese speziellen Problemklassen zu lösen. Ahuja (1993) enthält eine ausführliche Diskussion zahlreicher Anwendungen von Netzwerkflussalgorithmen:

Aufgabe

Bei einer Reihe von auszuführenden Aufgaben und einer Reihe von Mitarbeitern, die je nach zugewiesener Aufgabe unterschiedlich viel kosten können, weise die Mitarbeiter den Aufgaben zu und minimiere dabei die Gesamtkosten.

Zweiteiliges Matching

Finde für eine Menge von Bewerbern, die für eine Reihe von Aufträgen interviewt wurden, ein Matching, das die Anzahl der Bewerber maximiert, die für die Stellen ausgewählt werden, für die sie qualifiziert sind.

Maximaler Durchfluss

Berechne anhand eines Netzwerks, das die potenzielle Kapazität für den Transport von Waren zwischen zwei Orten zeigt, den maximalen Fluss, der durch das Netzwerk unterstützt wird .

Transport

Bestimme den kostengünstigsten Weg, um Waren von einer Reihe von Zulieferbetrieben zu einer Reihe von Einzelhandelsgeschäften zu transportieren.

Umschlag

Finde den kostengünstigsten Weg, um Waren von einer Reihe von Zulieferbetrieben zu einer Reihe von Einzelhandelsgeschäften ...