Metoda z zastosowaniem przepływu blokującego

REKLAMA Thinking in Java. Edycja polska. Wydanie IV
149,00 zł
Czysta architektura. Struktura i design oprogramowania. Przewodnik dla profesjonalistów
67,00 zł
Deep Learning. Praca z językiem Python i biblioteką Keras
−30%41,30 zł
Wzorce projektowe. Elementy oprogramowania obiektowego wielokrotnego użytku
59,00 zł

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

  1. Wyznacz sieć residualną.
  2. Przekształć sieć residualną do warstwowej sieci residualnej.
  3. Jeśli warstwowa sieć residualna nie zawiera żadnej ścieżki prowadzącej ze źródła do ujścia, zakończ działanie algorytmu.
  4. Wyznacz przepływ blokujący w warstwowej sieci residualnej.
  5. Powiększ przepływ w sieci przepływowej o przepływ blokujący.
  6. 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.
Ocena: 0 Tak Nie
Liczba głosów: 0.

Dodano: 29 grudnia 2017 13:58, ostatnia edycja: 30 stycznia 2019 15:59.

REKLAMA

Zobacz też

Metoda przyrostowa – technika projektowania algorytmów polegająca na dodawaniu do rozwiązania kolejnych elementów z danych wejściowych. Przykładem algorytmu opartego na tej metodzie jest sortowanie przez wstawianie, gdzie kolejne elementy są wstawiane do posortowanej części tablicy.

Jest to metoda prosta, jednak sprawdza się tylko dla niektórych problemów obliczeniowych.

→ Czytaj całość

Przeszukiwanie w głąb (ang. depth-first search, w skrócie DFS) – jeden z dwóch podstawowych algorytmów przeszukiwania grafu. Polega na przechodzeniu zawsze do kolejnego nieodwiedzonego wierzchołka. Jeśli dany wierzchołek nie ma nieodwiedzonych sąsiadów, wracamy do poprzedniego wierzchołka i sprawdzamy jego sąsiadów. Mówiąc obrazowo, w algorytmie tym wchodzimy tak głęboko, jak to możliwe (przechodzimy dalej, dopóki się da).

Algorytm można zapisać w sposób rekurencyjny. Wywoływana rekurencyjnie procedura działa następująco: oznacz wierzchołek jako odwiedzony, a następnie wywołaj tę procedurę dla każdego sąsiada danego wierzchołka, jeśli nie został on wcześniej odwiedzony. Na początku wywołujemy procedurę dla wierzchołka początkowego.

→ Czytaj całość

Algorytm – przepis, zbiór poleceń, opis ciągu operacji prowadzących do rozwiązania konkretnego problemu. Algorytm możemy również rozumieć jako funkcję przekształcającą dane wejściowe w dane wyjściowe.

Algorytm musi być skończony, czyli jego zapis ma składać się ze skończonej liczby znaków. Musi również być poprawny, czyli dla wszystkich możliwych danych wejściowych powinien zwracać prawidłowy wynik (może być nim informacja o braku rozwiązania). Algorytm musi wykazywać również własność stopu – niezależnie od danych wejściowych obliczenia algorytmu powinny dochodzić do punktu końcowego, czyli po prostu kończyć się (nie mogą np. wpadać w nieskończoną iterację). Zapis algorytmu musi być precyzyjny, bez jakichkolwiek niejasności.

→ Czytaj całość
Polityka prywatnościKontakt