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ż
Algorytm Floyda-Warshalla – algorytm służący do wyznaczania najkrótszych ścieżek pomiędzy każdą parą wierzchołków w grafie. Jest to algorytm oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n3) i złożoność pamięciową O(n2), gdzie n jest liczbą wierzchołków.
Algorytm dopuszcza krawędzie o ujemnych wagach, o ile nie tworzą ujemnych cykli. Algorytm może być również wykorzystywany do wyszukiwania ujemnych cykli w grafie.
Wyznaczanie maksymalnego przepływu – problem obliczeniowy polegający na wyznaczeniu maksymalnego przepływu w sieci przepływowej.
Sieć przepływowa jest skierowanym grafem prostym. Każdy łuk (krawędź skierowana w grafie) ma swoją nieujemną wagę, która oznacza maksymalny dopuszczalny przepływ w tym łuku. Na potrzeby tego artykułu nazwijmy rzeczy przepływające przez sieć danymi. Jeden z wierzchołków sieci jest źródłem, z którego wypływają przesyłane dane. Inny z wierzchołków to ujście, do którego te dane wpływają. Zakłada się ponadto, że dla każdego z pozostałych wierzchołków istnieje ścieżka ze źródła do ujścia przechodząca przez ten wierzchołek.
Przepływem w sieci nazywamy przyporządkowanie każdemu łukowi pewnej wartości, która oznacza liczbę danych aktualnie przesyłanych przez ten łuk. Wartości te muszą spełniać następujące warunki:
- Wartość przyporządkowana krawędzi musi być mniejsza lub równa jej wadze (warunek przepustowości).
- Do każdego wierzchołka (poza źródłem i ujściem) musi wpływać tyle samo danych, ile z niego wypływa (warunek zachowania przepływu).
Omawiany problem polega na dobraniu takiego przepływu, aby liczba danych wypływających ze źródła (i zarazem wpływających do ujścia) była jak największa.
Algorytm genetyczny – metaheurystyka inspirowana biologiczną ewolucją.
Pojęcie algorytmu genetycznego nie jest powiązane z żadnym konkretnym problemem obliczeniowym, algorytm ten może być wykorzystywany do rozwiązywania różnych problemów. Algorytm genetyczny nie próbuje rozwiązywać problemu w sposób analityczny, ale próbuje uzyskać jak najlepsze rozwiązania poprzez wybieranie jak najlepszych cech rozwiązań z określonej puli. Implementując algorytm genetyczny należy przedstawić potencjalne rozwiązanie problemu w postaci jakiejś struktury danych, a następnie zdefiniować operacje krzyżowania, mutacji i selekcji. Zakładamy, że z każdym kolejnym pokoleniem rozwiązania występujące w populacji będą coraz lepsze.