Algorytm Forda-Fulkersona

Metoda Forda-Fulkersona lub algorytm Forda-Fulkersona ( FFA ) to zachłanny algorytm , który oblicza maksymalny przepływ w sieci przepływów . Czasami nazywa się to „metodą” zamiast „algorytmem”, ponieważ podejście do znajdowania ścieżek rozszerzających na wykresie resztkowym nie jest w pełni określone lub jest określone w kilku implementacjach o różnych czasach działania. Został opublikowany w 1956 roku przez LR Forda Jr. i DR Fulkersona . Nazwa „Ford – Fulkerson” jest również często używana w odniesieniu do algorytmu Edmondsa – Karpa , który jest w pełni zdefiniowaną implementacją metody Forda – Fulkersona.

Idea algorytmu jest następująca: dopóki istnieje ścieżka od źródła (węzeł startowy) do ujścia (węzeł końcowy), z dostępną przepustowością na wszystkich krawędziach ścieżki, wysyłamy przepływ wzdłuż jednej ze ścieżek. Następnie znajdujemy inną ścieżkę i tak dalej. Ścieżka z dostępną pojemnością jest nazywana ścieżką rozszerzającą .

Algorytm

Niech $v)}$ $wykresem$ i dla każdej krawędzi od $do$ v $,$ niech do i być przepływem ${\ Displaystyle f (u, v)} .$ Chcemy znaleźć maksymalny przepływ od źródła $s$ do ujścia $t$ . Po każdym kroku algorytmu zachowywane są:

Ograniczenia pojemności	${\ Displaystyle \ forall (u, v) \ w E: \ f (u, v) \ równoważnik c (u, v) )}$	Przepływ wzdłuż krawędzi nie może przekroczyć jej wydajności.
Symetria skośna	${\ Displaystyle \ forall (u, v) \ w E: \ f (u, v) = - f (v, u)}$	Przepływ netto od $u$ do $v$ musi być przeciwieństwem przepływu netto od $v$ do $u$ (patrz przykład).
Zachowanie przepływu	${\ Displaystyle \ forall u \ in V: u \ neq s {\ tekst {i}} u \ neq t \ Strzałka w prawo \sum _{w\in V}f(u,w)=0}$	Przepływ netto do węzła wynosi zero, z wyjątkiem źródła, które „wytwarza” przepływ, oraz ujścia, które „konsumuje” przepływ.
Wartość (f)	${\ Displaystyle \ suma _ {(s, u) \ w mi} f (s, u )=\suma _{(v,t)\in E}f(v,t)}$	Przepływ wychodzący z $s$ musi być równy przepływowi docierającemu do $t$ .

Oznacza to, że przepływ przez sieć jest legalnym przepływem po każdej rundzie w algorytmie. $)$ rezydualną definiujemy ${\ Displaystyle c_ {f} (u, v) = c (u, v) -f (u, v)}$ sieć i brak przepływu. Zauważ, że może się zdarzyć, że przepływ z $v$ do $u$ jest dozwolony w sieci rezydualnej, chociaż zabroniony w sieci oryginalnej: if ${\ Displaystyle f (u, v)> 0}$ i $u) = 0}$ wtedy do ${\ Displaystyle c_ {f} (v, u) = c (v, u) -f (v, u) = f (u, v)> 0}$ .

 Algorytm  Forda-Fulkersona

Wejścia Biorąc pod uwagę sieć o przepustowości

c

, węźle źródłowym

s

i węźle ujścia t

sol

\ Displaystyle G = (V, E)}

Wyjście Oblicz przepływ

f

od

s

do

t

o maksymalnej wartości

