Maximális áramlási probléma

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. szeptember 29-én felülvizsgált verziótól ; az ellenőrzések 11 szerkesztést igényelnek .

Az optimalizálás elméletben és a gráfelméletben a maximális áramlási probléma az, hogy olyan áramlást találjunk a szállítási hálózaton keresztül , amelynél a forrásból érkező áramlások összege, vagy ennek megfelelően a nyelőhöz tartó áramlások összege maximális.

A maximális áramlási probléma a nehezebb problémák speciális esete, mint például a keringési probléma .

Történelem

Miután az Egyesült Államok 1941-ben belépett a második világháborúba , George Bernard Dantzig matematikus csatlakozott az Egyesült Államok légierejének statisztikai hivatalához Washington DC -ben . 1941 és 1946 között a Combat Analysis Branch vezetője volt, ahol különféle matematikai problémákkal foglalkozott. [1] [2] Ezt követően, Danzig munkáját felhasználva, először a léghíd előkészítése során , az 1948-1949- es nyugat-berlini blokád idején oldották meg a maximális áramlási problémát . [3] [4] [5]

1951-ben George Dantzig fogalmazta meg először általánosságban a problémát. [6]

1955-ben Lester Ford és Delbert Ray Fulkerson először készített egy algoritmust, amelyet kifejezetten ennek a problémának a megoldására terveztek . Algoritmusukat Ford-Fulkerson algoritmusnak hívták . [7] [8]

A jövőben a probléma megoldását sokszor javították.

2010-ben Jonathan Kelner és Aleksander Mądry, az MIT kutatói , valamint kollégáikkal, Daniel Spielmannel , a Yale Egyetemen és Shen - Hua Tenggel , a Dél-A Kaliforniai Egyetemen 10 év után először mutattak be egy újabb fejlesztést az algoritmuson. [3] [9] [10]

Definíció

Adott egy szállítási hálózat forrással , nyelővel és kapacitással . $N=(V,E)$ $s\in V$ $t\in V$ $c$

Az áramlás értéke a forrásból származó áramlások összege . A „ Közlekedési hálózat ” cikkben bebizonyosodott, hogy ez egyenlő a nyelőhöz vezető áramlások összegével .

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

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

A maximális áramlás problémája az , hogy olyan áramlást találjunk, ahol az áramlás maximális értéke.

Döntések

Az alábbi táblázat felsorol néhány algoritmust a probléma megoldására.

Módszer	Bonyolultság	Leírás
Lineáris programozás	Az adott algoritmustól függ. A szimplex módszernél ez exponenciális.	Mutassa be a maximális áramlási problémát lineáris programozási problémaként. A változók a szélek mentén folyó áramlások, a korlátok pedig az áramlás megőrzése és az áteresztőképesség korlátozása.
Ford-Fulkerson algoritmus	A bővítő útvonal keresési algoritmusától függ. Ilyen keresést igényel . $O(\max \|f\|)$	Keressen bármilyen bővítő utat. Növelje az áramlást az összes széle mentén a maradék kapacitás minimális értékével. Addig ismételje, amíg van egy növelési út. Az algoritmus csak egész számú sávszélesség esetén működik. Ellenkező esetben korlátlan ideig futhat anélkül, hogy konvergálna a helyes válaszhoz.
Edmonds-Karp algoritmus	$O(\|V\|\|E\|^{2})$	Végrehajtjuk a Ford-Fulkerson algoritmust, minden alkalommal kiválasztva a legrövidebb kibővítési útvonalat ( a szélesség-első keresés alapján ).
Dinit algoritmusa	$O(\|V\|^{2}\|E\|)$ vagy Slethor és Tarjan dinamikus fákat használó egységkapacitásokhoz [11] $O(\|V\|\surd \|E\|)$ $O(\|V\|\|E\|\log(\|V\|))$	Az Edmonds-Karp algoritmus továbbfejlesztése (de kronologikusan korábban találtuk). Minden iterációnál a szélesség-első keresés segítségével meghatározzuk a távolságot a forrástól a maradék hálózat összes csúcsáig. Készítünk egy gráfot, amely a reziduális hálózatnak csak olyan éleit tartalmazza, amelyeken ez a távolság 1-gyel növekszik. A gráfból kizárunk minden olyan zsákutcát, amelynek élei beesnek, amíg az összes csúcs nem zsákutcává válik. (A zsákutca egy csúcs, kivéve a forrást és a nyelőt, amely nem tartalmaz egyetlen élt sem, vagy amelyből nem származnak élek.) Az eredményül kapott gráfon megtaláljuk a legrövidebb növelési utat (bármilyen út lesz az s-ből). t-ig). Kizárjuk a maradék hálózatból a minimális kapacitású élt, ismét kizárjuk a zsákutca csúcsait, és így tovább, amíg nincs bővítési út.
Preflow Push Algorithm	$O(\|V\|^{2}\|E\|)$	Előfolyamon működik folyam helyett. A különbség az, hogy bármely u csúcsra, kivéve a forrást és a nyelőt, az áramláshoz belépő áramlások összegének szigorúan nullának kell lennie (az áramlásmegmaradás feltétele), az előáramlásnál pedig nem negatívnak kell lennie. Ezt az összeget a csúcshoz vezető többletáramlásnak nevezzük , és a pozitív többletáramlású csúcsot túlcsordulásnak nevezzük . Ezenkívül az algoritmus minden csúcshoz elment egy további jellemzőt, a magasságot , amely egy nem negatív egész szám. Az algoritmus két műveletet használ: push , amikor a magasabb csúcsból az alacsonyabb csúcsba tartó él mentén az áramlást a lehető legnagyobb mértékben növeljük, és lift , amikor egy túlcsorduló csúcsot emelünk, amelyből a nem megfelelő magasság miatt nem lehet tolni. . A tolás akkor lehetséges, ha egy él a maradék hálózathoz tartozik, magasabb csúcsból egy alacsonyabbba vezet, és az eredeti csúcs túlcsordul. Az emelés akkor lehetséges, ha az emelendő csúcs megtelt, de azon csúcsok közül, ahová a maradék hálózat élei vezetnek, egyik sem alacsonyabb nála. Olyan magasságig hajtják végre, amely 1-gyel nagyobb, mint e csúcsok magasságának minimuma. Kezdetben a forrás magassága V, a forrásból kilépő összes él mentén a maximális lehetséges áramlási áramlások, a fennmaradó magasságok és áramlások nullák. A tolási és emelési műveleteket a lehető leghosszabb ideig kell végrehajtani.
Algoritmus "emelés az elejére"	$O(\|V\|^{3})$ vagy dinamikus fák használatával $O(\|V\|\|E\|\log(\|V\|^{2}/\|E\|))$	Az előző algoritmus egy olyan változata, amely speciális módon határozza meg a toló és emelő műveletek sorrendjét.
Bináris blokkoló áramlási algoritmus [1]	$O(\|E\|\min\{\|V\|^{2/3},\surd {\|E\|}\}\log(\|V\|^{2}/\|E\|)\log(\ max \|f\|))$

