Maximalt flödesproblem

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 29 september 2020; kontroller kräver 11 redigeringar .

Inom optimeringsteori och grafteori är det maximala flödesproblemet att hitta ett sådant flöde genom transportnätet att summan av flöden från källan, eller motsvarande summan av flöden till sänkan, är maximal.

Maxflödesproblemet är ett specialfall av svårare problem, såsom cirkulationsproblemet .

Historik

Efter USA:s inträde i andra världskriget 1941, anslöt sig matematikern George Bernard Dantzig till United States Air Forces statistiska kontor i Washington DC . Från 1941 till 1946 ledde han Combat Analysis Branch, där han arbetade med olika matematiska problem. [1] [2] Därefter, med hjälp av Danzigs arbete, löstes problemet med maximalt flöde först under förberedelserna av luftbron under blockaden av Västberlin , som ägde rum 1948-1949. [3] [4] [5]

1951 formulerade George Dantzig problemet först i allmänna termer. [6]

År 1955 byggde Lester Ford och Delbert Ray Fulkerson först en algoritm speciellt utformad för att lösa detta problem . Deras algoritm kallades Ford-Fulkerson-algoritmen . [7] [8]

I framtiden förbättrades lösningen av problemet många gånger.

År 2010 visade forskarna Jonathan Kelner och Aleksander Mądry från MIT tillsammans med sina kollegor Daniel Spielman från Yale University och Shen- Hua Teng från South University of California ytterligare en förbättring av algoritmen för första gången på tio år. [3] [9] [10]

Definition

Givet ett transportnät med källa , sänka och kapacitet . $N=(V,E)$ $s\in V$ $t\in V$ $c$

Flödesvärdet är summan av flödena från källan . I artikeln " Transportnät " bevisas att det är lika med summan av flödena till avloppet .

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

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

Problemet med det maximala flödet är att hitta ett sådant flöde, där flödets värde är maximalt.

Beslut

Följande tabell listar några algoritmer för att lösa problemet.

Metod	Komplexitet	Beskrivning
Linjär programmering	Beror på den specifika algoritmen. För simplexmetoden är den exponentiell.	Presentera maximalt flödesproblem som ett linjärt programmeringsproblem. Variablerna är flödena längs kanterna, och begränsningarna är bevarandet av flödet och begränsningen av genomströmningen.
Ford-Fulkerson algoritm	Beror på sökalgoritmen för utökad sökväg. Kräver sådana sökningar. $O(\max \|f\|)$	Hitta någon förstärkningsväg. Öka flödet längs alla dess kanter med ett minimum av deras restkapacitet. Upprepa så länge det finns en förstärkningsväg. Algoritmen fungerar bara för heltalsbandbredder. Annars kan det köras på obestämd tid utan att konvergera till rätt svar.
Edmonds-Karps algoritm	$O(\|V\|\|E\|^{2})$	Vi kör Ford-Fulkerson-algoritmen, varje gång vi väljer den kortaste förstärkningsvägen (hittad genom sökning på bredden först ).
Dinits algoritm	$O(\|V\|^{2}\|E\|)$ eller för enhetskapacitet med Slethor och Tarjan dynamiska träd [11] $O(\|V\|\surd \|E\|)$ $O(\|V\|\|E\|\log(\|V\|))$	Förbättring av Edmonds-Karp-algoritmen (men kronologiskt funnen tidigare). Vid varje iteration, med hjälp av bredd-först-sökning, bestämmer vi avstånden från källan till alla hörn i det kvarvarande nätverket. Vi konstruerar en graf som endast innehåller sådana kanter av det kvarvarande nätverket på vilka detta avstånd ökar med 1. Vi exkluderar från grafen alla återvändspunkter med kanter som faller mot dem, tills alla hörn blir icke-återvända. (En återvändsgränd är en vertex, förutom källan och sänkan, som inte inkluderar en enda kant eller från vilken inga kanter utgår.) På den resulterande grafen hittar vi den kortaste förstärkningsvägen (det kommer att vara vilken väg som helst från s till t). Vi exkluderar kanten med den minsta kapaciteten från det kvarvarande nätverket, utesluter återigen döda hörn, och så vidare tills det finns en utökad väg.
Preflow Push Algoritm	$O(\|V\|^{2}\|E\|)$	Fungerar på ett förflöde istället för en ström. Skillnaden är att för varje vertex u, förutom för källan och sänkan, måste summan av flödena som kommer in i den för flödet vara strikt noll (flödeskonserveringsvillkoret), och för förflödet måste det vara icke-negativt. Denna summa kallas för överflödet till vertexet, och en vertex med ett positivt överflöde sägs vara överflödande . Dessutom, för varje vertex, sparar algoritmen ytterligare en egenskap, höjden , som är ett icke-negativt heltal. Algoritmen använder två operationer: push , när flödet längs en kant som går från en högre till en lägre vertex ökas med maximalt möjliga mängd, och lift , när en överfull vertex, från vilken det är omöjligt att trycka på grund av otillräcklig höjd, höjs . Pushing är möjligt när en kant tillhör det resterande nätverket, leder från en högre vertex till en lägre, och den ursprungliga vertexen svämmar över. Lyftning är möjlig när vertexet som lyfts är fullt, men ingen av de hörn som kanterna på det kvarvarande nätverket leder till är lägre än den. Det utförs upp till en höjd som är 1 större än minimum av höjderna på dessa hörn. Ursprungligen är källans höjd V, längs alla kanter som utgår från källan, maximalt möjliga flödesflöden, och de återstående höjderna och flödena är noll. Tryck- och lyftoperationerna utförs så länge som möjligt.
Algoritm "höja till början"	$O(\|V\|^{3})$ eller använda dynamiska träd $O(\|V\|\|E\|\log(\|V\|^{2}/\|E\|))$	En variant av den tidigare algoritmen som definierar ordningen för push- och lyftoperationerna på ett speciellt sätt.
Binär blockeringsflödesalgoritm [1]	$O(\|E\|\min\{\|V\|^{2/3},\surd {\|E\|}\}\log(\|V\|^{2}/\|E\|)\log(\ max \|f\|))$

