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
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
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).
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.
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
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 DOISkopiowano.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 publikacjiSkopiowano.