Wyznaczanie maksymalnego przepływu
(1) Przykładowa sieć przepływowa. Przy każdym łuku liczba przed ukośnikiem oznacza aktualny przepływ w tym łuku, a liczba po ukośniku oznacza przepływ maksymalny. Pokazany w sieci przepływ nie jest przepływem maksymalnym
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.
Wykorzystywane algorytmy
Do wyznaczania maksymalnego przepływu można wykorzystać następujące algorytmy:
- Metoda Forda-Fulkersona, której jedną z implementacji jest algorytm Edmondsa-Karpa.
- Metoda przepływu blokującego, w której do wyznaczania przepływu blokującego można wykorzystać m.in. algorytm Dinica lub algorytm MKM.
Bibliografia
- A. Debudaj-Grabysz, S. Deorowicz, J. Widuch, Algorytmy i struktury danych. Wybór zaawansowanych metod, Wydawnictwo Politechniki Śląskiej, Gliwice, 2012.
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: 4.
- Minimalne drzewo rozpinające
- Problem komiwojażera
- Problem wydawania reszty
- Sortowanie
- Wyznaczanie maksymalnego przepływu
- Wyznaczanie najkrótszej ścieżki
Dodano: 8 grudnia 2017 17:14, ostatnia edycja: 30 stycznia 2019 15:59.
Zobacz też
Ten artykuł opisuje algorytm rozwiązujący problem wydawania reszty oparty na programowaniu dynamicznym. Algorytm ten daje gwarancję znalezienia rozwiązania optymalnego.
Istnieje również pewna modyfikacja tego algorytmu, która została opisana w osobnym artykule.
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.
Algorytm memetyczny – algorytm będący połączeniem algorytmu genetycznego i metod lokalnej optymalizacji. Czasami określany również jako hybrydowy algorytm ewolucyjny.