Algorytm push-relabel

Algorytm push-relabel

Algorytm push-relabel jest jednym z najskuteczniejszych algorytmów do obliczania maksymalnego przepływu. Jego ogólna złożoność czasowa wynosi

O(V2E),

podczas gdy modyfikacja Relabel-to-Front osiąga złożoność czasową

O(V3),

rozwiązanie z wyborem najbardziej aktywnego wierzchołka ma złożoność

O(V2√E),

a implementacja z dynamicznym drzewem Sleatora-Tarjana ma złożoność

O(VE log(V2/E)).

Asymptotycznie, algorytm ten jest znacznie bardziej efektywny niż algorytm Edmondsa-Karpa, którego złożoność czasowa wynosi

O(VE2).

Działanie

W sieci przepływowej, przepływ wpływający do wierzchołka powinien być równy przepływowi wychodzącemu z tego wierzchołka (z wyjątkiem źródła s oraz ujścia t). Z tego powodu, nie można akumulować przepływu w sieci.

Algorytmy przedprzepływowe ignorują to założenie i pozwalają na sytuację, w której do wierzchołka wpływa więcej przepływu, niż z niego wypływa. Taki stan nazywa się nadmiarowym przepływem lub przedprzepływem. Wierzchołek z nadmiarowym przepływem określa się jako wierzchołek aktywny. Nadmiarowy przepływ można jedynie przesunąć w dół po krawędziach residualnych w grafie residualnym. Przepływ jest przesyłany przez sieć (push) poprzez dostosowanie wysokości wierzchołków. Wysokość wierzchołków jest utrzymywana dzięki koncepcji valid labelling. W skrócie, koncepcja ta zakłada, że dla każdej krawędzi residualnej

height(u) ≤ height(v) + 1,

gdzie height(u) jest wysokością wierzchołka u, dla każdej krawędzi residualnej incydentnej do u. Innymi słowy, wierzchołek nie może być wyższy o więcej niż 1 od swojego sąsiada na krawędzi residualnej (przy czym nie ma ograniczenia, o ile niższy może być).

Przepływ zawsze przemieszcza się z wierzchołka o większej wysokości do wierzchołka o niższej wysokości.

Przesłanie przedprzepływu przez sieć polega na przemieszczeniu go w dół po krawędzi residualnej z wierzchołka u do wierzchołka v, gdzie

height(u) = height(v) + 1.

Operacja push jest nazywana wysycającą (saturating push), jeśli wykorzystano całą przepustowość krawędzi residualnej (wówczas krawędź (u,v) jest usuwana z grafu residualnego). Sytuacja, w której po przesłaniu przepływu pozostaje jeszcze dostępna pojemność krawędzi (u,v), nazywana jest niewysycającą (non-saturating push). Należy zauważyć, że non-saturating push wyczerpuje cały nadmiarowy przepływ z wierzchołka u, podczas gdy saturating push może, ale nie musi, wyczerpywać u.

Definicja

Algorytm push-relabel wyznacza maksymalny przepływ dla sieci przepływowej, która spełnia określone warunki:

Algorytm przedprzepływowy zachowuje dwa pierwsze warunki dla sieci przepływowej, jednocześnie ignorując trzeci na czas trwania algorytmu (algorytm kończy się, gdy cały nadmiar został usunięty z grafu – wówczas mamy już prawidłowy przepływ, a warunek zachowania przepływu jest spełniony).

Dla danej sieci G(V,E) o przepustowości c(u,v) z wierzchołka u do wierzchołka v, oraz przepływie między u i v danym jako f(u,v), źródle s i ujściu t, możemy ustalić maksymalny przepływ, jaki można przesłać od „s” do „t”. Algorytm wykorzystuje definicje:

Można zauważyć, że najdłuższa możliwa ścieżka z s do t ma długość |V| wierzchołków. Oznacza to, że można przypisać wysokość do wierzchołków dla każdego prawidłowego przepływu

height(s) = |V|

oraz

height(t) = 0,

a jeśli występuje przepływ dodatni z u do v, wtedy

height(u) > height(v).

W przeciwieństwie do algorytmu Ford-Fulkerson, przepływ przez sieć nie musi być przepływem prawidłowym przez cały czas trwania algorytmu.

Algorytm Push-Relabel

Wysokości aktywnych wierzchołków są podnoszone, aby umożliwić przesłanie przepływu do sąsiednich wierzchołków – proces ten trwa, aż cały przepływ dotrze do ujścia t. Następnie kontynuujemy podnoszenie wysokości wewnętrznych wierzchołków, aż cały przepływ, który wpłynął do sieci, ale nie opuścił jej przez t, wpłynie z powrotem do s. Wierzchołek może osiągnąć wysokość

2|V| – 1

zanim proces ten zostanie zakończony, ponieważ najdłuższa możliwa ścieżka do s, nie przechodząc przez t, ma długość |V| – 1, a

height(s) = |V|.

Wysokość t jest utrzymywana jako 0.

Kiedy cały możliwy przepływ zostanie przesunięty do t, nie istnieje ścieżka w grafie prowadząca z s do t (to stwierdzenie jest prawdziwe tak długo, jak wyczerpujemy minimalnego przekroju). Oznacza to, że kiedy nadmiarowy przepływ powraca do s, mamy do czynienia nie tylko z przepływem spełniającym zasadę zachowania, ale także z maksymalnym przepływem według twierdzenia o minimalnym przekroju i maksymalnym przepływie. Algorytm opiera się na dwóch funkcjach:

