Suche nach kurzen und fetten Wegen

Motivation: Bei Standard-Augmenting-Path-Maxflow-Algorithmen erfordert die innere Schleife das Finden von Pfaden von der Quelle zur Senke in einem gerichteten, gewichteten Diagramm. Theoretisch ist bekannt, dass wir die gefundenen Pfade einschränken müssen, damit der Algorithmus auch bei irrationalen Kantenkapazitäten endet. Der Edmonds-Karp-Algorithmus sagt uns beispielsweise, dass wir kürzeste Wege finden sollen.

Empirisch wurde beobachtet, dass wir möglicherweise auch Fettpfade finden möchten (gibt es dafür einen besseren Begriff?). Zum Beispiel bei der Verwendung von Kapazitätsskalierung finden wir kürzeste Wege , die zumindest tragen können Flussmenge. Es gibt keine Einschränkung, wie lang der Pfad sein kann. Wenn wir keine Pfade mehr finden können, verringern wir und wiederholen.$\epsilon$$\epsilon$

Ich bin daran interessiert, die Auswahl der Erweiterungspfade für eine sehr spezifische Anwendung von Max-Flow zu optimieren, und ich möchte diesen Kompromiss zwischen kurzen und fetten Pfaden untersuchen. (Hinweis: Es ist nicht erforderlich, dass ich das Problem immer löse. Ich bin am meisten daran interessiert, die größte untere Grenze des Durchflusses in kürzester Wandzeit zu finden.)

Frage: Gibt es eine Standardmethode für die Interpolation zwischen dem Ansatz des kürzesten Pfades und dem Ansatz der Kapazitätsskalierung? Das heißt, gibt es einen Algorithmus zum Finden von Pfaden, die sowohl kurz als auch fett sind, wobei im Idealfall ein Parameter steuern würde, wie viel Länge des Pfades wir bereit sind, gegen Fett auszutauschen? Im Extremfall möchte ich in der Lage sein, kürzeste Pfade an einem Ende und Pfade im Kapazitätsskalierungsstil am anderen Ende wiederherzustellen.

Im Geiste Ihres Kommentars zu "ziemlich gut, aber nicht unbedingt optimal" präsentiere ich die folgende Idee ohne jegliche Garantie für die Optimalität!

Der Vollständigkeit halber hier der Pseudocode, auf den Sie sich bezogen haben (Anmerkung: Der verknüpfte Algorithmus geht davon aus, dass die Kantenkapazitäten ganze Zahlen zwischen 1 und C sind und dass die Werte für Durchfluss und Restkapazität ganzzahlig sind):

Scaling-Max-Flow (G, s, t, C) {
   foreach e ∈ E f (e) ← 0
   Δ ← kleinste Potenz von 2 größer oder gleich C.
   G_f ← Restgraph

   während (Δ ≥ 1) {
      G_f (Δ) ← Δ-Restgraph
      while (es gibt einen Erweiterungspfad P in G_f (Δ)) {
         f ← ​​Augmentation (f, C, P)
         Aktualisiere G_f (Δ)
      }}
      Δ ← Δ / 2
   }}
   return f
}}

Beachten Sie, dass Sie bei = 1 ( im Pseudocode) nur Pfade in kürzester bis längster Reihenfolge finden, und wenn groß ist, finden Sie Pfade in (mehr oder weniger) fettester Reihenfolge schlankste Ordnung. Tatsächlich findet der Kapazitätsskalierungsalgorithmus abhängig von der Instanz Pfade in kürzester bis längster Reihenfolge innerhalb von "Buckets" von "genügend Fluss".ϵ = Δ $\epsilon$$\epsilon = \Delta$$\epsilon$

Fügen Sie dann einen weiteren Eingabeparameter , der angibt, wie sehr Sie sich für "Fett" und "Kürze" interessieren. Um sicherzustellen, dass wir die Laufzeit nicht massiv beeinflussen, benötigen wir außerdem, dass eine rationale Zahl ist.$0 \le \rho \le 1$$\rho$

Jedes Mal, wenn ein Wert zugewiesen wird, nehmen wir zusätzlich das gewichtete arithmetische Mittel (ich hoffe, das ist der richtige Begriff ..) zwischen 1 und seinem aktuellen Wert. Das ist,$\epsilon$$\rho$

$\epsilon \leftarrow (\rho)\epsilon + (1-\rho)$

Für wir einen reinen Algorithmus für den kürzesten Pfad. für wir einen rein fettesten Pfadalgorithmus; und für bekommen wir etwas dazwischen. Insbesondere für einen mittleren Wert konvergiert schneller zu , sodass Sie kürzere und weniger fetteste Pfade erhalten.ρ = 1 0 < ρ < 1 ϵ ≤ $\rho = 0$$\rho = 1$$0 < \rho < 1$$\epsilon$$\le 1$