Maksimalt flow problem

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 29. september 2020; checks kræver 11 redigeringer .

I optimeringsteori og grafteori er det maksimale flowproblem at finde et sådant flow gennem transportnettet, at summen af strømme fra kilden, eller tilsvarende summen af strømme til vasken, er maksimal.

Det maksimale flowproblem er et særligt tilfælde af vanskeligere problemer, såsom cirkulationsproblemet .

Historie

Efter USA's indtræden i Anden Verdenskrig i 1941 sluttede matematikeren George Bernard Dantzig sig til United States Air Forces statistiske kontor i Washington DC . Fra 1941 til 1946 ledede han Combat Analysis Branch, hvor han arbejdede med forskellige matematiske problemer. [1] [2] Efterfølgende, ved hjælp af Danzigs arbejde, blev problemet med maksimal flow først løst under klargøringen af luftbroen under blokaden af Vestberlin , som fandt sted i 1948-1949. [3] [4] [5]

I 1951 formulerede George Dantzig første gang problemet i generelle vendinger. [6]

I 1955 byggede Lester Ford og Delbert Ray Fulkerson først en algoritme specielt designet til at løse dette problem . Deres algoritme blev kaldt Ford-Fulkerson-algoritmen . [7] [8]

I fremtiden blev løsningen af problemet forbedret mange gange.

I 2010 demonstrerede forskerne Jonathan Kelner og Aleksander Mądry fra MIT sammen med deres kolleger Daniel Spielman fra Yale University og Shen - Hua Teng fra South University of California endnu en forbedring af algoritmen for første gang i 10 år. [3] [9] [10]

Definition

Givet et transportnetværk med kilde , synke og kapacitet . $N=(V,E)$ $s\in V$ $t\in V$ $c$

Værdien af flow er summen af strømmene fra kilden . I artiklen " Transportnetværk " er det bevist, at det er lig med summen af strømmene til vasken .

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

\ \sum _{{w\in V}}f(w,t)

Problemet med det maksimale flow er at finde et sådant flow, hvor værdien af flowet er maksimalt.

Beslutninger

Følgende tabel viser nogle algoritmer til løsning af problemet.

Metode	Kompleksitet	Beskrivelse
Lineær programmering	Afhænger af den specifikke algoritme. For simpleksmetoden er den eksponentiel.	Præsenter det maksimale flowproblem som et lineært programmeringsproblem. Variablerne er strømmene langs kanterne, og begrænsningerne er bevarelsen af strømmen og begrænsningen af gennemløbet.
Ford-Fulkerson algoritme	Afhænger af den udvidede stisøgningsalgoritme. Kræver sådanne søgninger. $O(\max \|f\|)$	Find en hvilken som helst forøgelsesvej. Øg flowet langs alle dets kanter med et minimum af deres resterende kapacitet. Gentag, så længe der er en forøgelsessti. Algoritmen virker kun for heltalsbåndbredder. Ellers kan den køre på ubestemt tid uden at konvergere til det rigtige svar.
Edmonds-Karp algoritme	$O(\|V\|\|E\|^{2})$	Vi udfører Ford-Fulkerson-algoritmen, hver gang vi vælger den korteste forøgelsesvej (fundet ved bredde-først-søgning ).
Dinits algoritme	$O(\|V\|^{2}\|E\|)$ eller for enhedskapaciteter ved hjælp af Slethor og Tarjan dynamiske træer [11] $O(\|V\|\surd \|E\|)$ $O(\|V\|\|E\|\log(\|V\|))$	Forbedring af Edmonds-Karp-algoritmen (men kronologisk fundet tidligere). Ved hver iteration, ved hjælp af bredde-først søgning, bestemmer vi afstandene fra kilden til alle hjørner i det resterende netværk. Vi konstruerer en graf, der kun indeholder sådanne kanter af det resterende netværk, hvor denne afstand øges med 1. Vi udelukker fra grafen alle blindgyder med kanter, der falder ind på dem, indtil alle hjørner bliver ikke-blindgænger. (En blindgyde er et toppunkt, bortset fra kilden og synken, som ikke omfatter en enkelt kant, eller hvorfra ingen kanter udgår.) På den resulterende graf finder vi den korteste forstærkende vej (det vil være enhver vej fra s til t). Vi udelukker kanten med den minimale kapacitet fra det resterende netværk, udelukker igen blinde hjørner og så videre, indtil der er en forøgelsessti.
Preflow Push Algoritme	$O(\|V\|^{2}\|E\|)$	Fungerer på en preflow i stedet for en stream. Forskellen er, at for ethvert toppunkt u, bortset fra kilden og synken, skal summen af de strømme, der kommer ind i den for flowet, være strengt nul (strømningsbevaringsbetingelsen), og for præflowet skal den være ikke-negativ. Denne sum kaldes overskydende flow til toppunktet, og et toppunkt med en positiv overskydende flow siges at være overfyldt . Derudover gemmer algoritmen for hvert toppunkt en yderligere karakteristik, højden , som er et ikke-negativt heltal. Algoritmen bruger to operationer: skub , når flowet langs en kant, der går fra et højere til et lavere toppunkt, øges med den maksimalt mulige mængde, og løft , når et overløbende toppunkt, hvorfra det er umuligt at skubbe på grund af utilstrækkelig højde, hæves . Det er muligt at skubbe, når en kant tilhører det resterende netværk, fører fra et højere toppunkt til et lavere, og det oprindelige toppunkt flyder over. Løft er muligt, når toppunktet, der løftes, er fuldt, men ingen af de toppunkter, hvortil kanterne af det resterende netværk fører fra det, er lavere end det. Det udføres op til en højde, der er 1 større end minimumshøjderne af disse hjørner. Indledningsvis er højden af kilden V, langs alle kanter, der udgår fra kilden, er de maksimalt mulige strømningsstrømme, og de resterende højder og strømme er nul. Skub- og løfteoperationerne udføres så længe som muligt.
Algoritme "løft til begyndelsen"	$O(\|V\|^{3})$ eller ved at bruge dynamiske træer $O(\|V\|\|E\|\log(\|V\|^{2}/\|E\|))$	En variant af den tidligere algoritme, der definerer rækkefølgen af skub- og løfteoperationerne på en særlig måde.
Binær blokeringsflowalgoritme [1]	$O(\|E\|\min\{\|V\|^{2/3},\surd {\|E\|}\}\log(\|V\|^{2}/\|E\|)\log(\ max \|f\|))$

