Wykres resztkowy w maksymalnym przepływie

14

Czytam tutaj o problemie z maksymalnym przepływem . Nie mogłem zrozumieć intuicji stojącej za wykresem rezydualnym. Dlaczego podczas obliczania przepływu bierzemy pod uwagę tylne krawędzie?

Czy ktoś może mi pomóc zrozumieć pojęcie wykresu resztkowego?

Jak zmienia się algorytm w niekierowanych grafach?

— csds
źródło

28

Intuicyjna interpretacja wykresu resztkowego w problemie maksymalnego przepływu jest bardzo dobrze przedstawiona w tym wykładzie. Wyjaśnienie jest następujące.

Załóżmy, że próbujemy rozwiązać problem maksymalnego przepływu dla następującej sieci (gdzie każda etykieta oznacza zarówno przepływ przepchnięty przez krawędź i pojemność tej krawędzi): $G$ $f_e/c_e$ $f_e$ $e$ $c_e$

Jednym z możliwych chciwych podejść jest:

Odebrać dowolne rozszerzanie ścieżki , która wychodzi z wierzchołka źródło zlewu wierzchołek tak, że ); to znaczy wszystkie krawędzie w mają dostępną pojemność. $P$ $s$ $t$ $\forall e \: (e \in P \rightarrow f_e \lt c_e$ $P$
Popchnij maksymalny możliwy przepływ przez tę ścieżkę. Wartość określa się przez wąskie gardło w ; to znaczy krawędź o minimalnej dostępnej pojemności. Formalnie . $\Delta$ $\Delta$ $P$ $\Delta=\min_{e \in P} (c_e-f_e)$
Przejdź do kroku 1, aż nie będzie żadnych ścieżek rozszerzających.

Oznacza to, że znajdź ścieżkę o dostępnej pojemności, wyślij przepływ wzdłuż tej ścieżki i powtórz.

W jedno możliwe wykonanie powyższej heurystyki znajduje trzy ścieżki rozszerzające , i , w tej kolejności. Te ścieżki wypychają odpowiednio 2, 2 i 1 jednostki przepływu, co daje całkowity przepływ 5: $G$ $P_1$ $P_2$ $P_3$

Wybór ścieżek w tej kolejności prowadzi do optymalnego rozwiązania; co się jednak stanie, jeśli najpierw wybierzemy (tj. przed i )? $P_3$ $P_1$ $P_2$

Otrzymujemy tak zwany przepływ blokujący : nie ma już żadnych ścieżek rozszerzających. W takim przypadku całkowity przepływ wynosi 3, co nie jest optymalne. Ten problem można rozwiązać, zezwalając na operacje cofania (tj. Zezwalając na wysyłanie przepływu w odwrotną stronę, cofanie pracy poprzednich iteracji): wystarczy przesunąć 2 jednostki przepływu wstecz od wierzchołka do wierzchołka następujący sposób: $w$ $v$

Kodowanie tych dozwolonych operacji cofania jest głównym celem wykresu resztkowego .

Wykres resztkowy sieci ma taki sam zestaw wierzchołków jak i zawiera dla każdej krawędzi : $R$ $G$ $G$ $e=(u,v) \in G$

Przednia krawędź o pojemności , jeśli . $e'=(u,v)$ $c_e-f_e$ $c_e-f_e \gt 0$
krawędź o pojemności , jeśli . $e''=(v,u)$ $f_e$ $f_e \gt 0$

Weźmy na przykład wykres resztkowy który jest uzyskiwany po pierwszej iteracji zachłannej heurystyki, gdy heurystyka najpierw wybiera (to znaczy, kiedy otrzymuje przepływ blokujący): $R$ $P_3$

Zauważ, że operacja cofania , która popycha 2 jednostki przepływu z do jest kodowana jako ścieżka do przodu (zwiększająca) od do w : $w$ $v$ $s$ $t$ $R$

Ogólnie:

Po wybraniu ścieżki rozszerzającej na wykresie resztkowym : $P'$ $R$

Każda krawędź w która odpowiada przedniej krawędzi w zwiększa przepływ, stosując krawędź o dostępnej pojemności. $P'$ $G$

Każda krawędź w która odpowiada krawędzi cofającej się w cofa przepływ, który w przeszłości był popychany do przodu. $P'$ $G$

Jest to główna idea metody Forda-Fulkersona .

Metoda Forda-Fulkersona postępuje dokładnie tak samo, jak chciwe podejście opisane powyżej, ale zatrzymuje się tylko wtedy, gdy nie ma już ścieżek rozszerzających na wykresie resztkowym (nie w oryginalnej sieci). Metoda jest poprawna (tzn. Zawsze oblicza maksymalny przepływ), ponieważ wykres resztkowy ustanawia następujący warunek optymalności :

Przy danej sieci przepływ jest maksymalny w jeśli nie ma ścieżki na wykresie resztkowym. $G$ $f$ $G$ $s-t$

— Mario Cervera
źródło

Czy istnieje przykład, w którym ścieżki są dodawane w kolejności najkrótszej długości, jak opisano w algorytmie Edmondsa-Karpa? W twoim kontrprzykładzie pierwsza ścieżka ma długość 3, podczas gdy krótsza (tj. 2) ścieżka może zostać znaleziona i zostanie dodana jako pierwsza, jeśli wykonujemy Edmonds-Karp.

— Roy

Możesz po prostu sprawić, aby wszystkie ścieżki na oryginalnym wykresie miały długość . Aby to zrobić, podziel wierzchołek na dwa wierzchołki i . Następnie podziel na i . Dodaj także dwie krawędzie i o pojemności . Krawędź, która pierwotnie przechodziła z na , teraz będzie się z na . Możemy uzyskać ten sam rodzaj przepływu blokującego, jeśli początkowo wybierzemy ścieżkę zawierającą krawędź .

s - t

$s-t$

3

$3$

v

$v$

v_{1}

$v_1$

v_{2}

$v_2$

w

$w$

w_{1}

$w_1$

w_{2}

$w_2$

(v_{1}, v_{2})

$(v_1,v_2)$

(w_{1}, w_{2})

$(w_1,w_2)$

2

$2$

v

$v$

w

$w$

v_{1}

$v_1$

w_{2}

$w_2$

(v_{1}, w_{2})

$(v_1,w_2)$

— Mario Cervera

Twój przykład ma sens. Zawsze możemy przedłużyć wykres na innych krawędziach cięcia, aby dana krawędź znajdowała się na jednej z najkrótszych ścieżek.

— Roy

3

Intuicyjna sieć rezydualna polega na tym, że pozwala nam „anulować” już przypisany przepływ, tj. Jeśli mamy już przypisane 2 jednostki przepływu z do , wówczas przekazanie 1 jednostki przepływu z do jest interpretowane jako anulowanie jednej jednostki pierwotnego przepływu od do . $A$ $B$ $B$ $A$ $A$ $B$

— Banach Tarski
źródło