Metoda z zastosowaniem przepływu blokującego
Metoda z zastosowaniem przepływu blokującego – algorytm wyznaczający maksymalny przepływ w sieci przepływowej. W algorytmie tym przepływ zwiększany jest iteracyjnie, w każdej iteracji wyznaczony przepływ jest powiększany o przepływ blokujący w warstwowej sieci residualnej.
Warstwowa sieć residualna
Warstwowa sieć residualna to taka sieć residualna, w której każda ścieżka ze źródła do dowolnego innego wierzchołka jest ścieżką najkrótszą (pod względem liczby krawędzi). Można ją wyznaczyć na podstawie zwykłej sieci residualnej poprzez usunięcie z niej:
- Wszystkich wierzchołków, które są bardziej odległe od źródła, niż ujście (wraz z krawędziami, które do nich prowadzą lub z nich wychodzą).
- Wszystkich łuków (krawędzi), które prowadzą z wierzchołka dalszego od źródła do wierzchołka bliższego (lub o równej odległości).
Pojęcie sieci residualnej zostało objaśnione w artykule na temat metody Forda-Fulkersona.
Przepływ blokujący w warstwowej sieci residualnej to taki przepływ, którego nie da się powiększyć poprzez zwiększanie przepływu w łukach (na każdej ścieżce ze źródła do ujścia jest co najmniej jeden łuk nasycony, czyli taki, dla którego nie da się już zwiększyć przepływu). Należy pamiętać, że mówimy tutaj o łukach warstwowej sieci residualnej, a nie o sieci przepływowej! Przepływ blokujący w warstwowej sieci residualnej nie musi być więc maksymalnym przepływem w sieci przepływowej.
Przebieg algorytmu
- Wyznacz sieć residualną.
- Przekształć sieć residualną do warstwowej sieci residualnej.
- Jeśli warstwowa sieć residualna nie zawiera żadnej ścieżki prowadzącej ze źródła do ujścia, zakończ działanie algorytmu.
- Wyznacz przepływ blokujący w warstwowej sieci residualnej.
- Powiększ przepływ w sieci przepływowej o przepływ blokujący.
- Wróć do punktu 1.
Wyznaczanie przepływu blokującego
Metoda opisana w tym artykule nie definiuje, w jaki sposób powinien być wyznaczony przepływ blokujący w warstwowej sieci residualnej (podobnie, jak w metodzie Forda-Fulkersona nie jest określony sposób wyznaczania ścieżki powiększającej. Do wyznaczenia ścieżki powiększającej można wykorzystać m.in. algorytm Dinica lub algorytm MKM (występujący również pod nazwą algorytm trzech Hindusów).Złożoność obliczeniowa
Algorytm wykona maksymalnie v−1 iteracji, gdzie v jest liczbą wierzchołków w sieci przepływowej. Wyznaczenie warstwowej sieci residualnej można wykonać w czasie O(e), gdzie e jest liczbą łuków w sieci przepływowej. Zwiększenie przepływu w sieci również można wykonać w czasie O(e). Złożoność obliczeniowa metody zależy od złożoności obliczeniowej algorytmu wyznaczającego przepływ blokujący. Jeśli oznaczymy tę złożoność jako T, to złożoność czasowa metody z wykorzystaniem przepływu blokującego wyniesie O(e⋅max(T,m)).
Bibliografia
- 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: 0.
- Algorytm Edmondsa-Karpa
- Metoda Forda-Fulkersona
- Metoda z zastosowaniem przepływu blokującego
Dodano: 29 grudnia 2017 13:58, ostatnia edycja: 30 stycznia 2019 15:59.
Zobacz też
Ten artykuł opisuje algorytm zachłanny rozwiązujący problem wydawania reszty. Algorytm ten polega na wybieraniu zawsze największej dostępnej monety, tzn. takiej, która nie jest większa od kwoty pozostałej do wydania.
Algorytm nie zawsze znajduje rozwiązanie optymalne. Przykładowo, dla zbioru nominałów {1, 3, 4} i kwoty 6 algorytm użyje najpierw monety o nominale 4 (pozostaje do wydania kwota 2), potem monety o nominale 1 (pozostaje kwota 1) i jeszcze raz monety o nominale 1. Łącznie algorytm użyje więc trzech monet, podczas gdy rozwiązanie optymalne wymaga użycia tylko dwóch (dwie monety o nominale 3).
Programowanie dynamiczne – technika projektowania algorytmów polegająca na rozwiązywaniu podproblemów i zapamiętywaniu ich wyników. W technice tej, podobnie jak w metodzie dziel i zwyciężaj, problem dzielony jest na mniejsze podproblemy. Wyniki rozwiązywania podproblemów są jednak zapisywane w tabeli, dzięki czemu w przypadku natrafienia na ten sam podproblem nie trzeba go ponownie rozwiązywać.
Wykorzystując programowanie dynamiczne można zastosować metodę zstępującą z zapamiętywaniem lub metodę wstępującą.
- Metoda zstępująca z zapamiętywaniem polega na rekurencyjnym wywoływaniu funkcji z zapamiętywaniem wyników. Metoda ta jest podobna do metody dziel i zwyciężaj – różni się od niej tym, że jeśli rozwiązanie danego problemu jest już w tabeli z wynikami, to należy je po prostu stamtąd odczytać.
- Metoda wstępująca polega na rozwiązywaniu wszystkich możliwych podproblemów, zaczynając od tych o najmniejszym rozmiarze. Wówczas w momencie rozwiązywania podproblemu na pewno są już dostępne rozwiązania jego podproblemów. W tym podejściu nie zużywa się pamięci na rekurencyjne wywołania funkcji. Może się jednak okazać, że część podproblemów została rozwiązana nadmiarowo (nie były one potrzebne do rozwiązania głównego problemu).
Powtarzalny algorytm najbliższego sąsiada (ang. repetitive nearest neighbour algorithm, w skrócie RNN) – algorytm służący do rozwiązywania problemu komiwojażera korzystający z algorytmu najbliższego sąsiada.
Algorytm polega na wielokrotnym wykonaniu algorytmu najbliższego sąsiada w taki sposób, aby każdy wierzchołek raz był wierzchołkiem początkowym. Następnie algorytm zwraca najlepsze spośród otrzymanych rozwiązań.
Dla grafu pełnego algorytm ma złożoność O(n3), gdzie n jest liczbą wierzchołków. W trakcie wykonywania algorytmu RNN n razy zostanie wykonany algorytm najbliższego sąsiada, który ma złożoność czasową O(n2).
Algorytm RNN nie daje gwarancji znalezienia rozwiązania optymalnego. W odróżnieniu od algorytmu najbliższego sąsiada daje jednak gwarancję, że zwróci rozwiązanie co najmniej tak dobre, jak n/2-1 innych rozwiązań (dowód i więcej informacji na ten temat znajduje się w pracy podanej w bibliografii).