${\ Displaystyle f (u, v) \ strzałka w lewo 0}$ dla wszystkich krawędzi ${\ Displaystyle (u, v)}$
Chociaż istnieje ścieżka p od s do t w , taka, że $>$ $G_{f}$ wszystkich krawędzi $\ Displaystyle c_ {f} (u, v)>$ $c_{f}(u,v)>0$ $(u,v)\in p$ $(u,v)\in p$ :
1. Znajdź do $v): (u,v)\w p\}}$
2. dla każdej krawędzi ${\ Displaystyle (u, v) \ w p}$ $(u,v)\in p$
  1. ${\ Displaystyle f (u, v) \ strzałka w lewo f (u, v) + c_ {f} (p)} ($ Wyślij przepływ wzdłuż ścieżka )
  2. ${\ Displaystyle f (v, u) \ leftarrow f (v, u) -c_ {f} (p)}$ ( Przepływ może być „powrócił” później )

„←” oznacza przypisanie . Na przykład „ największy ← przedmiot ” oznacza, że wartość największego zmienia się na wartość elementu .
„ return ” kończy działanie algorytmu i wyświetla następującą wartość.

Ścieżkę w kroku 2 można znaleźć na przykład za pomocą przeszukiwania wszerz (BFS) lub przeszukiwania w głąb w sol fa $Displaystyle G_ {f} (V, E_ {f} )}$ . Jeśli użyjesz pierwszego, algorytm nazywa się Edmonds-Karp .

Kiedy nie można znaleźć więcej ścieżek w kroku 2, $s$ nie będzie w stanie dotrzeć do $t$ w sieci rezydualnej. Jeśli $S$ jest zbiorem węzłów osiągalnych przez $s$ w sieci rezydualnej, to całkowita przepustowość w pierwotnej sieci krawędzi od $S$ do reszty $V$ jest z jednej strony równa całkowitemu przepływowi, który znaleźliśmy od $s$ do $t$ , oraz z drugiej strony służy jako górna granica dla wszystkich takich przepływów. Dowodzi to, że przepływ, który znaleźliśmy, jest maksymalny. Zobacz także Twierdzenie o maksymalnym przepływie i minimalnym cięciu .

Jeśli wykres $T$ $\ mid t {\ tekst {jest zlewem}} \}}$ Załóżmy, że ${\ Displaystyle T = \$ i ${\ Displaystyle S = \ {s \ mid s {\ tekst {jest źródłem}} \}}$ . Dodaj nowe źródło z krawędzią. ${\ displaystyle s ^ {*}}$ ${\ Displaystyle (s ^ {*}, s)}$ od ${\ Displaystyle s ^ {*}}$ do każdego węzła ${\ Displaystyle s \ w S}$ o pojemności ${\ Displaystyle c (s ^ {*}, s) = d_ {s} = \ suma _ {(s, u) \ w E} c (s, u)}$ . I $T}$ nowy zlew z krawędzią ${\ Displaystyle (t, t ^ {*})}$ $t$ z każdego węzła $\ Displaystyle t \$ do ${\ Displaystyle t ^ {*}}$ , z pojemnością $\ Displaystyle c (t, t ^ {*}) = d_ {t} = \ suma _ {(v, t) \ w E} c (v, t)}$ . Następnie zastosuj algorytm Forda-Fulkersona.

${w}}, u_ {\ mathrm {na zewnątrz}}}$ jeśli węzeł $u$ $\$ ograniczenie przepustowości , zastępujemy ten węzeł dwoma węzłami i krawędź ${\ Displaystyle (u _ {\ operatorname {w}}, u _ {\ operatorname {na zewnątrz}})}$ o pojemności ${\ Displaystyle c (u _ {\ operatorname {w}}, u _ {\ operatorname {na zewnątrz}}) = d_ {u}}$ . Następnie zastosuj algorytm Forda-Fulkersona.

Złożoność

