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

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

Rozmiar czcionki

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

1

Zainicjuj graf rezydualny z przepustowościami równymi oryginalnym przepustowościom krawędzi i zerowym przepływem na wszystkich krawędziach.

2

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.

3

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

  1. Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8(3), 399-404.

    Otwórz odnośnik DOI
    Skopiowano.
  2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.

    ISBN: 978-0-262-03384-8
    Skopiowano.