Metoda Forda-Fulkersona
(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)
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:
- Wyznacz sieć residualną (opis sieci residualnej znajduje się w dalszej części artykułu).
- Znajdź w sieci residualnej dowolną ścieżkę powiększającą.
- Jeśli nie udało się wyznaczyć żadnej ścieżki powiększającej, zakończ działanie algorytmu.
- 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.
Liczba głosów: 3.
- Algorytm Edmondsa-Karpa
- Metoda Forda-Fulkersona
- Metoda z zastosowaniem przepływu blokującego
Dodano: 12 grudnia 2017 15:56, ostatnia edycja: 24 kwietnia 2020 20:19.
Zobacz też
Matroid – struktura matematyczna składająca się z niepustego zbioru elementów E i takiej rodziny jego podzbiorów I, że spełnione są następujące warunki:
- Jeśli jakiś zbiór należy do I, to wszystkie jego podzbiory także należą do I.
- Jeśli weźmiemy dowolne dwa zbiory należące do I o różnej liczbie elementów, to jesteśmy w stanie dodać do mniejszego z nich taki element z większego (spośród tych, które nie należą do mniejszego), że utworzony w ten sposób zbiór także będzie należał do I.
Drugi warunek, zwany własnością wymiany, formalnie może być zapisany jako:
$$⋀↙{A,B∊I}↙{ |A|>|B| }⋁↙{t∊(A-B)} B∪\{t\} ∈ I$$Co istotne, rodzina zbiorów I nie musi zawierać wszystkich możliwych podzbiorów zbioru E. Ważne tylko, aby była spełniona własność wymiany. Przykładowo, dla E={a,b,c,d} prawidłową rodziną I, może być zarówno { {a,b}, {b,c}, {a}, {b}, {c}, ∅}, jak i { {a}, {b}, {c}, {d}, ∅}. Trywialnym przypadkiem poprawnego matroidu jest taki, w którym rodzina I zawiera jedynie zbiór pusty.
Sortowanie przez scalanie – rekurencyjny algorytm sortowania wykorzystujący metodę dziel i zwyciężaj.
Metoda Otsu – algorytm służący do binaryzacji obrazu, czyli przekształcenia obrazu w odcieniach szarości do obrazu binarnego. Metoda ta realizuje progowanie globalne – dla całego obrazu wyznaczany jest jeden próg jasności, a następnie wszystkim pikselom jaśniejszym od tego progu przypisywana jest jedna wartość, a ciemniejszym druga.
Algorytm jest oparty na analizie histogramu. Przygotowanie histogramu polega na zliczeniu pikseli w każdym możliwym odcieniu (zazwyczaj liczba odcieni wynosi 256, gdyż tyle da się zakodować w jednym bajcie). Następnie należy sprawdzić każdy możliwy próg jasności i wybrać ten, dla którego wariancja międzyklasowa jest największa (lub suma ważona wariancji wewnątrzklasowych jest najmniejsza).
Jeśli obrazem wejściowym jest obraz kolorowy, można go łatwo sprowadzić do odcieni szarości. W przypadku kolorów zakodowanych w RGB najprostszym rozwiązaniem jest uśrednienie dla każdego piksela wartości wszystkich trzech kanałów.