For en mere detaljeret liste, se [2] og Liste over algoritmer for at finde det maksimale flow .

Hele flowsætningen

Hvis gennemløbene er heltal, er det maksimale flow også heltal.

Sætningen følger for eksempel af Ford-Fulkerson-sætningen .

Generaliseringer, der reducerer til det oprindelige problem

Nogle generaliseringer af det maksimale flow-problem reduceres let til det oprindelige problem.

Vilkårligt antal kilder og/eller dræn

Hvis der er mere end én kilde, tilføj et nyt toppunkt S, som vi gør til den eneste kilde. Vi tilføjer kanter med uendelig kapacitet fra S til hver af de gamle kilder.

På samme måde, hvis der er mere end én vask, tilføjer vi et nyt toppunkt T, som vi gør til den eneste vask. Vi tilføjer kanter med uendelig kapacitet fra hver af de gamle vaske til T.

Urettede kanter

Hver ikke-rettet kant (u, v) erstattes af et par rettede kanter (u, v) og (v, u).

Vertex båndbreddegrænse

Vi opdeler hvert hjørne v med begrænset kapacitet i to spidser v ind og v ud . Alle kanter inkluderet i v før opdeling er nu inkluderet i v i . Alle kanter, der stammer fra v før spaltning, stammer nu fra v ud . Tilføj en kant (v ind , v ud ) med kapacitet . $c_{v}$ $c_{v}$

Begrænsning af kapaciteten af kanter nedefra

I denne version af problemformuleringen er værdien af flowet for hver kant yderligere begrænset nedefra af funktionen . Således kan flowværdien for enhver kant ikke overstige dens kapacitet, men den kan ikke være mindre end det specificerede minimum, dvs. . For at løse problemet er det nødvendigt at omdanne det oprindelige transportnetværk til et transportnetværk som følger: ${\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'')$