A részletesebb listát lásd: [2] és A maximális áramlás megtalálására szolgáló algoritmusok listája .

Teljes áramlási tétel

Ha az áteresztőképesség egész szám, akkor a maximális áramlás is egész szám.

A tétel például a Ford–Fulkerson tételből következik .

Az eredeti problémára redukáló általánosítások

A maximális áramlási probléma néhány általánosítása könnyen redukálható az eredeti problémára.

Tetszőleges számú forrás és/vagy elnyelő

Ha egynél több forrás van, adjunk hozzá egy új S csúcsot, amelyet az egyetlen forrássá tesszük. Mindegyik régi forráshoz S-től végtelen kapacitású éleket adunk.

Hasonlóképpen, ha egynél több nyelő van, adunk hozzá egy új T csúcsot, amelyet az egyetlen süllyedővé tesszük. Minden régi mosogatóból végtelen kapacitású éleket adunk a T-hez.

Irányítatlan élek

Minden irányítatlan élt (u, v) egy pár irányított él (u, v) és (v, u) helyettesít.

Vertex Bandwidth Limit

Minden korlátozott kapacitású v csúcsot felosztunk két v be és v ki csúcsra . A felosztás előtt a v-ben szereplő összes él szerepel a v -ben . Minden él, amely v-ből származott a felosztás előtt, most v- ből származik . Adjon hozzá egy élt (v be , v out ) kapacitással . $önéletrajz}$ $önéletrajz}$

Az élek kapacitásának korlátozása alulról

A problémafelvetés ezen verziójában az egyes élek áramlásának értékét alulról a függvény is korlátozza . Így az áramlási érték egyetlen élre sem haladhatja meg a kapacitását, de nem lehet kisebb a megadott minimumnál, pl. . A probléma megoldásához az eredeti közlekedési hálózatot közlekedési hálózattá kell átalakítani az alábbiak szerint: ${\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'')$

