Suurin virtausongelma

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 29.9.2020 tarkistetusta versiosta . tarkastukset vaativat 11 muokkausta .

Optimointiteoriassa ja graafiteoriassa maksimivirtausongelmana on löytää sellainen virtaus kuljetusverkon läpi , että lähteestä tulevien virtausten summa tai vastaavasti nielulle menevien virtausten summa on maksimi .

Maksimivirtausongelma on erikoistapaus vaikeammista ongelmista, kuten kiertohäiriöstä .

Historia

Kun Yhdysvallat astui toiseen maailmansotaan vuonna 1941, matemaatikko George Bernard Dantzig liittyi Yhdysvaltain ilmavoimien tilastotoimistoon Washington DC :ssä . Vuodesta 1941 vuoteen 1946 hän johti Combat Analysis Branchia, jossa hän työskenteli erilaisten matemaattisten ongelmien parissa. [1] [2] Myöhemmin, Danzigin työn avulla, maksimivirtausongelma ratkaistiin ensin ilmasillan valmistelun aikana Länsi-Berliinin saarron aikana , joka tapahtui vuosina 1948-1949. [3] [4] [5]

Vuonna 1951 George Dantzig muotoili ensimmäisen kerran ongelman yleisesti. [6]

Vuonna 1955 Lester Ford ja Delbert Ray Fulkerson rakensivat ensimmäisen algoritmin, joka oli erityisesti suunniteltu ratkaisemaan tämä ongelma . Heidän algoritmiaan kutsuttiin Ford-Fulkerson-algoritmiksi . [7] [8]

Jatkossa ongelman ratkaisua parannettiin monta kertaa.

Vuonna 2010 tutkijat Jonathan Kelner ja Aleksander Mądry MIT :stä sekä kollegansa Daniel Spielman Yalen yliopistosta ja Shen- Hua Teng Etelä -Kalifornian yliopistosta osoittivat toisen parannuksen algoritmiin ensimmäistä kertaa 10 vuoteen. [3] [9] [10]

Määritelmä

Kun otetaan huomioon liikenneverkko , jossa on lähde , nielu ja kapasiteetti . $N=(V,E)$ $s\in V$ $t\in V$ $c$

Virtauksen arvo on lähteestä lähtevien virtojen summa . Artikkelissa " Liikenneverkko " todistetaan , että se on yhtä suuri kuin viemäriin menevien virtausten summa .

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

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

Maksimivirtauksen ongelmana on löytää sellainen virtaus, jossa virtauksen arvo on maksimi.

Päätökset

Seuraavassa taulukossa on lueteltu joitakin algoritmeja ongelman ratkaisemiseksi.

