Problém s maximálním průtokem

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 29. září 2020; kontroly vyžadují 11 úprav .

V teorii optimalizace a teorii grafů je problémem maximálního toku najít takový tok transportní sítí , aby součet toků ze zdroje, nebo ekvivalentně, součet toků do jímky, byl maximální.

Problém maximálního průtoku je zvláštní případ složitějších problémů, jako je problém s cirkulací .

Historie

Po vstupu USA do druhé světové války v roce 1941 se matematik George Bernard Dantzig připojil ke statistickému úřadu letectva Spojených států ve Washingtonu DC . Od roku 1941 do roku 1946 vedl oddělení bojových analýz, kde pracoval na různých matematických problémech. [1] [2] Následně s využitím práce Danziga byl problém maximálního průtoku poprvé vyřešen při přípravě leteckého mostu během blokády Západního Berlína , která probíhala v letech 1948-1949. [3] [4] [5]

V roce 1951 George Dantzig poprvé formuloval problém obecně. [6]

V roce 1955 Lester Ford a Delbert Ray Fulkerson poprvé vytvořili algoritmus speciálně navržený k vyřešení tohoto problému . Jejich algoritmus se jmenoval Ford-Fulkersonův algoritmus . [7] [8]

V budoucnu bylo řešení problému mnohokrát vylepšeno.

V roce 2010 výzkumníci Jonathan Kelner a Aleksander Mądry z MIT spolu se svými kolegy Danielem Spielmanem z Yale University a Shen -Hua Teng z South The University of California poprvé po 10 letech prokázali další vylepšení algoritmu. [3] [9] [10]

Definice

Daná dopravní síť se zdrojem , jímkou a kapacitou . $N=(V,E)$ $s\in V$ $t\in V$ $c$

Hodnota průtoku je součtem průtoků ze zdroje . V článku " Dopravní síť " je dokázáno , že se rovná součtu průtoků do stoky .

{\displaystyle |f|=\sum _{v\in V}f_{sv))

\ \součet _{{w\in V}}f(w,t)

Problém maximálního průtoku je najít takový průtok, kde je hodnota průtoku maximální.

Rozhodnutí

Následující tabulka uvádí některé algoritmy pro řešení problému.

Metoda	Složitost	Popis
Lineární programování	Záleží na konkrétním algoritmu. U simplexové metody je exponenciální.	Prezentujte problém maximálního průtoku jako problém lineárního programování. Proměnnými jsou toky podél okrajů a omezení jsou zachování toku a omezení propustnosti.
Ford-Fulkersonův algoritmus	Závisí na rozšiřujícím algoritmu hledání cesty. Vyžaduje takové vyhledávání. $O(\max \|f\|)$	Najděte jakoukoli rozšiřující cestu. Zvyšte průtok podél všech jeho okrajů o minimum jejich zbytkových kapacit. Opakujte, dokud existuje rozšiřující cesta. Algoritmus funguje pouze pro celočíselné šířky pásma. V opačném případě může běžet neomezeně dlouho, aniž by došlo ke správné odpovědi.
Edmonds-Karpův algoritmus	$O(\|V\|\|E\|^{2})$	Spustíme Ford-Fulkersonův algoritmus, pokaždé vybereme nejkratší rozšiřující cestu (nalezenou vyhledáváním do šířky ).
Dinitův algoritmus	$O(\|V\|^{2}\|E\|)$ nebo pro kapacity jednotek pomocí dynamických stromů Slethor a Tarjan [11] $O(\|V\|\surd \|E\|)$ $O(\|V\|\|E\|\log(\|V\|))$	Vylepšení Edmonds-Karpova algoritmu (ale chronologicky nalezeno dříve). Při každé iteraci pomocí prohledávání do šířky určujeme vzdálenosti od zdroje ke všem vrcholům zbytkové sítě. Sestrojíme graf obsahující pouze takové hrany zbytkové sítě, na kterých se tato vzdálenost zvětší o 1. Z grafu vyjmeme všechny slepé vrcholy s hranami, které k nim přiléhají, dokud se všechny vrcholy nestanou slepými. (Slepá ulička je vrchol, kromě zdroje a jímky, který neobsahuje jedinou hranu nebo z něj žádné hrany nevycházejí.) Na výsledném grafu najdeme nejkratší rozšiřující cestu (bude to libovolná cesta od s do t). Ze zbytkové sítě vyloučíme hranu s minimální kapacitou, opět vyloučíme vrcholy slepé uličky a tak dále, dokud nevznikne rozšiřující cesta.
Preflow Push Algorithm	$O(\|V\|^{2}\|E\|)$	Funguje na předběžném toku namísto proudu. Rozdíl je v tom, že pro jakýkoli vrchol u, kromě zdroje a jímky, musí být součet průtoků vstupujících do něj pro tok přísně nulový (podmínka zachování toku) a pro předtok musí být nezáporný. Tento součet se nazývá nadměrný tok k vrcholu a vrchol s kladným nadměrným tokem se říká , že přetéká . Navíc pro každý vrchol algoritmus ukládá další charakteristiku, výšku , což je nezáporné celé číslo. Algoritmus používá dvě operace: push , kdy se tok podél hrany směřující z vyššího do nižšího vrcholu zvětší o maximální možnou hodnotu, a lift , kdy se zvedne přetékající vrchol, ze kterého není možné tlačit kvůli nedostatečné výšce. . Zatlačení je možné, když hrana patří do zbytkové sítě, vede z vyššího vrcholu do nižšího a původní vrchol přetéká. Zvedání je možné, když je zvedáný vrchol plný, ale žádný z vrcholů, do kterých z něj vedou okraje zbytkové sítě, není níže než on. Provádí se do výšky o 1 větší, než je minimum výšek těchto vrcholů. Zpočátku je výška zdroje V, podél všech hran vycházejících ze zdroje protéká maximální možný průtok a zbývající výšky a průtoky jsou nulové. Operace tlačení a zvedání se provádějí tak dlouho, jak je to možné.
Algoritmus "zvednout na začátek"	$O(\|V\|^{3})$ nebo pomocí dynamických stromů $O(\|V\|\|E\|\log(\|V\|^{2}/\|E\|))$	Varianta předchozího algoritmu, která zvláštním způsobem definuje pořadí operací tlačení a zvedání.
Algoritmus binárního blokovacího toku [1]	$O(\|E\|\min\{\|V\|^{2/3},\surd {\|E\|}\}\log(\|V\|^{2}/\|E\|)\log(\ max \|f\|))$

