Algoritmus Ford-Fulkerson - Ford–Fulkerson algorithm
The Ford-Fulkersonova metoda nebo Algoritmus Ford-Fulkerson (FFA) je chamtivý algoritmus který počítá maximální průtok v toková síť. Někdy se tomu říká „metoda“ namísto „algoritmu“, protože přístup k nalezení rozšiřujících cest ve zbytkovém grafu není zcela specifikován[1] nebo je zadán v několika implementacích s různými dobami běhu.[2] To bylo vydáváno v roce 1956 autorem L. R. Ford Jr. a D. R. Fulkerson.[3] Název „Ford – Fulkerson“ se často používá také pro Algoritmus Edmonds – Karp, což je plně definovaná implementace metody Ford – Fulkerson.
Myšlenka algoritmu je následující: pokud existuje cesta ze zdroje (počáteční uzel) do umyvadla (koncový uzel), s dostupnou kapacitou na všech okrajích v cestě, pošleme tok po jedné z cest. Pak najdeme jinou cestu atd. Cesta s dostupnou kapacitou se nazývá rozšiřující cesta.
Algoritmus
Nechat být graf a pro každou hranu z u na proti, nechť být kapacita a být tok. Chceme najít maximální průtok ze zdroje s do umyvadla t. Po každém kroku v algoritmu je zachováno následující:
Omezení kapacity Tok podél okraje nesmí překročit jeho kapacitu. Šikmá symetrie Čistý tok z u na proti musí být opakem čistého toku z proti na u (viz příklad). Zachování toku Čistý tok do uzlu je nulový, s výjimkou zdroje, který „produkuje“ tok, a jímky, která „spotřebovává“ tok. Hodnota (f) Tok odcházející z s se musí rovnat toku, který dorazí k t.
To znamená, že tok sítí je a legální tok po každém kole v algoritmu. Definujeme zbytková síť být sítí s kapacitou a žádný tok. Všimněte si, že se může stát, že tok z proti na u je povolen v reziduální síti, i když je v původní síti zakázán: pokud a pak .
Algoritmus Ford – Fulkerson
- Vstupy Vzhledem k síti s průtokovou kapacitou C, zdrojový uzel sa uzel jímky t
- Výstup Vypočítejte tok F z s na t maximální hodnoty
- pro všechny hrany
- Zatímco tam je cesta str z s na t v , takový, že pro všechny hrany :
- Nalézt
- Pro každou hranu
- (Pošlete tok podél cesty)
- (Tok může být později „vrácen“)
- „←“ označuje úkol. Například, "největší ← položka"znamená, že hodnota největší změny hodnoty položka.
- "vrátit se"ukončí algoritmus a odešle následující hodnotu.
Cestu v kroku 2 lze najít například pomocí a vyhledávání na šířku (BFS) nebo a hloubkové vyhledávání v . Pokud použijete první, je volán algoritmus Edmonds – Karp.
Pokud v kroku 2 nelze najít žádné další cesty, s nebude schopen dosáhnout t ve zbytkové síti. Li S je sada uzlů dosažitelných pomocí s ve zbytkové síti pak celková kapacita v původní síti hran od S do zbývající části PROTI je na jedné straně rovný celkovému toku, ze kterého jsme našli s na t, a na druhé straně slouží jako horní mez pro všechny takové toky. To dokazuje, že tok, který jsme našli, je maximální. Viz také Věta o maximálním toku Min-cut.
Pokud graf má více zdrojů a propadů, jednáme následovně: Předpokládejme, že a . Přidat nový zdroj s hranou z do každého uzlu , s kapacitou . A přidejte nový dřez s hranou z každého uzlu na , s kapacitou . Poté použijte algoritmus Ford – Fulkerson.
Také pokud uzel u má kapacitní omezení , nahradíme tento uzel dvěma uzly a okraj , s kapacitou . Poté použijte algoritmus Ford – Fulkerson.
Složitost
Přidáním cesty ke zvýšení průtoku k toku, který je již stanoven v grafu, bude dosaženo maximálního průtoku, když v grafu již nebude možné najít žádné cesty ke zvýšení průtoku. Neexistuje však jistota, že této situace bude někdy dosaženo, takže nejlepší, co lze zaručit, je, že odpověď bude správná, pokud bude algoritmus ukončen. V případě, že algoritmus běží navždy, tok se nemusí ani sbíhat k maximálnímu toku. K této situaci však dochází pouze při iracionálních hodnotách toku.[Citace je zapotřebí ] Jsou-li kapacity celá čísla, je doba běhu Ford-Fulkerson omezena (vidět velká O notace ), kde je počet hran v grafu a je maximální průtok v grafu. Je to proto, že každou rozšiřující cestu najdete v času a zvyšuje tok alespoň o celé číslo , s horní mezí .
Varianta algoritmu Ford – Fulkerson se zaručeným ukončením a dobou chodu nezávislou na maximální hodnotě toku je Algoritmus Edmonds – Karp, který běží dovnitř čas.
Integrální příklad
Následující příklad ukazuje první kroky Ford-Fulkersona v síti toku se 4 uzly, zdroj a umyvadlo . Tento příklad ukazuje nejhorší chování algoritmu. V každém kroku pouze tok se odesílá přes síť. Pokud by bylo místo toho použito vyhledávání podle šířky, bylo by zapotřebí pouze dvou kroků.
Cesta | Kapacita | Výsledná síť toku |
---|---|---|
Síť počátečního toku | ![]() | |
![]() | ||
![]() | ||
Po roce 1998 další kroky ... | ||
Síť konečného toku | ![]() |
Všimněte si, jak je tok „tlačen zpět“ na při hledání cesty .
Nekončící příklad