Menetelmä	Monimutkaisuus	Kuvaus
Lineaarinen ohjelmointi	Riippuu tietystä algoritmista. Simplex -menetelmässä se on eksponentiaalinen.	Esitä maksimivirtausongelma lineaarisena ohjelmointitehtävänä. Muuttujat ovat virtaukset reunoja pitkin ja rajoituksia ovat virtauksen säilyminen ja läpimenon rajoittaminen.
Ford-Fulkerson-algoritmi	Riippuu lisäävän polun hakualgoritmista. Vaatii tällaisia hakuja. $O(\max \|f\|)$	Etsi mikä tahansa lisäävä polku. Lisää virtausta sen kaikkia reunoja pitkin niiden jäännöskapasiteetin vähimmäismäärällä. Toista niin kauan kuin lisäävä polku on olemassa. Algoritmi toimii vain kokonaislukujen kaistanleveyksillä. Muuten se voi jatkua loputtomiin ilman, että se konvergoi oikeaan vastaukseen.
Edmonds-Karp-algoritmi	$O(\|V\|\|E\|^{2})$	Suoritamme Ford-Fulkerson-algoritmin ja valitsemme joka kerta lyhimmän lisäyspolun (löytyy leveyshaulla ).
Dinitin algoritmi	$O(\|V\|^{2}\|E\|)$ tai yksikkökapasiteeteille käyttämällä Slethorin ja Tarjanin dynaamisia puita [11] $O(\|V\|\surd \|E\|)$ $O(\|V\|\|E\|\log(\|V\|))$	Edmonds-Karp-algoritmin parannus (mutta kronologisesti löydetty aiemmin). Jokaisessa iteraatiossa määritämme etäisyydet lähteestä kaikkiin jäännösverkon kärkiin käyttämällä leveyshakua. Rakennamme graafin, joka sisältää vain ne jäännösverkon reunat, joilla tämä etäisyys kasvaa 1:llä. Jätetään graafista pois kaikki umpikujapisteet, joiden reunat osuvat niihin, kunnes kaikki kärjet muuttuvat ei-umpikuiksi. (Umpikuja on kärki, paitsi lähde ja nielu, joka ei sisällä yhtä reunaa tai josta ei tule yhtään reunaa.) Tuloksena olevasta graafista löydämme lyhimmän lisäyspolun (se on mikä tahansa polku s:stä kohtaan t). Jätetään pois jäännösverkosta reuna, jolla on pienin kapasiteetti, jätetään jälleen pois umpikujapisteet ja niin edelleen, kunnes on olemassa lisäyspolku.
Preflow Push Algorithm	$O(\|V\|^{2}\|E\|)$	Toimii esivirtauksella virran sijaan. Erona on se, että missä tahansa kärjessä u, paitsi lähde ja nielu, siihen tulevien virtausten summan tulee olla tiukasti nolla (virtauksen säilymisehto) ja esivirtauksen osalta sen ei-negatiivinen. Tätä summaa kutsutaan ylivirtaukseksi kärkeen, ja huippupisteen, jolla on positiivinen ylivirtaus, sanotaan olevan ylivuoto . Lisäksi algoritmi tallentaa jokaiselle kärjelle lisäominaisuuden, korkeuden , joka on ei-negatiivinen kokonaisluku. Algoritmi käyttää kahta operaatiota: push , kun virtausta pitkin ylemmästä alempaan kärkeen menevää reunaa kasvatetaan suurimmalla mahdollisella määrällä ja lift , kun nostetaan ylivuotava kärki, josta työntäminen on mahdotonta riittämättömän korkeuden vuoksi. . Työntäminen on mahdollista, kun reuna kuuluu jäännösverkkoon, johtaa korkeammasta kärjestä alempaan ja alkuperäinen kärki on ylivuoto. Nosto on mahdollista, kun nostettava kärki on täynnä, mutta yksikään kärkipisteistä, joihin jäännösverkon reunat johtavat siitä, ei ole sitä alempana. Se suoritetaan korkeudelle, joka on 1 suurempi kuin näiden kärkien korkeuksien minimi. Aluksi lähteen korkeus on V, kaikkia lähteestä lähteviä reunoja pitkin suurimmat mahdolliset virtaukset ja loput korkeudet ja virtaukset ovat nollia. Työntö- ja nostotoiminnot suoritetaan niin kauan kuin mahdollista.
Algoritmi "nostaa alkuun"	$O(\|V\|^{3})$ tai käyttämällä dynaamisia puita $O(\|V\|\|E\|\log(\|V\|^{2}/\|E\|))$	Edellisen algoritmin muunnelma, joka määrittää työntö- ja nostotoimintojen järjestyksen erityisellä tavalla.
Binäärinen estovirtaalgoritmi [1]	$O(\|E\|\min\{\|V\|^{2/3},\surd {\|E\|}\}\log(\|V\|^{2}/\|E\|)\log(\ max \|f\|))$

Katso tarkempi luettelo kohdista [2] ja Luettelo algoritmeista maksimivirtauksen löytämiseksi .

Koko virtauslause

Jos läpimenot ovat kokonaislukuja, myös maksimivirtaus on kokonaisluku.

Lause seuraa esimerkiksi Ford–Fulkersonin lausetta .

Yleistykset, jotka pelkistyvät alkuperäiseen ongelmaan

Jotkut maksimivirtausongelman yleistykset voidaan helposti pelkistää alkuperäiseen ongelmaan.

Mielivaltainen määrä lähteitä ja/tai nieluja

