Metoda z zastosowaniem przepływu blokującego

REKLAMA

Kwalifikacja INF.03. Tworzenie i administrowanie stronami i aplikacjami internetowymi oraz bazami danych. Część 1. Projektowanie stron internetowych. Podręcznik do nauki zawodu technik informatyk i technik programista
−15%50,91 zł
Algorytmy uczenia maszynowego. Zaawansowane techniki implementacji
−40%53,40 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ż

Problem wydawania reszty (ang. change-making problem) – problem obliczeniowy polegający na tym, aby mając określony zbiór nominałów wyrazić daną kwotę za pomocą jak najmniejszej liczby monet. Jest to szczególny przypadek problemu plecakowego.

→ Czytaj całość

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:

  1. Jeśli jakiś zbiór należy do I, to wszystkie jego podzbiory także należą do I.
  2. 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.

→ Czytaj całość

K-opt, algorytm k-optymalny – algorytm lokalnej optymalizacji wykorzystywany przy rozwiązywaniu problemu komiwojażera. Algorytm ten nie służy do samego wyznaczania trasy, a jedynie do ulepszania jej. Najprostszą wersją tego algorytmu jest algorytm 2-optymalny.

→ Czytaj całość
Polityka prywatnościKontakt