Tilføj ny kilde og vask . $s'$ $t'$
For hver kant : $(v,w)$
1. Opret to nye hjørner og . $x$ $y$
2. Installer og . $c''(v,x)=c(v,w)$ $c''(y,w)=c(v,w)$
3. Installer . $c''(x,y)=c(v,w)-c'(v,w)$
4. Installer og . $c''(s',y)=c'(v,w)$ $c''(x,t')=c'(v,w)$
Installer . $c''(t,t')=c''(s,s')=\sum _{e\in E}c(e)$

Et flow er defineret i B, der opfylder betingelsen om at begrænse gennemstrømningen af kanter nedefra, hvis og kun hvis der er defineret et maksimalt flow, hvor alle kanter af formen og er "mættede". Takket være denne konstruktion vil algoritmen til at finde et flow afgrænset nedefra være som følger: $G$ $G'$ $(s',y)$ $(x,t')$

Fra opbygning . $G$ $G'$
Find strømmen af grafen , foretrækker kanterne af formularen og . $f'$ $G'$ $(s',y)$ $(x,t')$
Hvis , hvor er flowet af grafen , hvor båndbredden af kanterne nedenfor er udeladt, så er der ingen løsning. $f'<f''+\sum _{e\in E(G)}c'(e)$ $f''$ $G$
Ellers skal du beregne flowet fra flowet , dvs. . $f$ $f'$ $f(a,b)=f(a,x)$

Begrænsning af kantkapacitet nedefra med en alternativ

Denne variant af problemet er identisk med den foregående, med den forskel at flowværdien for hver kant også kan være lig , dvs. eller . På trods af en lille ændring i tilstanden er der ingen polynomiel løsning på dette problem, hvis klasserne P og NP ikke er ens . Som et bevis på påstanden kan man give en polynomiel reduktion til Exact-3-SAT- problemet . $0$ $c'(e)\leqslant f(e)\leqslant c(e)$ $f(e)=0$

Se også

Noter

↑ John J. O'Connor og Edmund F. Robertson . George Dantzig (engelsk) er en biografi på MacTutor- arkivet .
↑ Cottle, Richard; Johnson, Ellis; Wets, Roger, "George B. Dantzig (1914-2005)" Arkiveret 7. september 2015 på Wayback Machine , Notices of the American Mathematical Society , v.54, nr.3, marts 2007. Jf. s. 348
↑ 1 2 Hardesty, Larry, "Første forbedring af fundamental algoritme i 10 år" Arkiveret 28. marts 2014 på Wayback Machine , MIT News Office, 27. september 2010
↑ Borndörfer, Ralf; Grotschel, Martin; Löbel, Andreas, "Alcuins transportproblemer og heltalsprogrammering" Arkiveret 7. august 2011 på Wayback Machine , Konrad-Zuse-Zentrum für Informationstechnik , Berlin, Tyskland, november 1995. Jf. s.3
↑ Powell, Stewart M., "The Berlin Airlift" , Air Force Magazine , juni 1998.
↑ Dantzig, GB, "Application of the Simplex Method to a Transportation Problem" Arkiveret 19. juli 2010 på Wayback Machine , i TC Koopman (red.): Activity Analysis and Production and Allocation , New York, (1951) 359-373.
↑ Ford, LR, Jr.; Fulkerson, D.R., "Maximum Flow through a Network", Canadian Journal of Mathematics (1956), s. 399-404.
↑ Ford, LR, Jr.; Fulkerson, D.R., Flows in Networks , Princeton University Press (1962).
↑ Kelner, Jonathan, "Electrical Flows, Laplacian Systems and Faster Approximation of Maximum Flow in Undirected Graphs" Arkiveret 24. juni 2011 på Wayback Machine , foredrag på CSAIL, MIT, tirsdag den 28. september 2010
↑ Elektriske flows, Laplacian-systemer og hurtigere tilnærmelse af maksimalt flow i urettede grafer Arkiveret 29. november 2010 på Wayback Machine af Paul Cristiano et al., 19. oktober 2010.
↑ Dinits-algoritme . Hentet 28. oktober 2010. Arkiveret fra originalen 7. maj 2015. (ubestemt)

Litteratur

Schrijver, Alexander, "Om transport- og maksimalstrømsproblemernes historie" , Mathematical Programming 91 (2002) 437-445
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmer: konstruktion og analyse = Introduktion til algoritmer / Ed. I. V. Krasikova. - 2. udg. - M. : Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 . . Kapitel 26
↑ Andrew V. Goldberg og S. Rao . Ud over strømningsnedbrydningsbarrieren (neopr.) // J. Assoc. Comput. Mach.. - 1998. - T. 45 . - S. 753-782 . - doi : 10.1145/290179.290181 .
↑ Andrew V. Goldberg og Robert E. Tarjan . A new approach to the maximum-flow problem (engelsk) // Journal of the ACM : journal. - ACM Press, 1988. - Vol. 35 , nr. 4 . - S. 921-940 . — ISSN 0004-5411 . - doi : 10.1145/48014.61051 .
↑ Joseph Cheriyan og Kurt Mehlhorn . En analyse af den højeste udvælgelsesregel i preflow-push max-flow-algoritmen // Information Processing Letters : journal. - 1999. - Bd. 69 , nr. 5 . - S. 239-242 . - doi : 10.1016/S0020-0190(99)00019-8 .
↑ Daniel D. Sleator og Robert E. Tarjan . En datastruktur for dynamiske træer (engelsk) // Journal of Computer and System Sciences : journal. - 1983. - Bd. 26 , nr. 3 . - S. 362-391 . — ISSN 0022-0000 . - doi : 10.1016/0022-0000(83)90006-5 .
↑ Daniel D. Sleator og Robert E. Tarjan . Selvjusterende binære søgetræer (engelsk) // Journal of the ACM : journal. - ACM Press, 1985. - Vol. 32 , nr. 3 . - s. 652-686 . — ISSN 0004-5411 . - doi : 10.1145/3828.3835 .
Eugene Lawler 4. Netværksflow // Kombinatorisk optimering: netværk og matroider (engelsk) . - Dover, 2001. - S. 109-177. — ISBN 0486414531 .