Algorytm Edmondsa-Karpa
(1) Animacja pokazująca przykładowe wykonanie algorytmu. W sieci przepływowej wartość przed ukośnikiem oznacza aktualny przepływ, a wartość po ukośniku – przepływ maksymalny. Ścieżka powiększająca oznaczana jest na pomarańczowo
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.
Pojęcia
Aby zrozumieć algorytm Edmondsa-Karpa (i ogólnie metodę Forda-Fulkersona) konieczna jest znajomość następujących pojęć:
- Sieć residualna – graf skierowany, w którym każdy łuk (krawędź skierowana) informuje, o ile można zmienić (zwiększyć bądź zmniejszyć) przepływ w danym łuku sieci przepływowej. Przykład: załóżmy, że w sieci przepływowej mamy łuk prowadzący z wierzchołka A do wierzchołka B o przepustowości 5, przy czym aktualnie wykorzystujemy przepustowość 2. Zakładamy też, że sieć nie zawiera łuku prowadzącego z B do A. W takim przypadku sieć residualna będzie zawierała łuk prowadzący z A do B o wartości 3 (o tyle możemy zwiększyć przepływ) oraz łuk prowadzący z B do A o wartości 2 (o tyle możemy zmniejszyć przepływ).
- Ścieżka powiększająca – ścieżka prosta (tzn. nie przechodząca wielokrotnie przez ten sam wierzchołek) w sieci residualnej prowadząca od źródła do ujścia.
- Przepustowość residualna ścieżki powiększającej – maksymalna wartość, o którą możemy zwiększyć przepływ na ścieżce powiększającej. Jest ona równa najmniejszej spośród wag łuków należących do ścieżki powiększającej.
Przebieg algorytmu
Algorytm ten przebiega w następująco:
- Tworzymy sieć residualną,
- Wyznaczamy ścieżkę powiększającą w sieci residualnej przeszukując ją wszerz,
- Jeśli nie da się wyznaczyć żadnej ścieżki powiększającej, kończymy działanie algorytmu. W przeciwnym razie modyfikujemy przepływ w sieci przepływowej o wartość residualną ścieżki powiększającej.
Złożoność czasowa algorytmu
Wyznaczenie ścieżki za pomocą przeszukiwania wszerz ma złożoność O(e) (e jest liczbą krawędzi). Liczba wykonań głównej pętli algorytmu jest rzędu O(ne) (n jest liczbą wierzchołków). Złożoność czasowa algorytmu Edmondsa-Karpa wynosi zatem O(ne2). Wyprowadzenie tych wartości można znaleźć w książce Wprowadzenie do algorytmów.
Bibliografia
- T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, Warszawa, 2012.
- A. Debudaj-Grabysz, S. Deorowicz, J. Widuch, Algorytmy i struktury danych. Wybór zaawansowanych metod, Wydawnictwo Politechniki Śląskiej, Gliwice, 2012
Liczba głosów: 0.
- Algorytm Edmondsa-Karpa
- Metoda Forda-Fulkersona
- Metoda z zastosowaniem przepływu blokującego
Dodano: 22 listopada 2017 18:04, ostatnia edycja: 12 grudnia 2017 15:57.
Zobacz też
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.
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.
Zanieczyszczenie Giniego (ang. Gini Impurity) – miara niejednorodności danego zbioru wyrażająca się wzorem:
$$G = ∑↙{n} p_n (1-p_n),$$gdzie pn jest prawdopodobieństwem przynależności elementu do klasy n, czyli liczbą elementów danej klasy podzieloną przez liczbę elementów całego zbioru. Jeśli wszystkie elementy zbioru należą do tej samej klasy, zanieczyszczenie Giniego jest równe 0.
Zanieczyszczenia Giniego nie należy mylić ze współczynnikiem Giniego. Są to miary służące do wyrażania zupełnie innych rzeczy. Współczynnik Giniego określa nierównomierność rozkładu i jest wykorzystywany między innymi do liczbowego wyrażania nierówności w dochodach danego społeczeństwa.