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ż
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.
Algorytm Edmondsa-Karpa – algorytm wyszukiwania maksymalnego przepływu w sieci przepływowej. Jest to przypadek szczególny algorytmu Forda-Fulkersona.
W algorytmie Edmondsa-Karpa ścieżka powiększająca wyznaczana jest za pomocą przeszukiwania grafu wszerz. Dzięki temu w każdej iteracji algorytmu dołączana jest zawsze najkrótsza (pod względem liczby krawędzi) ścieżka powiększająca. W metodzie Forda-Fulkersona sposób wyznaczania ścieżki powiększającej jest dowolny.
Rekurencja (inaczej rekursja) – odwołanie się funkcji lub definicji do samej siebie. Mówiąc inaczej, podejście rekurencyjne polega na tym, że rozwiązanie problemu wyraża się za pomocą rozwiązania tego samego problemu dla mniejszych danych wejściowych. Stosowanie rekurencji jest charakterystyczne dla algorytmów projektowanych metodą dziel i zwyciężaj.
Typowym problemem, dla którego można zastosować rekurencję, jest obliczanie silni. Przypomnijmy, że silnia z n jest zdefiniowana jako n!=1×2×…×n. Funkcja ta może być równoważnie zapisana jako:
n!=(n−1)!×n, dla n>0,
n!=1, dla n=0.
W powyższym przykładzie górny wiersz jest ogólnym równaniem rekurencji, zaś dolny wiersz jest wartością brzegową. W języku C++ powyższa funkcja byłaby zapisana w poniższy sposób.
int silnia(int n)
{
if (n > 0)
{
return n * silnia(n-1);
}
else
{
return 1;
}
};
Przekształcenie postaci rekurencyjnej funkcji do postaci zwartej (tzn. takiej, która nie zawiera odwołania do samej siebie) jest określane jako rozwiązanie rekurencji. Metody rozwiązywania rekurencji są dostępne między innymi w książkach podanych w bibliografii.
Algorytmy stosujące rekurencję są zazwyczaj proste w implementacji. Jednocześnie wiążą się one z pewnymi problemami. Przy podejściu rekurencyjnym ta sama funkcja jest wywoływana wielokrotnie, co zużywa pamięć operacyjną (w skrajnych przypadkach może to spowodować przepełnienie stosu).