Algorytm Dinica - Dinic's algorithm

Algorytm Dinica lub algorytm Dinitza to silnie wielomianowy algorytm do obliczania maksymalnego przepływu w sieci przepływowej , wymyślony w 1970 roku przez izraelskiego (dawniej sowieckiego) informatyka Jefima (Chaima) A. Dinitza. Algorytm działa w czasie i jest podobny do algorytmu Edmondsa-Karpa , który działa w czasie, ponieważ używa najkrótszych ścieżek rozszerzających. Wprowadzenie pojęć grafu poziomu i przepływu blokującego umożliwia algorytmowi Dinica osiągnięcie odpowiedniej wydajności. ${\ Displaystyle O (V ^ {2} E)}$${\ Displaystyle O (VE ^ {2})}$

Historia

Yefim Dinitz wynalazł ten algorytm w odpowiedzi na przedklasowe ćwiczenie w klasie algorytmów Adelsona-Velsky'ego . Nie znał wówczas podstawowych faktów dotyczących algorytmu Forda-Fulkersona .

Dinitz wspomina o wynalezieniu swojego algorytmu w styczniu 1969 roku, który został opublikowany w 1970 roku w czasopiśmie Doklady Akademii Nauk SSSR . W 1974 roku Shimon Even i (jego ówczesny doktorant) Alon Itai z Technion w Hajfie byli bardzo ciekawi i zaintrygowani algorytmem Dinitza, a także powiązanym z nim pomysłem Aleksandra V. Karzanowa o blokowaniu przepływu. Trudno było im jednak rozszyfrować te dwa dokumenty, z których każdy był ograniczony do czterech stron, aby spełnić wymogi czasopisma Doklady Akademii Nauk SSSR . Nawet się nie poddał i po trzech dniach wysiłku zdołał zrozumieć oba artykuły, z wyjątkiem kwestii konserwacji sieci warstwowej. Przez kilka następnych lat Even prowadził wykłady na temat „Algorytmu Dinica”, błędnie wymawiając nazwisko autora podczas jego popularyzacji. Even i Itai również przyczynili się do tego algorytmu, łącząc BFS i DFS , w ten sposób algorytm jest obecnie powszechnie prezentowany.

Przez około 10 lat po wynalezieniu algorytmu Forda-Fulkersona nie było wiadomo, czy można go zakończyć w czasie wielomianowym w ogólnym przypadku niewymiernych możliwości krawędziowych. Spowodowało to brak jakiegokolwiek znanego algorytmu wielomianowego do rozwiązania problemu maksymalnego przepływu w ogólnych przypadkach. Zarówno algorytm Dinitza, jak i algorytm Edmondsa-Karpa (opublikowany w 1972 r.) niezależnie wykazały, że w algorytmie Forda-Fulkersona, jeśli każda ścieżka rozszerzająca jest najkrótsza, to długość ścieżek rozszerzających nie maleje, a algorytm zawsze się kończy.

Definicja

Niech być siecią z i pojemność i przepływ krawędzi , odpowiednio. ${\ Displaystyle G = ((V, E), c, f, s, t)}$${\displaystyle c(u,v)}$${\displaystyle f(u,v)}$${\displaystyle (u,v)}$

Pojemności resztkowej jest odwzorowaniem zdefiniowane jak ${\ Displaystyle C_ {f} \ dwukropek V \ razy V \ do R ^ {+}}$

1. jeśli , ${\ Displaystyle (u, v) \ w E}$

   ${\ Displaystyle C_ {f} (u, v) = c (u, v)-f (u, v)}$

2. ${\ Displaystyle C_ {f} (u, v) = 0}$ Inaczej.

Pozostały wykres jest nieważony wykres , w którym ${\ Displaystyle G_ {f} = ((V, E_ {f}), c_ {f} | _ {E_ {f}}, s, t)}$

${\ Displaystyle E_ {f} = \ {(u, v) \ w V \ razy V \ dwukropek \; c_ {f} (u, v)> 0 \}}$.

Zwiększając ścieżka jest - droga w resztkowym wykresie .${\displaystyle s}$${\displaystyle t}$${\ Displaystyle G_ {f}}$

Zdefiniuj długość najkrótszej ścieżki od do in . Następnie wykres poziomu od jest wykres , w którym ${\ Displaystyle \ operatorname {odleg} (v)}$${\displaystyle s}$${\displaystyle v}$${\ Displaystyle G_ {f}}$${\ Displaystyle G_ {f}}$${\ Displaystyle G_ {L} = ((V, E_ {L}), c_ {f} | _ {E_ {L}}, s, t)}$

${\ Displaystyle E_ {L} = \ {(u, v) \ w E_ {f} \ dwukropek \; \ operatorname {odleg} (v) = \ operatorname {odleg} (u) + 1 \}}$.