Podrobnější seznam viz [2] a Seznam algoritmů pro zjištění maximálního průtoku .

Celá věta o proudění

Pokud jsou propustnosti celočíselné, maximální průtok je také celé číslo.

Věta vyplývá např. z Ford-Fulkersonovy věty .

Zobecnění, která redukují na původní problém

Některá zobecnění problému maximálního průtoku lze snadno zredukovat na původní problém.

Libovolný počet zdrojů a/nebo propadů

Pokud existuje více než jeden zdroj, přidejte nový vrchol S, ze kterého uděláme jediný zdroj. Ke každému ze starých zdrojů přidáváme hrany s nekonečnou kapacitou od S.

Podobně, je-li více jímek, přidáme nový vrchol T, ze kterého uděláme jedinou výlevku. K T přidáme hrany s nekonečnou kapacitou z každého ze starých dřezů.

Neorientované hrany

Každá neorientovaná hrana (u, v) je nahrazena dvojicí usměrněných hran (u, v) a (v, u).

Vertex Bandwidth Limit

Každý vrchol v s omezenou kapacitou rozdělíme na dva vrcholy v in a v out . Všechny hrany zahrnuté do v před rozdělením jsou nyní zahrnuty do v v . Všechny hrany, které vznikly z v před rozdělením, nyní pocházejí z v out . Přidejte hranu (v in ,v out ) s kapacitou . $životopis}$ $životopis}$

Omezení kapacity hran zespodu

