Przejdź do treści
Wróć do wyników wyszukiwania

Algorytm Push-Relabel

Autor metody
Andrew V. Goldberg and Robert E. Tarjan
Rok
1988
Typ
algorithm
Rodzina
Graph Algorithms

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Algorytm Push-Relabel, opracowany przez Andrew V. Goldberga i Roberta E. Tarjana w 1988 roku, jest wysoce wydajną metodą obliczania maksymalnego przepływu w sieciach.

W przeciwieństwie do metod ścieżek powiększających, utrzymuje on pre-przepływ i wykorzystuje lokalne operacje wypychania (push) oraz globalnego przekalibrowania (relabel) w celu skierowania przepływu do ujścia, osiągając lepszą złożoność w najgorszym przypadku.

Intuicja stojąca za metodą

Algorytm utrzymuje „wysokość” lub „etykietę odległości” dla każdego węzła i wykorzystuje pre-przepływ (gdzie węzły mogą tymczasowo przekraczać zapotrzebowanie ujścia). Powtarzalnie wypycha nadwyżkę przepływu z węzłów o wyższych etykietach do sąsiadów o niższych etykietach i przekalibrowuje węzły, aby utworzyć ścieżki do ujścia. Kluczowe spostrzeżenie polega na tym, że dzięki utrzymywaniu niezmienników wysokości i wykorzystaniu wydajnych struktur danych, algorytm unika wielokrotnego przeszukiwania całego grafu, co jest konieczne w metodach ścieżek powiększających. Algorytm kończy działanie, gdy cały pre-przepływ dotrze do ujścia.

Historia

Goldberg i Tarjan opublikowali swój algorytm push-relabel w 1988 roku, wprowadzając fundamentalnie odmienny paradygmat obliczania maksymalnego przepływu. Ich algorytm osiągnął złożoność w najgorszym przypadku O(V³), co stanowiło poprawę w stosunku do O(VE²) algorytmu Edmonds-Karp. W kolejnych dekadach opracowano liczne warianty, w tym heurystyki luki (Goldberg i Tarjan, 1990), reguły najwyższej etykiety (highest-label rules) oraz najnowsze warianty osiągające empiryczną wydajność bliską liniowej w sieciach rzeczywistych.

Kiedy stosować

Zastosuj algorytm push-relabel do obliczania maksymalnego przepływu w dużych, gęstych sieciach, gdzie metody ścieżek powiększających stają się nieefektywne. Jest on szczególnie skuteczny w sieciach z tysiącami lub milionami krawędzi. Używaj go, gdy potrzebujesz gwarantowanego czasu działania w czasie wielomianowym i chcesz wykorzystać nowoczesne struktury danych. W przypadku sieci rzadkich lub celów edukacyjnych, metody ścieżek powiększających mogą być prostsze do zrozumienia i zaimplementowania.

Ograniczenia i uwagi

  • Bardziej złożony do zrozumienia i zaimplementowania niż metody ścieżek powiększających
  • Wymaga starannego zarządzania strukturami danych (listy rozładowania, heurystyki luki) dla optymalnej wydajności
  • Złożoność w najgorszym przypadku nadal wyższa niż niektórych wyspecjalizowanych algorytmów dla specyficznych klas grafów
  • Mniej intuicyjne zrozumienie procesu rozwiązywania w porównaniu do ścieżek powiększających

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Lepsza złożoność w najgorszym przypadku: O(V³) lub O(V²√E) z heurystyką luki (gap heuristic)
  • Wysoce wydajny w praktyce, szczególnie w dużych i gęstych sieciach
  • Lokalność operacji (push/relabel) pozwala na dobrą wydajność pamięci podręcznej
  • Nadaje się do paralelizacji i implementacji rozproszonych
  • Wiele wariantów implementacji dla różnych struktur problemów