Zvažte síť toku zobrazenou vpravo se zdrojem , dřez , kapacity hran , a resp , a a kapacita všech ostatních hran nějaké celé číslo . Konstanta byl vybrán tak, že . Používáme rozšiřující cesty podle následující tabulky, kde , a .
Krok | Zvyšující se cesta | Odeslaný tok | Zbytkové kapacity | ||
---|---|---|---|---|---|
0 | |||||
1 | |||||
2 | |||||
3 | |||||
4 | |||||
5 |
Všimněte si, že po kroku 1 i po kroku 5 jsou zbytkové kapacity hran , a jsou ve formě , a pro některé . To znamená, že můžeme použít rozšiřující cesty , , a nekonečně mnohokrát a zbytkové kapacity těchto okrajů budou vždy ve stejné formě. Celkový tok v síti po kroku 5 je . Pokud budeme i nadále používat rozšiřující cesty, jak je uvedeno výše, celkový tok konverguje k . Všimněte si však, že existuje tok hodnot zasláním jednotky toku podél , 1 jednotka toku , a jednotky toku podél . Algoritmus proto nikdy nekončí a tok se ani nesbližuje s maximálním tokem.[4]
Další nekončící příklad založený na Euklidovský algoritmus darováno Backman & Huynh (2018), kde také ukazují, že nejhorší doba běhu algoritmu Ford-Fulkerson v síti v řadové číslovky je .
Python implementace Edmonds – Karp algoritmus
import sbírkytřída Graf: "" "Tato třída představuje směrovaný graf využívající reprezentaci matice sousedství." "" def __init__(já, graf): já.graf = graf # zbytkový graf já.řádek = len(graf) def bfs(já, s, t, rodič): "" "Vrátí hodnotu true, pokud existuje cesta ze zdroje 'do zdroje' t ' zbytkový graf. Také vyplní nadřazené [] pro uložení cesty. "" " # Označte všechny vrcholy jako nenavštívené navštívil = [Nepravdivé] * já.řádek # Vytvořte frontu pro BFS fronta = sbírky.deque() # Označte zdrojový uzel jako navštívený a zařaďte jej do fronty fronta.připojit(s) navštívil[s] = Skutečný # Standardní smyčka BFS zatímco fronta: u = fronta.popleft() # Získejte všechny přilehlé vrcholy vyřazeného vrcholu u # Pokud sousední nebyl navštíven, označte jej # navštívil a zařadil jej do pořadí pro ind, val v vyjmenovat(já.graf[u]): -li (navštívil[ind] == Nepravdivé) a (val > 0): fronta.připojit(ind) navštívil[ind] = Skutečný rodič[ind] = u # Pokud jsme dosáhli potopení v BFS od zdroje, pak se vraťte # true, else false vrátit se navštívil[t] # Vrátí maximální průtok od s do t v daném grafu def edmonds_karp(já, zdroj, dřez): # Toto pole je vyplněno BFS a pro uložení cesty rodič = [-1] * já.řádek max_flow = 0 # Zpočátku neexistuje žádný tok # Zvyšte tok, když je cesta od zdroje ke dnu zatímco já.bfs(zdroj, dřez, rodič): # Najděte minimální zbytkovou kapacitu okrajů podél # cesta vyplněna BFS. Nebo můžeme říci najít maximální průtok # nalezenou cestou. path_flow = plovák("Inf") s = dřez zatímco s != zdroj: path_flow = min(path_flow, já.graf[rodič[s]][s]) s = rodič[s] # Přidejte tok cesty k celkovému toku max_flow += path_flow # aktualizujte zbytkovou kapacitu okrajů a reverzních okrajů # Podél cesty proti = dřez zatímco proti != zdroj: u = rodič[proti] já.graf[u][proti] -= path_flow já.graf[proti][u] += path_flow proti = rodič[proti] vrátit se max_flow
Viz také
Poznámky
- ^ Laung-Terng Wang, Yao-Wen Chang, Kwang-Ting (Tim) Cheng (2009). Elektronická automatizace designu: syntéza, ověření a testování. Morgan Kaufmann. str.204. ISBN 0080922007.CS1 maint: více jmen: seznam autorů (odkaz)
- ^ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Úvod do algoritmů. MIT Stiskněte. str.714. ISBN 0262258102.
- ^ Ford, L. R.; Fulkerson, D. R. (1956). „Maximální tok sítí“ (PDF). Kanadský žurnál matematiky. 8: 399–404. doi:10.4153 / CJM-1956-045-5.
- ^ Zwick, Uri (21. srpna 1995). "Nejmenší sítě, u kterých může selhat ukončení postupu maximálního toku Ford-Fulkerson". Teoretická informatika. 148 (1): 165–170. doi:10.1016 / 0304-3975 (95) 00022-O.
Reference
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). „Oddíl 26.2: Metoda Ford – Fulkerson“. Úvod do algoritmů (Druhé vydání.). MIT Press a McGraw – Hill. str. 651–664. ISBN 0-262-03293-7.
- George T. Heineman; Gary Pollice; Stanley Selkow (2008). "Kapitola 8: Algoritmy toku v síti". Algoritmy v kostce. Oreilly Media. str. 226–250. ISBN 978-0-596-51624-6.
- Jon Kleinberg; Éva Tardos (2006). „Kapitola 7: Rozšíření problému maximálního toku“. Návrh algoritmu. Pearson Education. str.378–384. ISBN 0-321-29535-8.
- Samuel Gutekunst (2009). ENGRI 1101. Cornell University.
- Backman, Spencer; Huynh, Tony (2018). „Transfinitní Ford – Fulkerson v konečné síti“. Vyčíslitelnost. 7 (4): 341–347. arXiv:1504.04363. doi:10.3233 / COM-180082.
externí odkazy
- Výukový program vysvětlující metodu Ford-Fulkerson k vyřešení problému s maximálním průtokem
- Další animace Java
- Java Web Start aplikace
Média související s Ford-Fulkersonův algoritmus na Wikimedia Commons