Algorytm push-relabel
Rodzaj | |
---|---|
Struktura danych | |
Złożoność | |
Czasowa |
|
Algorytm push-relabel – jeden z najbardziej efektywnych algorytmów obliczania maksymalnego przepływu. Ogólny algorytm działa ze złożonością podczas gdy modyfikacja Relabel-to-Front ma złożoność czasową rozwiązanie z wyborem najbardziej aktywnego wierzchołka a implementacja z dynamicznym drzewem Sleatora-Tarajana Asymptotycznie, algorytm ten jest znacznie bardziej efektywny niż algorytm Edmondsa-Karpa, którego złożoność czasowa wynosi
Działanie
W sieci przepływowej, przepływ wpływający do wierzchołka musi być równy przepływowi opuszczającemu wierzchołek (z wyjątkiem źródła i ujścia ). W związku z tym ograniczeniem nie można akumulować przepływu w sieci.
Algorytmy przedprzepływowe pomijają to założenie i pozwalają na sytuację, gdy do wierzchołka wpływa więcej przepływu niż z niego wypływa. Sytuacja ta nazywana jest nadmiarowym przepływem, bądź przedprzepływem. Wierzchołek z nadmiarowym przepływem nazywany jest wierzchołkiem aktywnym. Nadmiarowy przepływ można jedynie przemieścić w dół krawędzi residualych grafu residualnego. Przepływ zostaje przesłany przez sieć (push) poprzez dostosowanie wysokości wierzchołków. Wysokość wierzchołków jest dostosowywana i utrzymywana za pomocą koncepcji valid labelling. Ściśle mówiąc, koncepcja ta zakłada, że dla każdej krawędzi residualnej gdzie jest wysokością wierzchołka dla każdej krawędzi residualnej incydentnej do 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 istnieje ograniczenie o ile niższy może być).
Przepływ przepływa zawsze z wierzchołka o większej wysokości do wierzchołka o mniejszej wysokości.
Przesłanie przedprzepływu przez sieć oznacza przemieszczenie go w dół po krawędzi residualnej z wierzchołka do wierzchołka gdzie Operacja push nazywana jest wysycającą (saturating push) jeśli użyta została cała przepustowość krawędzi residualnej (a więc krawędź została usunięta z grafu residualnego). Sytuację w której po przesłaniu przepływu dostępna jest jeszcze pojemność krawędzi nazywa się niewysycającą (non-saturating push). Należy zauważyć, że non-saturating push wyczerpuje cały nadmiarowy przepływ z wierzchołka z kolei saturating push może wyczerpywać ale nie musi.
Definicja
Algorytm push-relabel znajduje maksymalny przepływ dla sieci przepływowej, spełniającej następujące warunki:
Ograniczenie objętości: Przepływ wzdłuż krawędzi nie może przekraczać jej przepustowości. Symetria skośna: Suma przepływów w odwrotnych kierunkach musi być zerowa. Zachowanie przepływu: chyba że lub Przepływ sieciowy do wierzchołka jest zerowy, z wyjątkiem źródła, które „produkuje” przepływ, i ujścia, które „konsumuje” przepływ.
Algorytm przedprzepływowy zachowuje dwa pierwsze warunki dla sieci przepływowej, jednocześnie zaniedbując trzeci na czas trwania algorytmu (algorytm kończy się kiedy cały nadmiar jest usunięty z grafu – w tym momencie występuje już prawidłowy przepływ, a warunek zachowania przepływu jest spełniony).
Ograniczenie na nieujemność nadmiaru: dla wszystkich wierzchołków Więcej przepływu wpływa do wierzchołka niż go opuszcza.
Dla danej sieci o przepustowości z wierzchołka do wierzchołka i przepływie pomiędzy i danym jako źródle i ujściu możemy wyznaczyć maksymalny przepływ jaki można przesłać od „s” do „t”. Algorytm wykorzystuje definicje:
krawędź residualna: Jeśli dostępna jest przepustowość mamy krawędź residualną krawędź residualna (odwrotna): Możemy przesyłać przepływ w obu kierunkach. graf residualny: Zestaw krawędzi residualnych formuje graf residualny. poprawne etykietowanie ("legal labelling"): Dla krawędzi residualnych operację push możemy wykonywać jedynie na wierzchołkach. nadmiar(u): Suma przepływu wpływającego do i opuszczającego wysokość(u): Każdemu wierzchołkowi przypisana jest konkretna wysokość. Dla wartości wysokość służy do oszacowania odległości do ujścia Dla wartości wysokość służy do oszacowania odległości z powrotem do źródła
Można zaobserwować, że najdłuższa możliwa ścieżka z do ma długość wierzchołków. Stąd musi być możliwe, aby przypisać wysokość do wierzchołków dla każdego prawidłowego przepływu i a jeśli występuje przepływ dodatni z do W odróżnieniu od algorytmu Forda-Fulkersona, 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 na tyle, by zaszło przesłanie przepływu do sąsiednich wierzchołków – dzieje się tak aż do momentu kiedy cały przepływ dotrze do ujścia Wówczas kontynuujemy podnoszenie wysokości wewnętrznych wierzchołków aż do momentu, kiedy cały przepływ, jaki wpłynął do sieci, ale nie opuścił jej przez wpłynie z powrotem do Wierzchołek może osiągnąć wysokość zanim proces ten zostanie ukończony, ponieważ najdłuższa możliwa ścieżka do nie przechodząca przez jest długości i Wysokość jest utrzymywana jako 0.
Kiedy już cały możliwy przepływ zostanie przemieszczony do nie istnieje ścieżka w grafie prowadząca z do (w rzeczywistości stwierdzenie to jest prawdziwe tak długo jak wyczerpujemy minimalnego przekroju). Oznacza to, że kiedy nadmiarowy przepływ powróci do mamy do czynienia nie tylko z przepływem spełniającym zasadę zachowania przepływu, ale jednocześnie z przepływem maksymalnym według twierdzenia o minimalnym przekroju i maksymalnym przepływie. Algorytm bazuje na dwóch funkcjach:
Push
Push z do oznacza przesłanie całej możliwej ilości nadmiarowego przepływu z do Aby przeprowadzić procedurę push, spełnione muszą być trzy warunki:
jest aktywny lub Więcej przepływu dociera do wierzchołka niż go opuszcza. Istnieje krawędź residualna od do dla której jest wyższy niż
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 zwiększamy jego wysokość do momentu kiedy jest o 1 większa od najniższego sąsiada w grafie residualnym. Warunki dla relabel:
jest aktywny gdzie
Mamy więc nadmiarowy przepływ do przesłania, jednak nie znajdujemy się wyżej niż którykolwiek z sąsiadów posiadają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 wygląda 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 Czynnikiem zwiększającym pesymistyczną złożoność algorytmu jest ilość wykonywanych operacji non-saturating push.
Algorytm Relabel-to-Front
Algorytm Relabel-to-Front jest wariantem algorytmu Push-Relabel, który obniża złożoność obliczeniową z do Osiąga się to dzięki przeprowadzeniu procedur push i relabel w określonym porządku. Główna różnica polega na tym, że wykonujemy push and relabel na pojedynczym wierzchołku do momentu, kiedy jego nadmiar jest zupełnie wykorzystany. To ogranicza ilość operacji non-saturating push, które stanowią czynnik zwiększający pesymistyczną złożoność obliczeniową algorytmu.
Aby to zrobić, tworzymy listę wszystkich wierzchołków w grafie 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 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 następująco:
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. Kolejność ta ogranicza ilość 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 (dowód pomijamy). Ponownie czynnikiem zwiększającym pesymistyczną złożoność algorytmu jest ilość 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 do w grafie esidualnym.
Przykładowe implementacje
Implementacja w C:
#include <stdlib.h> #include <stdio.h> #define NODES 6 #define MIN(X,Y) ((X) < (Y) ? (X) : (Y)) #define INFINITE 10000000 void push(const int * const * C, int ** F, int *excess, int u, int v) { int send = MIN(excess[u], C[u][v] - F[u][v]); F[u][v] += send; F[v][u] -= send; excess[u] -= send; excess[v] += send; } void relabel(const int * const * C, const int * const * F, int *height, int u) { int v; int min_height = INFINITE; for (v = 0; v < NODES; v++) { if (C[u][v] - F[u][v] > 0) { min_height = MIN(min_height, height[v]); height[u] = min_height + 1; } } }; void discharge(const int * const * C, int ** F, int *excess, int *height, int *seen, int u) { while (excess[u] > 0) { if (seen[u] < NODES) { int v = seen[u]; if ((C[u][v] - F[u][v] > 0) && (height[u] > height[v])){ push(C, F, excess, u, v); } else seen[u] += 1; } else { relabel(C, F, height, u); seen[u] = 0; } } } void moveToFront(int i, int *A) { int temp = A[i]; int n; for (n = i; n > 0; n--){ A[n] = A[n-1]; } A[0] = temp; } int pushRelabel(const int * const * C, int ** F, int source, int sink) { int *excess, *height, *list, *seen, i, p; excess = (int *) calloc(NODES, sizeof(int)); height = (int *) calloc(NODES, sizeof(int)); seen = (int *) calloc(NODES, sizeof(int)); list = (int *) calloc((NODES-2), sizeof(int)); for (i = 0, p = 0; i < NODES; i++){ if((i != source) && (i != sink)) { list[p] = i; p++; } } height[source] = NODES; excess[source] = INFINITE; for (i = 0; i < NODES; i++) push(C, F, excess, source, i); p = 0; while (p < NODES - 2) { int u = list[p]; int old_height = height[u]; discharge(C, F, excess, height, seen, u); if (height[u] > old_height) { moveToFront(p,list); p=0; } else p += 1; } int maxflow = 0; for (i = 0; i < NODES; i++) maxflow += F[source][i]; free(list); free(seen); free(height); free(excess); return maxflow; } void printMatrix(const int * const * M) { int i,j; for (i = 0; i < NODES; i++) { for (j = 0; j < NODES; j++) printf("%d\t",M[i][j]); printf("\n"); } } int main(void) { int **flow, **capacities, i; flow = (int **) calloc(NODES, sizeof(int*)); capacities = (int **) calloc(NODES, sizeof(int*)); for (i = 0; i < NODES; i++) { flow[i] = (int *) calloc(NODES, sizeof(int)); capacities[i] = (int *) calloc(NODES, sizeof(int)); } //Sample graph capacities[0][1] = 2; capacities[0][2] = 9; capacities[1][2] = 1; capacities[1][3] = 0; capacities[1][4] = 0; capacities[2][4] = 7; capacities[3][5] = 7; capacities[4][5] = 4; printf("Capacity:\n"); printMatrix(capacities); printf("Max Flow:\n%d\n", pushRelabel(capacities, flow, 0, 5)); printf("Flows:\n"); printMatrix(flow); return 0; }
Implementacja w Pythonie:
def relabel_to_front(C, source, sink): n = len(C) # C - macierz przepustowości F = [[0] * n for _ in xrange(n)] # przepustowość residualna z u do v wynosi C[u][v] - F[u][v] height = [0] * n # wysokość wierzchołka excess = [0] * n # różnica między przepływem wpływającym do wierzchołka a opuszczającym go seen = [0] * n # wierzchołki odwiedzone od czasu ostatniego wywołania relabel # kolejka wierzchołków nodelist = [i for i in xrange(n) if i != source and i != sink] def push(u, v): send = min(excess[u], C[u][v] - F[u][v]) F[u][v] += send F[v][u] -= send excess[u] -= send excess[v] += send def relabel(u): # znajdź najmniejszą wysokość umożliwiającą # operację push min_height = ∞ for v in xrange(n): if C[u][v] - F[u][v] > 0: min_height = min(min_height, height[v]) height[u] = min_height + 1 def discharge(u): while excess[u] > 0: if seen[u] < n: # sprawdź kolejnego sąsiada v = seen[u] if C[u][v] - F[u][v] > 0 and height[u] > height[v]: push(u, v) else: seen[u] += 1 else: # odwiedzono wszystkich sąsiadów, wykonujemy relabel relabel(u) seen[u] = 0 height[source] = n # najdłuższa ścieżka z s to t jest mniejsza niż n excess[source] = Inf # prześlij jak najwięcej przepływu do wszystkich sąsiadów s for v in xrange(n): push(source, v) p = 0 while p < len(nodelist): u = nodelist[p] old_height = height[u] discharge(u) if height[u] > old_height: nodelist.insert(0, nodelist.pop(p)) # przenieś na początek listy p = 0 # zacznij od początku listy else: p += 1 return sum(F[source])
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.
- p
- d
- e
Najważniejsze pojęcia |
więcej... |
---|---|
Wybrane klasy grafów | |
Algorytmy grafowe | |
problemy grafowe | |
Inne zagadnienia |