Graph Throughput Algorithmus

Question

Ich habe die Aufgabe, den maximalen Durchsatz in einem Diagramm zu berechnen.

Die einfachste Art, das Diagramm zu beschreiben, ist . Die innere Anordnung ist die Knoten in Graphen und die äußere Anordnung ist der Abstand jeder Knoten in dem Graphen verbinden, zum Beispiel:

new int[][] { 
    {0, 5, 0, 0}, // node 0 (the "source") 
    {0, 0, 4, 0}, // node 1 
    {0, 0, 0, 8}, // node 2 
    {0, 0, 0, 0} // node 3 (the "destination") 
} 

So von node 0 (Quelle) zu node 3 (das Ziel zu erhalten, die „maximale Durchsatz“ wäre 4 pro Umdrehung, weil:

• 5 Pakete vom Knoten 0 zum Knoten gehen kann 1
• 4 Pakete von Knoten 1 zu Knoten gehen kann 2
• 8 Pakete von Knoten 2 zu Knoten gehen kann 3

Auf einer „pro Umdrehung“ Basis ist der Engpass zwischen node 1 und node 2, wo die maximalen Durchsatzleistung 4.em

ist

Kann mich jemand einen Algorithmus zeigen, dass dieses „maximalen Durchsatz“ würde lösen Problem für jeder gegebene Graph, der auf diese Weise als int[][] definiert ist, und source und destination Knoten?

Das Beispieldiagramm soll um mehrere "Quellen" und "Ziele" erweitert werden, wo ich den maximalen Durchsatz des gesamten Systems für jede gegebene "Runde" berechnen muss.

Ich würde Hilfe in Form von Algorithmen zu studieren oder "Pseudocode" schätzen.

Answer 1

Maximum flow problem ist, was Sie suchen:

In Optimierungstheorie, beinhalten maximale Strömungsprobleme eine gangbare Strömung durch ein Single-Source-Single-Sinkstrom Netzwerk zu finden, die maximal ist.

Edmonds–Karp algorithm ein gewöhnlicher Algorithmus ist den maximalen Durchfluss für die Suche:

In der Informatik ist der Edmonds-Karp-Algorithmus eine Implementierung der Ford-Fulkerson Methode, um die maximale Strömung in einem Flussnetzwerk zur Berechnung in O (VE) Zeit.

Wie aus der Pseudocode ersichtlich, ist es kein komplexer Algorithmus, wenn es um die Implementierung geht. Hier ist ein C++ implementation auch.

Die in einem Strömungsnetzwerk geschnitten, daß die Quellen- und Senkenscheitelpunkte und minimieren trennt:

Minimum cut kann mit dem maximalen Strömungsproblem, um einen Engpass (sei es kann mehr als einen) zu finden, kombiniert werden, das Gesamtgewicht an den Kanten, die von der Quellenseite des Schnitts zur Senkseite des Schnitts gerichtet sind. Wie im Max-Flow-Min-Cut-Theorem gezeigt, entspricht das Gewicht dieses Schnitts der maximalen Menge an Fluss, die in dem gegebenen Netzwerk von der Quelle zur Senke gesendet werden kann.

Der minimale Schnitt verwendet den maximalen Fluss und sucht nach den ersten Kanten, die ausgelastet sind.

Lesen Sie mehr in Max Flow, Min Cut.