Znalezienie krótkich i grubych ścieżek

Motywacja: W standardowych algorytmach maksymalnego przepływu ścieżki augmentacyjnej wewnętrzna pętla wymaga znalezienia ścieżek od źródła do zatonięcia na ukierunkowanym, ważonym wykresie. Teoretycznie dobrze wiadomo, że aby algorytm nawet zakończył działanie, gdy istnieją nieracjonalne pojemności krawędzi, musimy nałożyć ograniczenia na ścieżki, które znajdziemy. Na przykład algorytm Edmondsa-Karpa mówi nam, aby znaleźć najkrótsze ścieżki.

Empirycznie zaobserwowano, że możemy również chcieć znaleźć ścieżki tłuszczu (czy istnieje na to lepszy termin?). Na przykład, stosując skalowanie pojemności , znajdujemy najkrótsze ścieżki, które mogą znieść co najmniej przepływu. Nie ma ograniczeń co do długości trasy. Kiedy nie możemy już znaleźć żadnych ścieżek, zmniejszamy ϵ i powtarzamy.$\epsilon$$\epsilon$

Interesuje mnie optymalizacja wyboru ścieżek zwiększania dla bardzo specyficznego zastosowania maksymalnego przepływu i chcę zbadać ten kompromis między ścieżkami krótkimi i grubymi. (Uwaga: nie zawsze muszę rozwiązywać problem. Najbardziej interesuje mnie znalezienie największej dolnej granicy przepływu w jak najkrótszym czasie).

Pytanie: Czy istnieje standardowy sposób interpolacji między podejściem najkrótszej ścieżki a podejściem skalowania zdolności? To znaczy, czy istnieje algorytm znajdowania ścieżek zarówno krótkich, jak i grubych, gdzie idealnie jakiś parametr kontrolowałby, ile długości na ścieżce jesteśmy skłonni zamienić na tłuszcz? W skrajności chciałbym móc odzyskać najkrótsze ścieżki na jednym końcu i ścieżki w stylu skalowania pojemności na drugim.

W duchu komentarza na temat „całkiem dobrze, ale niekoniecznie optymalnie”, przedstawiam następujący pomysł bez absolutnie żadnej gwarancji optymalności!

Dla kompletności, oto pseudokod, o którym mówiłeś (uwaga: połączony algorytm zakłada, że ​​pojemności brzegowe są liczbami całkowitymi od 1 do C, a wartości przepływu i resztkowej pojemności są integralne):

Scaling-Max-Flow (G, s, t, C) {
   foreach e ∈ E f (e) ← 0
   Δ ← najmniejsza moc 2 większa lub równa C
   G_f ← wykres resztkowy

   podczas gdy (Δ ≥ 1) {
      G_f (Δ) ← Δ-wykres resztkowy
      podczas gdy (istnieje ścieżka rozszerzająca P w G_f (Δ)) {
         f ← ​​augment (f, C, P)
         aktualizacja G_f (Δ)
      }
      ← ← Δ / 2
   }
   powrót f
}

$\epsilon$$\epsilon = \Delta$$\epsilon$

$0 \le \rho \le 1$$\rho$

$\epsilon$$\rho$

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

$\rho = 0$$\rho = 1$$0 < \rho < 1$$\epsilon$$\le 1$