Dodając ścieżkę zwiększania przepływu do przepływu już ustalonego na wykresie, maksymalny przepływ zostanie osiągnięty, gdy na wykresie nie będzie już można znaleźć ścieżek zwiększania przepływu. Jednak nie ma pewności, że ta sytuacja kiedykolwiek zostanie osiągnięta, więc najlepsze, co można zagwarantować, to to, że odpowiedź będzie poprawna, jeśli algorytm się zakończy. W przypadku, gdy algorytm działa w nieskończoność, przepływ może nawet nie zbliżać się do przepływu maksymalnego. Taka sytuacja występuje jednak tylko przy nieracjonalnych wartościach przepływu. Gdy pojemności są liczbami całkowitymi, czas pracy Forda-Fulkersona jest ograniczony przez ${\ Displaystyle O (Ef)}$ (patrz $notacja$ dużego O ), gdzie jest $wykresie$ krawędzi na wykresie, a maksymalnym przepływem na Dzieje się tak, ponieważ każdą ścieżkę zwiększającą można znaleźć w czasie i zwiększa przepływ o liczbę całkowitą wynoszącą co najmniej $Displaystyle$ $1}$ górną granicą $}$ ${\ displaystyle f$ .

Odmianą algorytmu Forda-Fulkersona z gwarantowanym zakończeniem i czasem działania niezależnym od maksymalnej wartości przepływu jest $-$ działa w .

Przykład integralny

$przykład$ pokazuje pierwsze kroki Forda-Fulkersona w sieci przepływowej z 4 węzłami $,$ i . Ten przykład pokazuje zachowanie algorytmu w najgorszym przypadku. przez sieć przesyłany jest $strumień$ . Gdyby zamiast tego zastosowano przeszukiwanie wszerz, potrzebne byłyby tylko dwa kroki.

Ścieżka	Pojemność	Wynikowa sieć przepływów
Początkowa sieć przepływu
${\ Displaystyle A, B, C, D}$	${\ Displaystyle {\ rozpocząć {wyrównane} i \ min (c_ {f} ( A,B),c_{f}(B,C),c_{f}(C,D))\\={}&\min(c(A,B)-f(A,B),c( B,C)-f(B,C),c(C,D)-f(C,D))\\={}&\min(1000-0,1-0,1000-0)=1\ koniec {wyrównany}}}$
${\ Displaystyle A, C, B, D}$	${\ Displaystyle {\ rozpocząć {wyrównane} i \ min (c_ { f}(A,C),c_{f}(C,B),c_{f}(B,D))\\={}&\min(c(A,C)-f(A,C) ,c(C,B)-f(C,B),c(B,D)-f(B,D))\\={}&\min(1000-0,0-(-1),1000 -0)=1\end{wyrównane}}}$
Po 1998 kolejne kroki...
Sieć finalna

$B$ $uwagę,$ jest „cofany” z { displaystyle $}$ ścieżki

Niekończący się przykład

Rozważmy sieć przepływów pokazaną po prawej stronie, ze źródłem ${\ displaystyle$ zlew $t}$ , pojemnościami krawędzi ${\ displaystyle e_ {1}}$ , ${\ displaystyle e_ {2}}$ mi ${\ Displaystyle e_ {3}}$ odpowiednio ${\ Displaystyle 1}$ , ${\ Displaystyle R = ({\ sqrt {5}} -1) / 2$ i ${\ Displaystyle 1}$ i pojemność wszystkich innych krawędzi niektóre liczby całkowite ${\ Displaystyle M \ geq 2}$ . Stała została wybrana tak, że $r$ ${\ displaystyle r ^ {2} = 1-$ } Używamy ścieżek rozszerzających zgodnie z poniższą tabelą, gdzie ${\ Displaystyle p_ {1} = \ {s, v_ {4}, v_ {3}, v_ {2}, v_ {1}, t \}}$ , ${\ Displaystyle p_ {2} = \ {s, v_ {2}, v_ {3}, v_ {4}, t \}}$ i ${\ Displaystyle p_ {3} = \ {s, v_ {1}, v_ {2}, v_ {3}, t \}}$ .

Krok	Ścieżka powiększająca	Wysłany strumień	Pojemność resztkowa
Krok	Ścieżka powiększająca	Wysłany strumień	${\ displaystyle e_ {1}}$	${\ displaystyle e_ {2}}$	${\ displaystyle e_ {3}}$
0			${\ displaystyle r ^ {0} = 1}$	${\ displaystyle r}$	${\ Displaystyle 1}$
1	${\ Displaystyle \ {s, v_ {2}, v_ {3}, t \}}$	${\ Displaystyle 1}$	${\ displaystyle r ^ {0}}$	${\ displaystyle r ^ {1}}$	${\ styl wyświetlania 0}$
2	${\ displaystyle p_ {1}}$	${\ displaystyle r ^ {1}}$	${\ displaystyle r ^ {2}}$	${\ styl wyświetlania 0}$	${\ displaystyle r ^ {1}}$
3	${\ displaystyle p_ {2}}$	${\ displaystyle r ^ {1}}$	${\ displaystyle r ^ {2}}$	${\ displaystyle r ^ {1}}$	${\ styl wyświetlania 0}$
4	${\ displaystyle p_ {1}}$	${\ displaystyle r ^ {2}}$	${\ styl wyświetlania 0}$	${\ displaystyle r ^ {3}}$	${\ displaystyle r ^ {2}}$
5	${\ displaystyle p_ {3}}$	${\ displaystyle r ^ {2}}$	${\ displaystyle r ^ {2}}$	${\ displaystyle r ^ {3}}$	${\ styl wyświetlania 0}$

Należy zauważyć, że zarówno po kroku 1, jak i po kroku 5, resztkowe pojemności krawędzi mi $\ displaystyle e_ {1}}$ , ${\ displaystyle e_ {2}}$ i ${\ displaystyle e_ {3}}$ w postaci odpowiednio ${\ displaystyle r ^ {n}}$ , ${\ displaystyle r ^ {n + 1}}$ i ${\ displaystyle 0}$ przez pewien ${\ displaystyle n \ w \mathbb {N} }$ . Oznacza to, że możemy użyć ścieżek rozszerzających ${\ displaystyle p_ {1}}$ , ${\ displaystyle p_ {2}}$ , ${\ displaystyle p_ {1}}$ i ${\ displaystyle p_ {3} }$ nieskończenie wiele razy, a pojemności resztkowe tych krawędzi będą zawsze w tej samej postaci. Całkowity przepływ w sieci po kroku 5 wynosi ${\ Displaystyle 1 + 2 (r ^ {1} + r ^ {2})}$ . Jeśli nadal będziemy używać ścieżek rozszerzających jak powyżej, całkowity przepływ zbiegnie się do ${\ Displaystyle \ textstyle 1 + 2 \ suma _ {i = 1} ^ {\ infty }r^{i}=3+2r}$ . $Należy jednak$ $Displaystyle$ przepływ wartości , wysyłając jednostki przepływu wzdłuż $sv_ {1} t}$ , 1 jednostka przepływu wzdłuż $Displaystyle sv_$ przepływu wzdłuż ${3}$ $\$ v_ . Dlatego algorytm nigdy się nie kończy, a przepływ nawet nie zbliża się do maksymalnego przepływu.

