Metoda Forda-Fulkersona

Sieć przepływowa i residualna (1) Sieć przepływowa z pewnym przepływem (na górze), odpowiadająca jej sieć residualna (w środku) z zaznaczoną ścieżką powiększającą i ta sama sieć przepływowa po zwiększeniu przepływu (na dole)
REKLAMA Programowanie w języku C. Ćwiczenia praktyczne. Wydanie II
19,90 zł
Czysty kod. Podręcznik dobrego programisty
69,00 zł
Gotowanie dla geeków. Wydanie II
−30%48,30 zł
Kwalifikacja EE.09. Programowanie, tworzenie i administrowanie stronami internetowymi i bazami danych. Część 1. Tworzenie stron internetowych. Podręcznik do nauki zawodu technik informatyk
47,00 zł

Metoda Forda-Fulkersona – algorytm służący do wyznaczania maksymalnego przepływu. Jest to algorytm bardzo ogólny, dlatego często nie jest nazywany algorytmem, a metodą. Popularną implementacją tej metody jest algorytm Edmondsa-Karpa. Algorytm można opisać następująco:

  1. Wyznacz sieć residualną (opis sieci residualnej znajduje się w dalszej części artykułu).
  2. Znajdź w sieci residualnej dowolną ścieżkę powiększającą.
  3. Jeśli nie udało się wyznaczyć żadnej ścieżki powiększającej, zakończ działanie algorytmu.
  4. W przeciwnym razie zwiększ przepływ w sieci (w sposób opisany w dalszej części artukułu) i wróć do punktu 1.

Sieć residualna i ścieżka powiększająca

Sieć residualna jest grafem skierowanym tworzonym na podstawie sieci przepływowej i jej aktualnego przepływu. Wagi łuków w sieci residualnej oznaczają, o ile można zmienić przepływ w odpowiadającym mu łuku sieci przepływowej.

Liczba i układ łuków w sieci residualnej mogą być nieco inne, niż w sieci przepływowej. Jeśli przepływ w danym łuku sieci przepływowej jest większy od zera, to przepływ w tym łuku da się zmniejszyć – w sieci residualnej pojawi się wówczas dodatkowo łuk skierowany w przeciwną stronę, niż łuk w sieci przepływowej. Jeśli natomiast przepływ w łuku sieci przepływowej jest już maksymalny, to nie można go zwiększyć, zatem taki łuk nie będzie występował w sieci residualnej (będzie występował tylko łuk o przeciwnym zwrocie).

Ścieżka powiększająca to ścieżka w sieci residualnej prowadząca od źródła do ujścia. Najmniejsza spośród wag łuków należących do ścieżki powiekszającej jest określana jako jej przepustowość residualna. Jest to wartość, o którą można zwiększyć przepływ w sieci przepływowej.

Powiększenie przepływu w sieci o ścieżkę powiększającą można opisać następująco. Dla każdego łuku należącego do ścieżki powiększającej:

  • Jeśli taki łuk istnieje w sieci przepływowej, zwiększ jego przepływ o przepustowość residualną ścieżki powiększającej.
  • Jeśli taki łuk nie istnieje w sieci przepływowej, zmniejsz przepływ w łuku o przeciwnym zwrocie o przepustowość residualną ścieżki powiększającej.

Złożoność obliczeniowa

Ze względu na to, że metoda Forda-Fulkersona jest algorytmem bardzo ogólnym, złożoność obliczeniowa zależy od konkretnej implementacji. Jeśli założymy, że przepływy w łukach są liczbami naturalnymi, to możemy oszacować górne ograniczenie tej złożoności. W każdej iteracji algorytmu powiększymy przepływ o co najmniej 1, zatem liczba wykonań głównej pętli algorytmu będzie mniejsza bądź równa od maksymalnego przepływu (oznaczmy go f). W trakcie wyznaczania ścieżki powiększającej i zwiększania przepływu musimy przejrzeć w najgorszym wypadku wszystkie krawędzie (oznaczmy ich liczbę jako e). Kres górny złożoności czasowej jest zatem rzędu O(fe).

Bibliografia

  • T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, Warszawa, 2012, ISBN 9788301169114.
  • A. Debudaj-Grabysz, S. Deorowicz, J. Widuch, Algorytmy i struktury danych. Wybór zaawansowanych metod, Wydawnictwo Politechniki Śląskiej, Gliwice, 2012, ISBN 9788373359383.
Ocena: 0 Tak Nie
Liczba głosów: 0.

Dodano: 12 grudnia 2017 15:56, ostatnia edycja: 26 stycznia 2019 17:50.

REKLAMA

Zobacz też

Przeszukiwanie wszerz (ang. breadth-first search, w skrócie BFS) – jeden z dwóch podstawowych algorytmów przeszukiwania grafu. Polega na przeglądaniu wierzchołków grafu według ich odległości od wierzchołka źródłowego (wyrażanej w liczbie krawędzi).

→ Czytaj całość

Algorytm heurystyczny, heurystyka – algorytm niedający (w ogólnym przypadku) gwarancji znalezienia rozwiązania optymalnego, umożliwiający jednak znalezienie rozwiązania dość dobrego w rozsądnym czasie. Algorytmy tego typu używane są w takich problemach obliczeniowych, gdzie znalezienie rozwiązania optymalnego ma zbyt dużą złożoność obliczeniową (w szczególności są to problemy NP-trudne) lub w ogóle nie jest możliwe.

Pojęcie algorytmów heurystycznych jest bardzo szerokie, dotyczy ono różnych technik projektowania algorytmów. Wiele heurystyk wykorzystuje losowość, inne zaś są deterministyczne (wówczas dla takich samych danych wejściowych algorytm zawsze zwróci ten sam wynik).

Ogólny algorytm heurystyczny (opisujący samą ideę poszukiwań) bywa określany w literaturze jako metaheurystyka. Zgodnie z tym nazewnictwem, metaheurystyką jest np. algorytm zachłanny (jako ogólna idea), zaś heurystyką jest np. algorytm najbliższego sąsiada (jako zastosowanie idei algorytmu zachłannego do konkretnego problemu).

→ Czytaj całość

Graf – struktura składająca się ze zbioru wierzchołków oraz zbioru krawędzi. Grafy mają szerokie zastosowanie w informatyce, można za ich pomocą przedstawić wiele zagadnień.

Wyróżniamy grafy nieskierowane oraz grafy skierowane. W grafie nieskierowanym relacja sąsiedztwa jest symetryczna, tzn. krawędź łączy wierzchołki „w obie strony”. W grafie skierowanym krawędzie są „jednokierunkowe”. Krawędź grafu skierowanego zazwyczaj jest określana jako łuk.

Graf ważony (inaczej graf z wagami) to taki graf, w którym każdej krawędzi przypisana jest pewna wartość liczbowa. Wartość ta może oznaczać np. długość krawędzi lub jej przepustowość.

→ Czytaj całość
Polityka prywatnościKontakt