För en mer detaljerad lista, se [2] och Lista över algoritmer för att hitta det maximala flödet .

Hela flödessatsen

Om genomströmningarna är heltal är det maximala flödet också heltal.

Satsen följer till exempel från Ford–Fulkersons sats .

Generaliseringar som reducerar till det ursprungliga problemet

Vissa generaliseringar av problemet med maximalt flöde reduceras lätt till det ursprungliga problemet.

Godtyckligt antal källor och/eller sänkor

Om det finns mer än en källa, lägg till en ny vertex S, som vi gör till den enda källan. Vi lägger till kanter med oändlig kapacitet från S till var och en av de gamla källorna.

På samma sätt, om det finns mer än en diskbänk, lägger vi till en ny vertex T, som vi gör till den enda diskbänken. Vi lägger till kanter med oändlig kapacitet från var och en av de gamla diskbänkarna till T.

Oriktade kanter

Varje oriktad kant (u, v) ersätts av ett par riktade kanter (u, v) och (v, u).

Vertex bandbreddsgräns

Vi delar upp varje vertex v med begränsad kapacitet i två hörn v in och v ut . Alla kanter som ingår i v före delning ingår nu i v i . Alla kanter som härstammar från v innan klyvningen kommer nu från v ut . Lägg till en kant (v in ,v out ) med kapacitet . $CV}$ $CV}$

Begränsning av kanternas kapacitet underifrån

I den här versionen av problemformuleringen begränsas värdet av flödet för varje kant dessutom underifrån av funktionen . Således kan flödesvärdet för någon kant inte överstiga dess kapacitet, men det kan inte vara mindre än det specificerade minimumet, dvs. . För att lösa problemet är det nödvändigt att omvandla det ursprungliga transportnätet till ett transportnät enligt följande: ${\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'')$