Új forrás és mosogató hozzáadása . $s'$ $t'$
Minden élhez : $(v,w)$
1. Hozzon létre két új csúcsot és . $x$ $y$
2. Telepítse és . $c''(v,x)=c(v,w)$ $c''(y,w)=c(v,w)$
3. Telepítse . $c''(x,y)=c(v,w)-c'(v,w)$
4. Telepítse és . $c''(s',y)=c'(v,w)$ $c''(x,t')=c'(v,w)$
Telepítse . $c''(t,t')=c''(s,s')=\sum _{e\in E}c(e)$

Olyan áramlást határozunk meg a B-ben, amely akkor és csak akkor teljesíti az élek áteresztőképességének alulról történő korlátozására vonatkozó feltételt, ha olyan maximális áramlás van definiálva, amelyben az és az összes éle „telített”. Ennek a konstrukciónak köszönhetően az alulról határolt folyam megtalálásának algoritmusa a következő lesz: $G$ $G'$ ${\megjelenítési stílus (s',y)}$ $(x,t')$

Az építésből . $G$ $G'$
Keresse meg a gráf áramlását , előnyben részesítve az űrlap éleit és a . $f'$ $G'$ ${\megjelenítési stílus (s',y)}$ $(x,t')$
Ha , hol van a gráf folyama, amelyben az alábbi élek sávszélessége kimarad, akkor nincs megoldás. $f'<f''+\sum _{e\in E(G)}c'(e)$ $f''$ $G$
Ellenkező esetben számítsa ki az áramlást az áramlásból , pl. . $f$ $f'$ $f(a,b)=f(a,x)$

Az élkapacitás alulról történő korlátozása egy alternatívával

A feladatnak ez a változata megegyezik az előzővel, azzal a különbséggel, hogy az egyes élek áramlási értéke egyenlő is lehet -vel , azaz. vagy . A feltétel enyhe változása ellenére nincs polinomiális megoldás erre a problémára, ha a P és NP osztályok nem egyenlőek . Az állítás bizonyítására az Exact-3-SAT probléma polinomiális redukcióját adhatjuk . $0$ $c'(e)\leqslant f(e)\leqslant c(e)$ $f(e)=0$

Lásd még

Jegyzetek

↑ John J. O'Connor és Edmund F. Robertson . George Dantzig (angol) egy életrajz a MacTutor archívumában .
↑ Cottle, Richard; Johnson, Ellis; Wets, Roger, "George B. Dantzig (1914-2005)" Archiválva : 2015. szeptember 7., a Wayback Machine , Notices of the American Mathematical Society , v.54, no.3, 2007. március. Vö. 348. o
↑ 1 2 Hardesty, Larry, "Az alapvető algoritmus első javítása 10 év alatt" Archiválva : 2014. március 28., a Wayback Machine , MIT News Office, 2010. szeptember 27.
↑ Borndörfer, Ralf; Grotschel, Martin; Löbel, Andreas, "Alcuin's Transportation Problems and Integer Programing" Archiválva : 2011. augusztus 7., a Wayback Machine , Konrad-Zuse-Zentrum für Informationstechnik , Berlin, Németország, 1995. november. Vö. 3. o
↑ Powell, Stewart M., "The Berlin Airlift" , Air Force Magazine , 1998. június.
↑ Dantzig, GB, "Application of the Simplex Method to a Transportation Problem" Archiválva : 2010. július 19. a Wayback Machine -nél , in TC Koopman (szerk.): 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), 399-404.
↑ Ford, LR, Jr.; Fulkerson, D.R., Flows in Networks , Princeton University Press (1962).
↑ Kelner, Jonathan, "Elektromos áramlások, laplaci rendszerek és a maximális áramlás gyorsabb közelítése irányítatlan grafikonokban" Archiválva : 2011. június 24., a Wayback Machine , beszélgetés a CSAIL-nél, MIT, 2010. szeptember 28., kedd
↑ Elektromos áramlások, laplaci rendszerek és a maximális áramlás gyorsabb közelítése irányítatlan grafikonokon Archiválva 2010. november 29-én a Wayback Machine -nél , Paul Cristiano et al., 2010. október 19..
↑ Dinits algoritmus . Letöltve: 2010. október 28. Az eredetiből archiválva : 2015. május 7.. (неопр.)

Irodalom

Schrijver, Alexander, "A szállítás és a maximális áramlási problémák történetéről" , Mathematical Programming 91 (2002) 437-445
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algorithms: construction and analysis = Introduction to Algorithms / Szerk. I. V. Krasikova. - 2. kiadás - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 . . 26. fejezet
↑ Andrew V. Goldberg és S. Rao . Beyond the flow decomposition barrier (neopr.) // J. Assoc. Comput. Mach.. - 1998. - T. 45 . - S. 753-782 . - doi : 10.1145/290179.290181 .
↑ Andrew V. Goldberg és Robert E. Tarjan . A maximum-flow probléma új megközelítése (angol) // Journal of the ACM : Journal. - ACM Press, 1988. - Vol. 35 , sz. 4 . - P. 921-940 . — ISSN 0004-5411 . - doi : 10.1145/48014.61051 .
↑ Joseph Cheriyan és Kurt Mehlhorn . A preflow-push max-flow algoritmus legmagasabb szintű kiválasztási szabályának elemzése // Information Processing Letters : folyóirat. - 1999. - 1. évf. 69 , sz. 5 . - P. 239-242 . - doi : 10.1016/S0020-0190(99)00019-8 .
↑ Daniel D. Sleator és Robert E. Tarjan . Adatstruktúra dinamikus fákhoz (angol) // Journal of Computer and System Sciences : folyóirat. - 1983. - 1. évf. 26 , sz. 3 . - P. 362-391 . — ISSN 0022-0000 . - doi : 10.1016/0022-0000(83)90006-5 .
↑ Daniel D. Sleator és Robert E. Tarjan . Önbeállító bináris keresőfák (angol) // Journal of the ACM : Journal. - ACM Press, 1985. - Vol. 32 , sz. 3 . - P. 652-686 . — ISSN 0004-5411 . - doi : 10.1145/3828.3835 .
Eugene Lawler 4. Hálózati áramlások // Kombinatorikus optimalizálás: Networks and Matroids (angol) . - Dover, 2001. - P. 109-177. — ISBN 0486414531 .