Algorytm Forda-Fulkersona
- Autor metody
- Lester R. Ford and Delbert R. Fulkerson
- Rok
- 1956
- 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 Forda-Fulkersona, opracowany przez Lestera R. Forda i Delberta R. Fulkersona w 1956 roku, jest fundamentalną metodą obliczania maksymalnego przepływu w sieci przepływowej.
Znajduje on maksymalną ilość przepływu, która może być wysłana ze źródła do ujścia przez graf skierowany z ograniczeniami przepustowości na krawędziach.
Intuicja stojąca za metodą
Algorytm działa poprzez wielokrotne wyszukiwanie ścieżek powiększających od źródła do ujścia w sieci rezydualnej, gdzie każda krawędź ma pozostałą przepustowość. Każda ścieżka wnosi dodatkowy przepływ równy jej przepustowości wąskiego gardła (krawędź o minimalnej pozostałej przepustowości na ścieżce). Proces trwa do momentu, gdy nie można już znaleźć więcej ścieżek powiększających, co oznacza osiągnięcie maksymalnego przepływu. Kluczowym spostrzeżeniem jest twierdzenie o maksymalnym przepływie i minimalnym przekroju: maksymalny przepływ jest równy minimalnej przepustowości przekroju w sieci.
Historia
Ford i Fulkerson wprowadzili problem maksymalnego przepływu i swój przełomowy algorytm w 1956 roku. Praca ta była rewolucyjna, ustanawiając zarówno metodę algorytmiczną, jak i słynne twierdzenie o maksymalnym przepływie i minimalnym przekroju. Edmonds i Karp (1972) poprawili złożoność w najgorszym przypadku, używając przeszukiwania wszerz do wyboru ścieżki. Kolejne postępy dokonane przez Dinica, Karzanova i innych doprowadziły do jeszcze szybszych algorytmów, ale metoda Forda-Fulkersona pozostaje klasycznym i pedagogicznie cennym algorytmem w informatyce.
Kiedy stosować
Zastosuj algorytm Forda-Fulkersona do znalezienia maksymalnego przepływu w sieciach przepływowych skierowanych lub nieskierowanych z dodatnimi całkowitymi przepustowościami. Dobrze działa dla sieci małych i średnich oraz zapewnia intuicyjne zrozumienie koncepcji przepływu w sieci. Dla bardzo dużych sieci lub gdy wymagane są przepływy całkowite, rozważ algorytm Edmonds-Karp (używający BFS) lub algorytm Dinica dla lepszej wydajności w najgorszym przypadku. Używaj go, gdy zrozumienie zachowania algorytmu jest równie ważne jak szybkość.
Ograniczenia i uwagi
- Złożoność czasowa zależy od wartości przepustowości (ogólnie nie jest wielomianowa; może być wykładnicza przy przepustowościach niewymiernych)
- Może nie zbiegać, jeśli przepustowości są niewymierne (wymaga starannej implementacji z arytmetyką wymierną)
- Mniej wydajny niż wyspecjalizowane algorytmy, takie jak Edmonds-Karp lub Dinic, na dużych sieciach
- Wrażliwy na kolejność wyboru ś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
- Proste i intuicyjne podejście oparte na ścieżkach powiększających
- Gwarancja optymalnego rozwiązania, gdy przepustowości są wymierne lub całkowite
- Wydajny dla sieci z małymi całkowitymi przepustowościami
- Stanowi teoretyczną podstawę do zrozumienia dualności maksymalnego przepływu i minimalnego przekroju
- Działa zarówno z grafami skierowanymi, jak i nieskierowanymi
Zastosowania
- Routing sieciowy: maksymalizacja przepustowości danych ze źródła do miejsca docelowego w sieciach komunikacyjnych
- Sieci transportowe: określanie maksymalnej przepustowości ładunków między miastami z uwzględnieniem ograniczeń drogowych i kolejowych
- Dopasowanie dwudzielne: znajdowanie maksymalnych dopasowań w grafach dwudzielnych poprzez konstrukcję sieci przepływowych
- Segmentacja obrazu: wykorzystanie algorytmów maksymalnego przepływu do podziału obrazów na tło i pierwszy plan
- Planowanie lotnicze: optymalizacja tras samolotów w celu maksymalizacji przepływu pasażerów przez sieci typu hub-and-spoke
- Analiza białek: obliczanie maksymalnego przepływu w sieciach biologicznych w celu zrozumienia szlaków interakcji
Jak to działa
Jak to działa
Zainicjuj graf rezydualny z przepustowościami równymi oryginalnym przepustowościom krawędzi i zerowym przepływem na wszystkich krawędziach.
Znajdź ścieżkę powiększającą od źródła do ujścia w grafie rezydualnym za pomocą przeszukiwania w głąb (DFS) lub wszerz (BFS), oblicz minimalną przepustowość wzdłuż ścieżki i dodaj ten przepływ do wszystkich krawędzi na ścieżce, jednocześnie zmniejszając ich przepustowości rezydualne.
Powtarzaj powiększanie, aż nie będzie więcej ścieżek powiększających w grafie rezydualnym; całkowity zgromadzony przepływ jest maksymalnym przepływem.
Częste pułapki
- Wybór niekorzystnych ścieżek powiększających prowadzący do powolnej zbieżności lub błędnych wyników
- Nieprawidłowe aktualizowanie przepustowości rezydualnych lub dodawanie krawędzi wstecznych do cofania przepływu
- Używanie dzielenia całkowitoliczbowego lub arytmetyki zmiennoprzecinkowej, gdy do poprawności wymagana jest arytmetyka dokładna
Najczęściej zadawane pytania
Czym jest twierdzenie o maksymalnym przepływie i minimalnym przekroju?
Twierdzenie to stwierdza, że maksymalny przepływ ze źródła do ujścia jest równy minimalnej przepustowości dowolnego przekroju oddzielającego źródło od ujścia. Stanowi to zarówno wgląd teoretyczny, jak i metodę weryfikacji dla algorytmów przepływu.
Dlaczego algorytm czasami zbiega powoli?
Przy niekorzystnych wyborach ścieżek algorytm może powiększać przepływ tylko o jedną jednostkę na iterację, nawet gdy możliwe są większe powiększenia. Użycie przeszukiwania wszerz (Edmonds-Karp) zapewnia zbieżność w czasie wielomianowym.
Jak algorytm radzi sobie z krawędziami nieskierowanymi?
Każdą krawędź nieskierowaną zastępuje się dwiema krawędziami skierowanymi w przeciwnych kierunkach, obie o tej samej przepustowości. Algorytm następnie znajduje przepływ w sieci skierowanej.
Jaka jest różnica między przepływem na krawędzi a przepustowością rezydualną?
Przepływ na krawędzi reprezentuje ilość materiału wysłanego wzdłuż niej, podczas gdy przepustowość rezydualna to dostępna pozostała przepustowość. Przepustowość rezydualna maleje wraz ze wzrostem przepływu, a krawędzie wsteczne śledzą możliwość cofnięcia przepływu.
Pokrewne metody
Źródła
Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8(3), 399-404.
Otwórz odnośnik DOISkopiowano.Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
ISBN: 978-0-262-03384-8Skopiowano.