Zastosowania

  • Routing sieciowy: obliczanie maksymalnej przepustowości w wielkoskalowych sieciach komunikacyjnych
  • Przetwarzanie obrazów: wykorzystanie max-flow do segmentacji obrazów i aplikacji mattingowych
  • Optymalizacja linii lotniczych: określanie maksymalnego przepływu pasażerów przez złożone sieci tras
  • Analiza sieci energetycznych: obliczanie maksymalnej przepustowości przesyłu mocy w sieciach elektrycznych
  • Zarządzanie łańcuchem dostaw: optymalizacja przepływu produktów przez wielopoziomowe sieci dystrybucji
  • Sieci biologiczne: analiza maksymalnego przepływu w sieciach metabolicznych i interakcji białek

Jak to działa

Jak to działa

1

Ustaw wysokość źródła na liczbę wierzchołków, wszystkie inne wysokości na zero. Nasyć wszystkie krawędzie wychodzące ze źródła, tworząc początkowy pre-przepływ (nadwyżkę w sąsiednich węzłach).

2

Powtarzalnie wybieraj aktywny węzeł (z nadwyżką przepływu) i albo wypychaj nadwyżkę do sąsiada o niższej wysokości, albo przekalibruj węzeł, aby zwiększyć jego wysokość. Używaj wydajnych strategii wyboru i operacji rozładowania (discharge), aby zminimalizować liczbę iteracji.

3

Kontynuuj, aż nie pozostaną żadne aktywne węzły, w którym to momencie cały pre-przepływ zostanie rozwiązany jako maksymalny przepływ od źródła do ujścia.

Częste pułapki

  • Nieprawidłowe implementowanie aktualizacji wysokości lub operacji wypychania prowadzące do nie-maksymalnych przepływów
  • Zaniedbanie stosowania heurystyk luki i wydajnego wyboru węzłów, skutkujące słabą wydajnością praktyczną
  • Niewłaściwe utrzymanie niezmiennika pre-przepływu (nadwyżka w węzłach i ograniczenia przepustowości na krawędziach)

Najczęściej zadawane pytania

Jaka jest różnica między pre-przepływem a przepływem?

Pre-przepływ tymczasowo pozwala węzłom na przechowywanie nadwyżki przepływu (wpływ minus wypływ może być dodatni), podczas gdy prawdziwy przepływ musi być zachowany we wszystkich węzłach z wyjątkiem źródła i ujścia. Algorytm kończy działanie, gdy pre-przepływ stanie się prawidłowym przepływem.

Jaki jest cel funkcji wysokości?

Wysokości tworzą quasi-miarę odległości: przepływ może być wypychany tylko w dół (z wyższych na niższe wysokości), zapobiegając niepotrzebnym cyklom i zapewniając zakończenie. Wysokości są zwiększane poprzez przekalibrowanie w celu utworzenia nowych ścieżek w razie potrzeby.

Czym jest heurystyka luki i dlaczego jest ważna?

Heurystyka luki wykrywa, gdy żaden węzeł nie ma wysokości w pewnym zakresie, wskazując, że niektóre węzły nie mogą dotrzeć do ujścia. Węzły te i ich nadwyżki są szybko identyfikowane i przetwarzane, co znacznie poprawia wydajność praktyczną.

Jak algorytm push-relabel wypada w praktyce w porównaniu do Edmonds-Karp?

Algorytm push-relabel ma lepszą złożoność w najgorszym przypadku i zazwyczaj przewyższa Edmonds-Karp na dużych sieciach, ale dla małych sieci lub grafów rzadkich, Edmonds-Karp może być prostszy do zaimplementowania przy konkurencyjnej wydajności.

Pokrewne metody

Źródła

  1. Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum flow problem. Journal of the ACM, 35(4), 921-940.

    Otwórz odnośnik DOI
    Skopiowano.
  2. Goldberg, A. V. (1998). Recent advances in maximum flow and minimum-cost flow algorithms. In Algorithm Theory (pp. 1-10). Springer, Berlin.

    Otwórz odnośnik do publikacji
    Skopiowano.