V této verzi problémového prohlášení je hodnota toku každé hrany navíc zespodu omezena funkcí . Hodnota toku pro žádnou hranu tedy nemůže překročit její kapacitu, ale nemůže být menší než stanovené minimum, tzn. . K vyřešení problému je nutné transformovat původní dopravní síť na dopravní síť následovně: ${\displaystyle c'\colon E\to \mathbb {N} ^{+))$ $c'(e)\leqslant f(e)\leqslant c(e)$ $G=(V,E,s,t,c,c')$ $G'=(V',E',s',t',c'')$

Přidejte nový zdroj a umyvadlo . $s'$ $t'$
Pro každou hranu : $(v,w)$
1. Vytvořte dva nové vrcholy a . $X$ $y$
2. Nainstalujte a . $c''(v,x)=c(v,w)$ $c''(y,w)=c(v,w)$
3. Nainstalujte . $c''(x,y)=c(v,w)-c'(v,w)$
4. Nainstalujte a . $c''(s',y)=c'(v,w)$ $c''(x,t')=c'(v,w)$
Nainstalujte . $c''(t,t')=c''(s,s')=\sum _{e\in E}c(e)$

V B je definován tok, který splňuje podmínku omezení propustnosti hran zespodu právě tehdy, když je definován maximální tok, ve kterém jsou všechny okraje formy a "saturovány". Díky této konstrukci bude algoritmus pro nalezení toku ohraničeného zdola následující: $G$ $G'$ $(s',y)$ $(x,t')$

Od sestavení . $G$ $G'$
Najděte tok grafu , preferujte okraje formuláře a . $F'$ $G'$ $(s',y)$ $(x,t')$
Jestliže , kde je tok grafu, ve kterém je vynechána šířka pásma hran pod ním, pak neexistuje žádné řešení. $f'<f''+\sum _{e\in E(G)}c'(e)$ $F''$ $G$
V opačném případě vypočítejte tok z toku , tzn. . $F$ $F'$ $f(a,b)=f(a,x)$

Omezení kapacity hrany zespodu s alternativou

Tato varianta úlohy je shodná s předchozí s tím rozdílem, že hodnota průtoku pro každou hranu může být také rovna , tzn. nebo . Navzdory mírné změně podmínky neexistuje polynomické řešení tohoto problému, pokud třídy P a NP nejsou stejné . Jako důkaz tvrzení lze uvést polynomiální redukci problému Exact-3-SAT . $0$ $c'(e)\leqslant f(e)\leqslant c(e)$ $f(e)=0$

Viz také

Poznámky

↑ John J. O'Connor a Edmund F. Robertson . George Dantzig (anglicky) je biografie v archivu MacTutor .
↑ Cottle, Richard; Johnson, Ellis; Wets, Roger, "George B. Dantzig (1914-2005)" Archivováno 7. září 2015 na Wayback Machine , Notices of the American Mathematical Society , v.54, č.3, březen 2007. Srov. str. 348
↑ 1 2 Hardesty, Larry, „První vylepšení základního algoritmu za 10 let“ Archivováno 28. března 2014 na Wayback Machine , MIT News Office, 27. září 2010
↑ Borndörfer, Ralf; Grotschel, Martin; Löbel, Andreas, "Alcuin's Transportation Problems and Integer Programing" Archivováno 7. srpna 2011 ve Wayback Machine , Konrad-Zuse-Zentrum für Informationstechnik , Berlín, Německo, listopad 1995. Srov. str.3
↑ Powell, Stewart M., "The Berlin Airlift" , Air Force Magazine , červen 1998.
↑ Dantzig, GB, „Application of the Simplex Method to a Transportation Problem“ Archivováno 19. července 2010 ve Wayback Machine , v TC Koopman (ed.): Analýza činností a produkce a alokace , New York, (1951) 359-373.
↑ Ford, LR, Jr.; Fulkerson, D.R., "Maximum Flow through a Network", Canadian Journal of Mathematics (1956), str. 399-404.
↑ Ford, LR, Jr.; Fulkerson, D.R., Flows in Networks , Princeton University Press (1962).
↑ Kelner, Jonathan, "Elektrické toky, Laplaciánské systémy a rychlejší aproximace maximálního toku v neorientovaných grafech" Archivováno 24. června 2011 na Wayback Machine , přednáška na CSAIL, MIT, úterý 28. září 2010
↑ Elektrické toky, Laplaciánské systémy a rychlejší aproximace maximálního průtoku v neorientovaných grafech Archivováno 29. listopadu 2010 na Wayback Machine , Paul Cristiano et al., 19. října 2010.
↑ Dinits algoritmus . Získáno 28. října 2010. Archivováno z originálu 7. května 2015. (neurčitý)

Literatura

Schrijver, Alexander, "O historii problémů dopravy a maximálního toku" , Mathematical Programming 91 (2002) 437-445
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmy: konstrukce a analýza = Introduction to Algorithms / Ed. I. V. Krasíková. - 2. vyd. - M. : Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 . . Kapitola 26
↑ Andrew V. Goldberg a S. Rao . Beyond the flow decomposition barier (neopr.) // J. Assoc. Počítat. Mach.. - 1998. - T. 45 . - S. 753-782 . - doi : 10.1145/290179.290181 .
↑ Andrew V. Goldberg a Robert E. Tarjan . Nový přístup k problému maximálního toku (anglicky) // Journal of the ACM : journal. - ACM Press, 1988. - Sv. 35 , č. 4 . - S. 921-940 . — ISSN 0004-5411 . - doi : 10.1145/48014.61051 .
↑ Joseph Cheriyan a Kurt Mehlhorn . Analýza pravidla výběru nejvyšší úrovně v algoritmu preflow-push max-flow // Information Processing Letters : deník. - 1999. - Sv. 69 , č. 5 . - str. 239-242 . - doi : 10.1016/S0020-0190(99)00019-8 .
↑ Daniel D. Sleator a Robert E. Tarjan . Datová struktura pro dynamické stromy (anglicky) // Journal of Computer and System Sciences : deník. - 1983. - Sv. 26 , č. 3 . - S. 362-391 . — ISSN 0022-0000 . - doi : 10.1016/0022-0000(83)90006-5 .
↑ Daniel D. Sleator a Robert E. Tarjan . Samonastavitelné binární vyhledávací stromy (anglicky) // Journal of the ACM : journal. - ACM Press, 1985. - Sv. 32 , č. 3 . - S. 652-686 . — ISSN 0004-5411 . - doi : 10.1145/3828.3835 .
Eugene Lawler 4. Síťové toky // Kombinační optimalizace: Sítě a matice (anglicky) . - Dover, 2001. - S. 109-177. — ISBN 0486414531 .