Push

Push z u do v oznacza przesłanie całej możliwej ilości nadmiarowego przepływu z u do v. Aby przeprowadzić procedurę push, spełnione muszą być trzy warunki:

Jeśli powyższe warunki są spełnione, można przeprowadzić push:

Function Push(u,v)
   flow = min(excess(u), c(u,v) - f(u,v));
   excess(u) -= flow;                   // odejmuje ilość przepływu, która zostanie przesłana dalej
   excess(v) += flow;                   // dodaje przepływ do wierzchołka, do którego przesyłamy
   f(u,v) += flow;                      // dodaje przepływ do krawędzi (u,v)
   f(v,u) -= flow;                      // odejmuje przepływ od krawędzi przeciwnej, aby zachować skośną symetrię

Relabel

Kiedy wykonujemy operację relabel na wierzchołku u, podnosimy jego wysokość do momentu, kiedy jest o 1 większa od najmniejszego sąsiada w grafie residualnym. Warunki dla relabel:

Mamy więc nadmiarowy przepływ do przesłania, jednak nie możemy być wyżej niż którykolwiek z sąsiadów mających dostępną pojemność wzdłuż ich krawędzi. Wtedy możemy wykonać relabel:

Function Relabel(u)
   height(u) = min(height(v) where r(u,v) > 0) + 1;

Algorytm Push-Relabel

Cały algorytm Push-Relabel przedstawia się następująco:

Algorithm Push-Relabel(G(V,E),s,t)
   while push or relabel are legal:   // dopóki możemy wykonywać operację push-relabel
      Perform a legal push, or
      perform a legal relabel;

Wykonywanie tych dwóch funkcji w dowolnej kolejności, tak długo jak pozostają aktywne wierzchołki, prowadzi do obliczenia maksymalnego przepływu. Złożoność obliczeniowa tego algorytmu, gdy nie uwzględniamy kolejności wykonywania operacji push i relabel, wynosi

O(V2E).

Czynnik zwiększający pesymistyczną złożoność algorytmu to liczba wykonywanych operacji non-saturating push.

Algorytm Relabel-to-Front

Algorytm Relabel-to-Front jest wariantem algorytmu Push-Relabel, który redukuje złożoność obliczeniową z

O(V2E)

do

O(V3).

Osiąga się to dzięki przeprowadzaniu procedur push i relabel w określonym porządku. Główna różnica polega na tym, że wykonujemy push i relabel dla pojedynczego wierzchołka, aż jego nadmiar zostanie całkowicie wykorzystany. Ogranicza to liczbę operacji non-saturating push, które zwiększają pesymistyczną złożoność obliczeniową algorytmu.

Aby to zrobić, tworzymy listę wszystkich wierzchołków w grafie

L = V – {s, t},

w dowolnej kolejności (zostaną uporządkowane podczas działania algorytmu). Dodatkowo dla każdego wierzchołka tworzymy listę sąsiedztwa, której kolejność jest dowolna, ale musi być stała. Elementami tej listy są potencjalni sąsiedzi, do których możemy przesłać przepływ. Następnie, kolejno zaczynając od pierwszego wierzchołka na liście, przeprowadzamy procedurę Discharge dla każdego wierzchołka u ∈ L, jeśli jest aktywny. Jeśli nie możemy wykonać operacji push, wykonujemy relabel i umieszczamy wierzchołek na początku listy.

Procedura Discharge

W relabel-to-front, procedura discharge na wierzchołku przebiega w następujący sposób:

Function Discharge(u):
    while excess(u) > 0:
       if (u.currentNeighbour != NIL):
          push(u, u.currentNeighbour);
          u.currentNeighbour = u.nextNeighbour;
       else:
          relabel(u);
          u.currentNeighbour = u.headOfNeighbourList;    // wraca z powrotem na początek listy sąsiadów

Relabel-to-Front

W algorytmie relabel-to-front w pełni rozładowujemy wierzchołek przed przejściem do kolejnego. Taka kolejność ogranicza liczbę wykonywanych procedur non-saturating push.

Algorithm Relabel-to-Front(G(V,E),s,t):
   for each vertex v incident to s:
      push(s,v);                       // wyczerpie to krawędzie (s,v) - przepływ jest ograniczony
   L = v - {s,t};                      // tworzy listę wierzchołków w dowolnej kolejności
   current = L.head;
   while (current != NIL):
      old_height = height(u);
      discharge(u);
      if height(u) > old_height:
         Move u to front of L
      current = current.next;

Złożoność obliczeniowa algorytmu relabel-to-front wynosi

O(V3),

(dowód pomijamy). Ponownie czynnikiem zwiększającym pesymistyczną złożoność algorytmu jest liczba procedur non-saturating push, jednak w tym przypadku ich ilość została zredukowana. Należy zauważyć, że po wykonaniu pierwszego kroku nie istnieje ścieżka z s do t w grafie residualnym.

Przykładowe implementacje

Implementacja w C:

Implementacja w Pythonie:

Bibliografia

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 26.4: Push-relabel algorithms, and section 26.5: The relabel-to-front-algorithm.

Andrew V. Goldberg, Robert E. Tarjan. A new approach to the maximum flow problem. Annual ACM Symposium on Theory of Computing, Proceedings of the eighteenth annual ACM symposium on Theory of computing, 136–146. ISBN 0-89791-193-8, 1986.

Przeczytaj u przyjaciół: