Was ist der Unterschied zwischen dem maximalen Fluss und dem maximalen Fluss?

Question

Was ist der Unterschied zwischen dem maximalen Fluss und dem maximalen Fluss.Ich lese diese Bedingungen während der Arbeit an FORD Fulkerson Algorithmen und sie sind ziemlich verwirrend.Ich habe im Internet versucht, konnte aber keine vernünftige Antwort bekommen.Ich glaube, dass der maximale Durchfluss ziemlich klar ist, da es maximale Flussmenge bedeutet, die von der Quelle übertragen werden kann, um in einem Netzwerk zu sinken, aber genau ist der maximale Fluss.

Bitte antworten Sie in Laienbedingungen, wenn möglich.

danke.

Answer 1

Kurze Antwort:

Denken Sie an die Oberseite der Berge, Jeder von ihnen ist eine maximale Lösung, Es gibt keinen Platz in der Nähe, der höher ist als sie, Aber nur die Spitze des Everest-Bergs hat die maximale Höhe und ist daher die maximale Lösung.

längere Antwort:

lass mich es in geometrischen Begriffen erklären: Denken Sie an ein Flugzeug (z. B. ein großer Frieden Papier). Jeder Punkt in der Ebene ist eine mögliche Lösung für das Problem. Die Höhe jedes Punktes ist die Qualität der Lösung, die diesem Punkt entspricht. In der Optimierung möchten wir die optimale Lösung finden, d. H. Der höchste Punkt in der Ebene. Eine Idee, um die optimale Lösung zu finden, ist, von einer möglichen Lösung in der Ebene zu beginnen und Verbessern Sie es wenig nachtern, Jedes Mal, wenn wir von einem Punkt auf eins in der Nähe gehen, der höher ist. Dies wird als lokaler Suchalgorithmus bezeichnet. Dieser Prozess stoppt, wenn wir einen Punkt erreichen, der höher ist als alle Punkte in der Nähe. Ein solcher Punkt wird ein lokales Optimum bezeichnet. Die entsprechende Lösung wird maximal bezeichnet, da wir die Qualität der Lösung nicht erhöhen können, indem wir auf jede Lösung in der Nähe bewegt werden. Eine maximale Lösung muss jedoch nicht die optimale Lösung sein, Es ist im Vergleich zu seinen Nachbarn optimal.

Es gibt gemeinsame Bedingungen, die falls erfüllt sind Wir haben keine lokalen Optimalungen in der Ebene, die nicht global optimal sind. In solchen Situationen können wir lokale Suchalgorithmen verwenden, um die optimale Lösung zu finden. Ein solcher Zustand ist, wenn die Lösungsebene konvex ist, Intuitiv für alle zwei Punkte haben wir alle Punkte auf der Zeilenverbindung auch im lösungsraum und Die Qualität von jedem von ihnen kann aus ermittelt werden der relative Abstand des Punktes zu den beiden Endpunkten und die Qualität der beiden Endpunkte. Die Optimierung über konvexen Räume wird in konvexoptimierung studiert.

Nun können Sie zum MAX Flow-Problem zurückkehren. Fixieren Sie ein Diagramm als Eingabe. Denken Sie an jeden Fluss, der die Kapazität und den Aufbewahren des Flusses erfüllt Anforderungen als Punkt. Wir nennen diese gültigen Flüsse. Wir möchten einen maximalen Fluss finden. Zwei Punkte sind in der Nähe voneinander, wenn wir eines durch Erhöhen oder Abnehmen erhalten können der Fluss durch einen Pfad von der Quelle zur Spüle.

Wir können mit dem Fluss beginnen, in dem der Fluss an allen Kanten Null ist (Dies ist ein gültiger Fluss). In jedem Schritt finden wir einen Pfad von der Quelle zum Waschbecken im aktualisierten verbleibenden Kapazitätsdiagramm (das Gewicht jeder Kante ist der Betrag seiner nicht verwendeten Kapazität) irgendwie (z. B. mit BFS) und den Fluss erhöhen, indem Sie dies hinzufügen. Dies gibt uns einen lokalen Suchalgorithmus. Das Problem ist, dass der Raum der Lösungen nicht konvex ist und Wir können mit einem Fluss enden dass wir nicht mehr erhöhen können, aber es ist kein maximaler Fluss.

Was können wir tun? Eine Idee ist, den Raum von Lösungen auf einen konvexen zu ändern. Für Intuition denken Sie über einen Stern in einem Flugzeug. Die Punkte im Inneren des Sterns machen keinen konvexen Raum Wir können es jedoch in einen konvexen Raum drehen, indem wir mehr Punkte in unseren Lösungsraum einschließen und in ein Pentagon drehen.

Dies ist im Wesentlichen das, was wir tun, indem wir den bestehenden Fluss an betrachten die ursprünglichen Kanten der Grafik als neue Kanten (genannt Restkanten ) wobei der Fluss über ihnen entspricht, den bestehenden Fluss an den ursprünglichen Kanten zu verringern. Dies macht den Raum konvex und unser lokaler Suchalgorithmus bleibt nicht auf Lösungen stecken die lokal optimal sind, aber nicht weltweit optimal.