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 Algorytmy
49,00 zł
Spring w akcji. Wydanie V
89,00 zł
Vue.js 2. Wprowadzenie dla profesjonalistów
−30%69,30 zł
Automatyzacja nudnych zadań z Pythonem. Nauka programowania
89,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ż

2-opt, algorytm 2-optymalny – algorytm lokalnej optymalizacji wykorzystywany przy rozwiązywaniu problemu komiwojażera. Jest to szczególny przypadek algorytmu k-optymalnego.

Algorytm 2-opt nie służy do wyznaczania trasy, a jedynie do ulepszania jej. Samą trasę można wyznaczyć np. za pomocą algorytmu najbliższego sąsiada. Algorytm może być wykorzystany do ulepszenia algorytmu genetycznego – w ten sposób powstanie algorytm memetyczny.

→ Czytaj całość

K-opt, algorytm k-optymalny – algorytm lokalnej optymalizacji wykorzystywany przy rozwiązywaniu problemu komiwojażera. Algorytm ten nie służy do samego wyznaczania trasy, a jedynie do ulepszania jej. Najprostszą wersją tego algorytmu jest algorytm 2-optymalny.

→ Czytaj całość

Algorytm Bellmana-Forda – algorytm służący do wyznaczania najkrótszych ścieżek w grafie. Wyznacza najkrótsze ścieżki z jednego wierzchołka (zwanego wierzchołkiem źródłowym) do pozostałych wierzchołków. W odróżnieniu od algorytmu Dijkstry, algorytm Bellmana-Forda dopuszcza krawędzie o ujemnych wagach, nie mogą istnieć jednak ujemne cykle osiągalne z wierzchołka źródłowego. Algorytm może być również wykorzystywany do sprawdzania, czy w grafie występują ujemne cykle.

Algorytm występuje również pod nazwą algorytm Bellmana-Forda-Moore’a.

→ Czytaj całość
Polityka prywatnościKontakt