Blokowania przepływu jest - przepływ tak, że wykres z nie zawiera - ścieżki.${\displaystyle s}$${\displaystyle t}$${\displaystyle f'}$${\ Displaystyle G '= ((V, E_ {L} '), s, t)}$${\ Displaystyle E_ {L} '= \ {(u, v) \ dwukropek \; f '(u, v) <c_ {f} | _ {e_ {L}} (u, v) \}}$${\displaystyle s}$${\displaystyle t}$

Algorytm

Algorytm Dinica

Wejście : Sieć .${\ Displaystyle G = ((V, E), c, s, t)}$

Wyjście : An – przepływ o wartości maksymalnej.${\displaystyle s}$${\displaystyle t}$${\displaystyle f}$

1. Zestaw dla każdego .${\ Displaystyle f (e) = 0}$${\displaystyle e\w e}$
2. Skonstruować z o . Jeśli , zatrzymaj się i wyślij .${\ Displaystyle G_ {L}}$${\ Displaystyle G_ {f}}$${\ Displaystyle G}$${\ Displaystyle \ operatorname {odleg} (t) = \ infty}$${\displaystyle f}$
3. Znajdź blokujący przepływ w .${\displaystyle f'}$${\ Displaystyle G_ {L}}$
4. Dodaj przepływ augment przez i wróć do kroku 2.${\displaystyle f}$${\displaystyle f'}$

Analiza

Można wykazać, że liczba warstw w każdym przepływie blokującym wzrasta za każdym razem o co najmniej 1, a zatem w algorytmie występują co najwyżej przepływy blokujące. Dla każdego z nich: ${\displaystyle |V|-1}$

• wykres poziomu może być skonstruowany przez wyszukiwanie wszerz w czasie${\ Displaystyle G_ {L}}$${\ Displaystyle O(E)}$
• blokujący przepływ na wykresie poziomu można znaleźć w czasie${\ Displaystyle G_ {L}}$${\ Displaystyle O(VE)}$

z całkowitym czasem działania dla każdej warstwy. W konsekwencji czas działania algorytmu Dinica wynosi . ${\ Displaystyle O (E + VE) = O (VE)}$${\ Displaystyle O (V ^ {2} E)}$

Stosując strukturę danych zwaną dynamicznymi drzewami , czas znajdowania przepływu blokującego w każdej fazie można skrócić do, a zatem czas działania algorytmu Dinic można poprawić do . ${\ Displaystyle O (E \ log V)}$${\ Displaystyle O (VE \ log V)}$

Przypadki specjalne

W sieciach o pojemnościach jednostkowych obowiązuje znacznie silniejsza granica czasu. Każdy przepływ blokujący można znaleźć w czasie i można wykazać, że liczba faz nie przekracza i . W ten sposób algorytm działa w czasie. ${\ Displaystyle O(E)}$${\ Displaystyle O ({\ sqrt {E}})}$${\ Displaystyle O (V ^ {2/3})}$${\ Displaystyle O (\ min \ {V ^ {2/3}, E ^ {1/2} \} E)}$

W sieciach, które wynikają z problemu dopasowania dwudzielnego , liczba faz jest ograniczona przez , co prowadzi do ograniczenia czasowego. Powstały algorytm jest również znany jako algorytm Hopcrofta-Karpa . Mówiąc bardziej ogólnie, to ograniczenie obowiązuje dla dowolnej sieci jednostkowej — sieci, w której każdy wierzchołek, z wyjątkiem źródła i ujścia, ma albo pojedynczą wchodzącą krawędź pojemności 1, albo pojedynczą krawędź wychodzącą pojemności 1, a wszystkie inne pojemności są arbitralnymi liczbami całkowitymi . ${\ Displaystyle O ({\ sqrt {V}})}$${\ Displaystyle O ({\ sqrt {V}} E)}$

Przykład

Poniżej znajduje się symulacja algorytmu Dinica. Na wykresie poziomu wierzchołki z etykietami w kolorze czerwonym są wartościami . Ścieżki w kolorze niebieskim tworzą przepływ blokujący. ${\ Displaystyle G_ {L}}$${\ Displaystyle \ operatorname {odleg} (v)}$

	${\ Displaystyle G}$	${\ Displaystyle G_ {f}}$	${\ Displaystyle G_ {L}}$
1.
	Przepływ blokujący składa się z ${\displaystyle \{s,1,3,t\}}$ z 4 jednostkami przepływu, ${\displaystyle \{s,1,4,t\}}$ z 6 jednostkami przepływu i ${\displaystyle \{s,2,4,t\}}$ z 4 jednostkami przepływu. Dlatego przepływ blokujący wynosi 14 jednostek, a wartość przepływu wynosi 14. Należy zauważyć, że każda ścieżka zwiększająca się w przepływie blokującym ma 3 krawędzie. ${\displaystyle |f|}$
2.
	Przepływ blokujący składa się z ${\displaystyle \{s,2,4,3,t\}}$ z 5 jednostkami przepływu. Dlatego przepływ blokujący wynosi 5 jednostek, a wartość przepływu wynosi 14 + 5 = 19. Zauważ, że każda ścieżka rozszerzająca ma 4 krawędzie. ${\displaystyle |f|}$
3.
	Ponieważ nie można osiągnąć w , algorytm kończy działanie i zwraca przepływ o maksymalnej wartości 19. Należy zauważyć, że w każdym przepływie blokującym liczba krawędzi w ścieżce rozszerzającej wzrasta o co najmniej 1. ${\displaystyle t}$${\ Displaystyle G_ {f}}$

Zobacz też

• Algorytm Forda-Fulkersona
• Problem z maksymalnym przepływem

Uwagi

Bibliografia

• Jefima Dinitza (2006). „Dinitz” Algorytm: oryginalną wersję, a nawet jest wersja” (PDF) . W Oded Goldreich ; Arnold L. Rosenberg; Alan L. Selman (red.). Informatyka teoretyczna: Eseje ku pamięci Shimona Evena . Skoczek. s. 218–240. Numer ISBN 978-3-540-32880-3.
• Tarjan, RE (1983). Struktury danych i algorytmy sieciowe .
• BH Korte; Jensa Vygena (2008). „8.4 Blokowanie przepływów i algorytm Fujishige” . Optymalizacja kombinatoryczna: teoria i algorytmy (Algorytmy i kombinatoryka, 21) . Springer Berlin Heidelberg. s. 174–176. Numer ISBN 978-3-540-71844-4.