Inny niekończący się przykład oparty na algorytmie euklidesowym podaje Backman & Huynh (2018) , gdzie pokazują również, że najgorszy przypadek czasu działania algorytmu Forda-Fulkersona w sieci ${\ Displaystyle G (V, E)}$ w liczbach porządkowych to ${\ Displaystyle \ omega ^ {\ Theta (| E |)}}$ .

Implementacja algorytmu Edmondsa-Karpa w języku Python

 


 
    




      
            
          

        import  collections  class  Graph  :  """  Ta klasa reprezentuje graf skierowany przy użyciu  reprezentacji macierzy sąsiedztwa.  """  def  __init__  (  self  ,  graph  ):  self  .  graph  =  graph  # resztkowy wykres  self  .  wiersz  =  len  (  wykres  )  def  bfs  (  self  ,  s  ,  t  
        





        
            

        
          

        
         ,  parent  ):  """  Zwraca true, jeśli istnieje ścieżka od  źródła "s" do ujścia "t" w resztkowym grafie.  Wypełnia również parent[], aby zapisać ścieżkę.  """  # Zaznacz wszystkie wierzchołki jako  nieodwiedzone  =  [  Fałsz  ]  *  jaźń  .  wiersz  # Utwórz kolejkę dla  kolejki BFS   =  kolekcje  .  deque  ()  # Zaznacz węzeł źródłowy jako odwiedzony i umieść go  w kolejce 
          

        
         
              

            
            
            
                
                 .  append  (  s  )  odwiedzono  [  s  ]  =  Prawda  # Standardowa pętla BFS  while  kolejka  :  u  =  kolejka  .  popleft  ()  # Pobierz wszystkie sąsiednie wierzchołki usuniętego z kolejki u  # Jeśli sąsiad nie został odwiedzony, zaznacz go  # odwiedzono i dodaj do kolejki  dla  ind  ,  val  in  enumerate  (  self  .  graph  [  u  ]):  if        0
                    
                      
                      

        
        
          (  odwiedzone  [  ind  ]  ==  False  )  i  (  val  >  ):  kolejka  .  append  (  ind  )  odwiedziliśmy  [  ind  ]  =  Prawdziwy  rodzic  [  ind  ]  =  u  # Jeśli osiągnęliśmy ujście w BFS zaczynając od źródła, zwróć  # prawda, w przeciwnym razie  zwróć  odwiedzone  [  t  ] 

    
       
        
            

          0  

        
           # Zwraca maksymalny przepływ od s do t w danym grafie  def  edmonds_karp  (  self  ,  source  ,  sink  ):  # Ta tablica jest wypełniana przez BFS i do przechowywania ścieżki  parent  =  [  -  1  ]  *  self  .  row  max_flow  =  # Na początku nie ma przepływu  # Zwiększ przepływ , dopóki istnieje ścieżka od źródła do ujścia ,  podczas gdy  self  .  bfs  (  źródło  ,  ujście  ,  
            
            
            
              
              
               
                   
                  parent  ):  # Znajdź minimalną pojemność resztkową krawędzi wzdłuż  # ścieżki wypełnionej przez BFS. Lub możemy powiedzieć, znajdź maksymalny przepływ   # przez znalezioną ścieżkę.  path_flow  =  float  (  "Inf"  )  s  =  sink  while  s  !=  source  :  path_flow  =  min  (  path_flow  ,  self  .  graph  [  rodzic  [  s  ]][  s  ])  s  =  

            
              

            
            
              
               
                  
                  
                 parent  [  s  ]  # Dodaj przepływ ścieżki do ogólnego przepływu  max_flow  +=  path_flow  # zaktualizuj resztkowe pojemności krawędzi i odwróć krawędzie  # wzdłuż ścieżki  v  =  sink  while  v  !=  source  :  u  =  parent  [  v  ]  self  .  graph  [  u  ][  v  ]  -=  ścieżka_przepływu  siebie  .  wykres  [  v  ][  u   
                  

          ]  +=  ścieżka_przepływu  v  =  rodzic  [  v  ]  powrót  maks_przepływu

Zobacz też

Notatki

Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). „Sekcja 26.2: Metoda Forda-Fulkersona”. Wprowadzenie do algorytmów (wyd. Drugie). MIT Press i McGraw-Hill. s. 651–664. ISBN 0-262-03293-7 .
George'a T. Heinemana; Gary'ego Pollice'a; Stanleya Selkowa (2008). „Rozdział 8: Algorytmy przepływu w sieci” . Algorytmy w pigułce . Oreilly Media . s. 226–250. ISBN 978-0-596-51624-6 .
Jona Kleinberga ; Eva Tardos (2006). „Rozdział 7: Rozszerzenia problemu maksymalnego przepływu” . Projektowanie algorytmów . Edukacja Pearsona. s. 378–384 . ISBN 0-321-29535-8 .
Samuela Gutekunsta (2009). ENGRI 1101 . Uniwersytet Cornella.
Backman, Spencer; Huynh, Tony (2018). „Transfinite Ford – Fulkerson w skończonej sieci”. Obliczalność . 7 (4): 341–347. ar Xiv : 1504.04363 . doi : 10.3233/COM-180082 . S2CID 15497138 .

Linki zewnętrzne

Media związane z algorytmem Forda-Fulkersona w Wikimedia Commons