Jos lähdettä on useampi kuin yksi, lisää uusi kärkipiste S, josta teemme ainoan lähteen. Jokaiseen vanhaan lähteeseen lisätään reunat, joilla on ääretön kapasiteetti S:stä.

Vastaavasti, jos nieluja on useampi kuin yksi, lisäämme uuden kärjen T, josta teemme ainoan nielun. Lisäämme T:hen jokaisesta vanhasta pesualtaasta äärettömän kapasiteetin reunat.

Ohjaamattomat reunat

Jokainen suuntaamaton reuna (u, v) korvataan parilla suunnattuja reunoja (u, v) ja (v, u).

Vertex Bandwidth Limit

Jaamme kukin rajallisella kapasiteetilla oleva kärki v kahdeksi kärjeksi v sisään ja v ulos . Kaikki reunat, jotka sisältyvät v:ään ennen jakamista, sisältyvät nyt v : ään . Kaikki reunat, jotka olivat peräisin v:stä ennen jakamista, ovat nyt peräisin v: stä ulos . Lisää reuna (v in ,v out ), jonka kapasiteetti on . $CV}$ $CV}$

Reunojen kapasiteetin rajoittaminen alhaalta

Tässä tehtävänlauseen versiossa kunkin reunan virtauksen arvoa rajoittaa lisäksi alhaalta funktio . Siten minkään reunan virtausarvo ei voi ylittää sen kapasiteettia, mutta se ei voi olla pienempi kuin määritetty minimi, ts. . Ongelman ratkaisemiseksi on tarpeen muuttaa alkuperäinen liikenneverkko liikenneverkoksi seuraavasti: ${\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'')$