Lägg till ny källa och sänk . $s'$ $t'$
För varje kant : $(v,w)$
1. Skapa två nya hörn och . $x$ $y$
2. Installera och . $c''(v,x)=c(v,w)$ $c''(y,w)=c(v,w)$
3. Installera . $c''(x,y)=c(v,w)-c'(v,w)$
4. Installera och . $c''(s',y)=c'(v,w)$ $c''(x,t')=c'(v,w)$
Installera . $c''(t,t')=c''(s,s')=\summa _{e\in E}c(e)$

Ett flöde definieras i B som uppfyller villkoret att begränsa genomströmningen av kanter underifrån om och endast om ett maximalt flöde definieras där alla kanter av formen och är "mättade". Tack vare denna konstruktion kommer algoritmen för att hitta ett flöde avgränsat underifrån att vara följande: $G$ $G'$ $(s',y)$ $(x,t')$

Från bygg . $G$ $G'$
Hitta flödet av grafen , föredrar kanterna på formuläret och . $f'$ $G'$ $(s',y)$ $(x,t')$
Om , var är flödet av grafen där bandbredden för kanterna nedanför utelämnas, så finns det ingen lösning. $f'<f''+\sum _{e\in E(G)}c'(e)$ $f''$ $G$
Beräkna annars flödet från flödet , dvs. . $f$ $f'$ $f(a,b)=f(a,x)$

Begränsning av kantkapacitet underifrån med en alternativ

Denna variant av problemet är identisk med den tidigare, med skillnaden att flödesvärdet för varje kant också kan vara lika med , d.v.s. eller . Trots en liten förändring i tillståndet finns det ingen polynomlösning på detta problem om klasserna P och NP inte är lika . Som ett bevis på påståendet kan man ge en polynomreduktion till Exact-3-SAT- problemet . $0$ $c'(e)\leqslant f(e)\leqslant c(e)$ $f(e)=0$

Se även

Anteckningar

↑ John J. O'Connor och Edmund F. Robertson . George Dantzig (engelska) är en biografi på MacTutor- arkivet .
↑ Cottle, Richard; Johnson, Ellis; Wets, Roger, "George B. Dantzig (1914-2005)" Arkiverad 7 september 2015 på Wayback Machine , Notices of the American Mathematical Society , v.54, nr 3, mars 2007. Jfr. s. 348
↑ 1 2 Hardesty, Larry, "Första förbättringen av fundamental algoritm på 10 år" Arkiverad 28 mars 2014 på Wayback Machine , MIT News Office, 27 september 2010
↑ Borndörfer, Ralf; Grotschel, Martin; Löbel, Andreas, "Alcuins transportproblem och heltalsprogrammering" Arkiverad 7 augusti 2011 på Wayback Machine , Konrad-Zuse-Zentrum für Informationstechnik , Berlin, Tyskland, november 1995. Jfr. s.3
↑ Powell, Stewart M., "The Berlin Airlift" , Air Force Magazine , juni 1998.
↑ Dantzig, GB, "Tillämpning av den enkla metoden för ett transportproblem" Arkiverad 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" Arkiverad 24 juni 2011 på Wayback Machine , föredrag på CSAIL, MIT, tisdag 28 september 2010
↑ Elektriska flöden, Laplacian-system och snabbare approximation av maximalt flöde i oriktade grafer Arkiverade 29 november 2010 på Wayback Machine , av Paul Cristiano et al., 19 oktober 2010.
↑ Dinits-algoritm . Hämtad 28 oktober 2010. Arkiverad från originalet 7 maj 2015. (obestämd)

Litteratur

Schrijver, Alexander, "Om problemen med transport och maximalt flöde" , Mathematical Programmering 91 (2002) 437-445
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmer: konstruktion och analys = Introduktion till algoritmer / Ed. I. V. Krasikova. - 2:a uppl. - M. : Williams, 2005. - 1296 sid. — ISBN 5-8459-0857-4 . . Kapitel 26
↑ Andrew V. Goldberg och S. Rao . Bortom flödesnedbrytningsbarriären (neopr.) // J. Assoc. Comput. Mach.. - 1998. - T. 45 . - S. 753-782 . - doi : 10.1145/290179.290181 .
↑ Andrew V. Goldberg och Robert E. Tarjan . A new approach to the maximum-flow problem (engelska) // Journal of the ACM : journal. - ACM Press, 1988. - Vol. 35 , nr. 4 . - P. 921-940 . — ISSN 0004-5411 . - doi : 10.1145/48014.61051 .
↑ Joseph Cheriyan och Kurt Mehlhorn . En analys av urvalsregeln på högsta nivå i preflow-push max-flow-algoritmen // Information Processing Letters : journal. - 1999. - Vol. 69 , nr. 5 . - s. 239-242 . - doi : 10.1016/S0020-0190(99)00019-8 .
↑ Daniel D. Sleator och Robert E. Tarjan . En datastruktur för dynamiska träd (engelska) // Journal of Computer and System Sciences : journal. - 1983. - Vol. 26 , nr. 3 . - s. 362-391 . — ISSN 0022-0000 . - doi : 10.1016/0022-0000(83)90006-5 .
↑ Daniel D. Sleator och Robert E. Tarjan . Självjusterande binära sökträd (engelska) // 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. Nätverksflöden // Kombinatorisk optimering: Nätverk och matroider (engelska) . - Dover, 2001. - S. 109-177. — ISBN 0486414531 .