Lisää uusi lähde ja pesuallas . $s'$ $t'$
Jokaiselle reunalle : $(v, w)$
1. Luo kaksi uutta kärkeä ja . $x$ $y$
2. Asenna ja . $c''(v,x)=c(v,w)$ $c''(y,w)=c(v,w)$
3. Asenna . $c''(x,y)=c(v,w)-c'(v,w)$
4. Asenna ja . $c''(s',y)=c'(v,w)$ $c''(x,t')=c'(v,w)$
Asenna . $c''(t,t')=c''(s,s')=\sum _{e\in E}c(e)$

Kohdassa B määritellään virtaus, joka täyttää ehdon reunojen läpimenon rajoittamisesta alhaalta, jos ja vain, jos on määritelty maksimivirtaus, jossa kaikki muodon ja reunat ovat "kylläisiä". Tämän rakenteen ansiosta algoritmi alhaalta rajatun virtauksen löytämiseksi on seuraava: $G$ $G'$ ${\näyttötyyli (s',y)}$ ${\näyttötyyli (x,t')}$

Rakentamisesta lähtien . $G$ $G'$
Etsi graafin virtaus mieluummin muodon reunat ja . $f'$ $G'$ ${\näyttötyyli (s',y)}$ ${\näyttötyyli (x,t')}$
Jos , missä on graafin kulku, jossa alla olevien reunojen kaistanleveys on jätetty pois, niin ratkaisua ei ole. $f'<f''+\sum _{e\in E(G)}c'(e)$ $f''$ $G$
Muussa tapauksessa laske virtaus virtauksesta , ts. . $f$ $f'$ $f(a,b)=f(a,x)$

Reunakapasiteetin rajoittaminen alhaalta vaihtoehdolla

Tämä tehtävän muunnos on identtinen edellisen kanssa sillä erolla, että kullekin reunalle virtausarvo voi olla myös yhtä suuri , ts. tai . Huolimatta pienestä ehdon muutoksesta, tähän ongelmaan ei ole polynomiratkaisua, jos luokat P ja NP eivät ole samat . Todisteeksi väitteelle voidaan antaa polynomipelkistys Exact-3-SAT- ongelmalle . $0$ $c'(e)\leqslant f(e)\leqslant c(e)$ $f(e)=0$

Katso myös

Muistiinpanot

↑ John J. O'Connor ja Edmund F. Robertson . George Dantzig (englanniksi) on elämäkerta MacTutor- arkistossa .
↑ Cottle, Richard; Johnson, Ellis; Wets, Roger, "George B. Dantzig (1914-2005)" Arkistoitu 7. syyskuuta 2015 Wayback Machinessa , Notices of the American Mathematical Society , v.54, no.3, maaliskuu 2007. Ks. s. 348
↑ 1 2 Hardesty, Larry, "Ensimmäinen perusalgoritmin parannus 10 vuoden aikana" Arkistoitu 28. maaliskuuta 2014 Wayback Machinessa , MIT News Office, 27. syyskuuta 2010
↑ Borndörfer, Ralf; Grotschel, Martin; Löbel, Andreas, "Alcuin's Transportation Problems and Integer Programming" Arkistoitu 7. elokuuta 2011 Wayback Machinessa , Konrad-Zuse-Zentrum für Informationstechnik , Berliini, Saksa, marraskuu 1995. Ks. s.3
↑ Powell, Stewart M., "The Berlin Airlift" , Air Force Magazine , kesäkuu 1998.
↑ Dantzig, GB, "Application of the Simplex Method to a Transportation Problem" Arkistoitu 19. heinäkuuta 2010 Wayback Machinessa , julkaisussa TC Koopman (toim.): 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 indirected Graphs" Arkistoitu 24. kesäkuuta 2011 Wayback Machinessa , keskustelu CSAILissa, MIT, tiistai, 28. syyskuuta 2010
↑ Sähkövirrat, Laplacian-järjestelmät ja nopeampi maksimivirtauksen arvioiminen ohjaamattomissa kaavioissa Arkistoitu 29. marraskuuta 2010 Wayback Machinessa , Paul Cristiano et al., 19. lokakuuta 2010.
↑ Dinits-algoritmi . Haettu 28. lokakuuta 2010. Arkistoitu alkuperäisestä 7. toukokuuta 2015. (määrätön)

Kirjallisuus

Schrijver, Alexander, "Kuljetus- ja maksimivirtausongelmien historiasta" , Mathematical Programming 91 (2002) 437-445
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmit: rakentaminen ja analyysi = Introduction to Algorithms / Ed. I. V. Krasikova. - 2. painos - M .: Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 . . Luku 26
↑ Andrew V. Goldberg ja S. Rao . Beyond the flow hajoamisesteen (neopr.) // J. Assoc. Comput. Mach.. - 1998. - T. 45 . - S. 753-782 . - doi : 10.1145/290179.290181 .
↑ Andrew V. Goldberg ja Robert E. Tarjan . Uusi lähestymistapa maksimivirtausongelmaan (englanniksi) // Journal of the ACM : Journal. - ACM Press, 1988. - Voi. 35 , ei. 4 . - s. 921-940 . — ISSN 0004-5411 . - doi : 10.1145/48014.61051 .
↑ Joseph Cheriyan ja Kurt Mehlhorn . Analyysi korkeimman tason valintasäännöstä preflow-push max-flow -algoritmissa // Information Processing Letters : päiväkirja. - 1999. - Voi. 69 , ei. 5 . - s. 239-242 . - doi : 10.1016/S0020-0190(99)00019-8 .
↑ Daniel D. Sleator ja Robert E. Tarjan . Tietorakenne dynaamisille puille (englanniksi) // Journal of Computer and System Sciences : päiväkirja. - 1983. - Voi. 26 , nro. 3 . - s. 362-391 . — ISSN 0022-0000 . - doi : 10.1016/0022-0000(83)90006-5 .
↑ Daniel D. Sleator ja Robert E. Tarjan . Itsesäätyvät binaariset hakupuut (englanniksi) // Journal of the ACM : Journal. - ACM Press, 1985. - Voi. 32 , ei. 3 . - s. 652-686 . — ISSN 0004-5411 . - doi : 10.1145/3828.3835 .
Eugene Lawler 4. Verkkovirrat // Kombinatorinen optimointi: verkot ja matroidit (englanti) . - Dover, 2001. - P. 109-177. — ISBN 0486414531 .