Problém s maximálním průtokem - Maximum flow problem

Tok sítě pro problém: Každý člověk (ri) je ochoten adoptovat kočku (wi1) a / nebo psa (wi2). Každé zvíře (stri) dává přednost pouze podmnožině lidí. Najděte jakoukoli shodu mazlíčků s lidmi tak, aby maximální počet mazlíčků přijal jeden z jejích preferovaných lidí.

v teorie optimalizace, problémy s maximálním průtokem zahrnovat nalezení proveditelného toku přes a toková síť který získá maximální možný průtok.

Na problém s maximálním tokem lze pohlížet jako na speciální případ složitějších problémů s tokem v síti, jako je problém oběhu. Maximální hodnota s-t toku (tj. Toku z zdroj s až dřez t) se rovná minimální kapacitě s-t řez (tj. odřízněte oddělování s od t) v síti, jak je uvedeno v věta o maximálním toku o minimálním řezu.

Dějiny

Problém s maximálním průtokem byl poprvé formulován v roce 1954 T. E. Harris a F. S. Ross jako zjednodušený model toku sovětské železniční dopravy.^[1]^[2]^[3]

V roce 1955 Lester R. Ford, Jr. a Delbert R. Fulkerson vytvořil první známý algoritmus, Algoritmus Ford-Fulkerson.^[4]^[5] Ve svém příspěvku z roku 1955^[4] Ford a Fulkerson napsali, že problém Harrisa a Rosse je formulován následovně (viz^[1] p. 5):

Zvažte železniční síť spojující dvě města prostřednictvím řady mezilehlých měst, kde každé propojení sítě má přiděleno číslo představující její kapacitu. Za předpokladu ustáleného stavu najděte maximální tok z jednoho daného města do druhého.

Ve své knize Toky v síti,^[5] v roce 1962 Ford a Fulkerson napsali:

Autorům ji položil na jaře 1955 T.E. Harris, který ve spojení s generálem F.S. Ross (Ret.), Formuloval zjednodušený model toku železniční dopravy a určil tento konkrétní problém jako ústřední problém navržený modelem [11].

kde [11] odkazuje na tajnou zprávu z roku 1955 Základy metody pro hodnocení kapacit železniční sítě Harris a Ross^[3] (vidět^[1] p. 5).

V průběhu let byla objevena různá vylepšená řešení problému maximálního průtoku, zejména nejkratší algoritmus rozšiřující cesty Edmondse a Karpa a nezávisle Dinitze; algoritmus blokujícího toku Dinitz; the algoritmus push-relabel z Goldberg a Tarjan; a algoritmus binárního blokovacího toku Goldberga a Raa. Algoritmy Shermana^[6] a Kelner, Lee, Orecchia a Sidford,^[7]^[8] najděte přibližně optimální maximální průtok, ale pracujte pouze v neorientovaných grafech.

V roce 2013 James B. Orlin zveřejnil článek popisující ${ displaystyle O (| V || E |)}$ algoritmus pro všechny hodnoty ${ displaystyle | V |}$ a ${ displaystyle | E |}$ .^[9]

Definice

Průtoková síť se zdrojem s a umyvadlo t. Čísla vedle okraje jsou kapacity.

Nejprve vytvoříme notaci:

Nechat ${ displaystyle N = (V, E)}$ být sítí s ${ displaystyle s, t ve V}$ být zdrojem a jímkou ${ displaystyle N}$ resp.
Li ${ displaystyle g}$ je funkce na okrajích ${ displaystyle N}$ pak jeho hodnota na ${ displaystyle (u, v) v E}$ je označen ${ displaystyle g_ {uv}}$ nebo ${ displaystyle g (u, v).}$

Definice. The kapacita hrany je maximální množství toku, které může projít hranou. Formálně je to mapa ${ displaystyle c: E to mathbb {R} ^ {+}.}$

Definice. A tok je mapa ${ displaystyle f: E to mathbb {R} ^ {+}}$ který splňuje následující podmínky:

Omezení kapacity. Tok hrany nesmí překročit její kapacitu, jinými slovy: ${ displaystyle f_ {uv} leq c_ {uv}}$ pro všechny ${ displaystyle (u, v) v E.}$
Zachování toků. Součet toků vstupujících do uzlu se musí rovnat součtu toků opouštějících tento uzel, s výjimkou zdroje a jímky. Nebo:

{ displaystyle forall v in V setminus {s, t }: quad součet _ {u: (u, v) v E} f_ {uv} = součet _ {u: (v, u) in E} f_ {vu}.}

Poznámka. Toky jsou zkosené symetrické: ${ displaystyle f_ {uv} = - f_ {vu}}$ pro všechny ${ displaystyle (u, v) v E.}$

Definice. The hodnota průtoku je množství toku procházejícího ze zdroje do jímky. Formálně pro tok ${ displaystyle f: E to mathbb {R} ^ {+}}$ je to dáno:

{ displaystyle | f | = součet _ {v: (s, v) v E} f_ {sv}.}

Definice. The problém s maximálním průtokem je směrovat co nejvíce toku ze zdroje ke dřezu, jinými slovy najít tok ${ displaystyle f _ { textrm {max}}}$ s maximální hodnotou.

Všimněte si, že může existovat několik maximálních toků, a pokud jsou povoleny libovolné skutečné (nebo dokonce libovolné racionální) hodnoty toku (místo pouze celých čísel), existuje buď právě jeden maximální tok, nebo nekonečně mnoho, protože existuje nekonečně mnoho lineárních kombinací základní maximální průtoky. Jinými slovy, pokud pošleme ${ displaystyle x}$ jednotky toku na hraně ${ displaystyle u}$ v jednom maximálním průtoku a ${ displaystyle y> x}$ jednotky toku zapnuty ${ displaystyle u}$ v jiném maximálním průtoku, pak pro každý ${ displaystyle Delta v [0, y-x]}$ můžeme poslat ${ displaystyle x + Delta}$ jednotky zapnuty ${ displaystyle u}$ a podle toho směrujte tok na zbývajících okrajích, abyste získali další maximální průtok. Pokud mohou být hodnoty toku libovolná reálná nebo racionální čísla, je jich nekonečně mnoho ${ displaystyle Delta}$ hodnoty pro každý pár ${ displaystyle x, y}$ .

Algoritmy

V následující tabulce jsou uvedeny algoritmy pro řešení problému s maximálním průtokem.

Metoda	Složitost	Popis
Lineární programování		Omezení daná definicí a legální tok. Viz lineární program tady.
Algoritmus Ford-Fulkerson	$Ó (E \| F max \|)$	Pokud je ve zbytkovém grafu otevřená cesta, pošlete na ní minimum zbytkových kapacit. Algoritmus je zaručeně ukončen, pouze pokud jsou všechny váhy Racionální.^{[je třeba další vysvětlení ]} Jinak je možné, že algoritmus nebude konvergovat na maximální hodnotu. Pokud se však algoritmus ukončí, je zaručeno najít maximální hodnotu.
Algoritmus Edmonds – Karp	$Ó (VE 2)$	Specializace Ford-Fulkerson, hledání rozšiřujících cest s vyhledávání na šířku.
Dinicův blokovací algoritmus toku	$Ó (PROTI 2 E)$	V každé fázi algoritmy vytvářejí vrstvený graf s vyhledávání na šířku na zbytkový graf. Maximální průtok ve vrstveném grafu lze vypočítat v $Ó (VE)$ čas a maximální počet fází je $PROTI -1$ . V sítích s jednotkovými kapacitami končí Dinicův algoritmus ${ displaystyle O ( min {V ^ {2/3}, E ^ {1/2} } E)}$ čas.
Algoritmus MKM (Malhotra, Kumar, Maheshwari)^[10]	$Ó (PROTI 3)$	Funguje pouze v acyklických sítích. Odkazovat na originální papír.
Dinicův algoritmus	$Ó (VE log PROTI)$	The dynamické stromy datová struktura zrychluje výpočet maximálního toku ve vrstveném grafu na $Ó (VE log PROTI)$ .
Obecný algoritmus maximálního toku push-relabel	$Ó (PROTI 2 E)$	Algoritmus push relabel udržuje preflow, tj. Funkci toku s možností přebytku ve vrcholech. Algoritmus běží, zatímco v grafu je vrchol s kladným přebytkem, tj. Aktivní vrchol. Operace tlačení zvyšuje průtok na zbytkové hraně a výšková funkce na vrcholech řídí, které zbytkové hrany lze tlačit. Funkce výšky se změní pomocí operace relabelu. Správné definice těchto operací zaručují, že výsledná funkce toku je maximální tok.
Algoritmus push-relabel s FIFO pravidlo výběru vrcholu	$Ó (PROTI 3)$	Varianta algoritmu push-relabel, která vždy vybírá naposledy aktivní vrchol a provádí operace push, dokud není přebytek pozitivní nebo nejsou z tohoto vrcholu přípustné zbytkové hrany.
Algoritmus push-relabel s dynamickými stromy	${ displaystyle O left (VE log { frac {V ^ {2}} {E}} right)}$	Algoritmus staví stromy omezené velikosti na zbytkovém grafu týkajícím se funkce výšky. Tyto stromy poskytují víceúrovňové operace push.
Algoritmus KRT (King, Rao, Tarjan)^[11]	${ displaystyle O (VE log _ { frac {E} {V log V}} V)}$
Algoritmus toku binárního blokování^[12]	${ displaystyle O left (E cdot min (V ^ { frac {2} {3}}, { sqrt {E}}) cdot log { frac {V ^ {2}} {E }} log {U} vpravo)}$	Hodnota U odpovídá maximální kapacitě sítě.
Algoritmus KRT (King, Rao, Tarjan) od Jamese B Orlina^[9]	${ displaystyle O (VE)}$	Orlinův algoritmus řeší maximální průtok dovnitř $Ó (VE)$ čas na ${ displaystyle E leq O (V ^ {{16 nad 15} - epsilon})}$ zatímco KRT to vyřeší $Ó (VE)$ pro ${ displaystyle E> V ^ {1+ epsilon}}$ .

Rozsáhlejší seznam viz Goldberg & Tarjan (1988).

Věta o integrálním toku

Věta o integrálním toku to říká

Pokud má každá hrana v síti toku integrální kapacitu, pak existuje integrální maximální tok.

aplikace

Problém s maximálním průtokem více zdrojů s více dřezy

Obr. 4.1.1. Transformace problému maximálního toku s více zdroji s více jímkami na problém s maximálním tokem s jedním zdrojem s jedním dřezem

Vzhledem k síti ${ displaystyle N = (V, E)}$ se sadou zdrojů ${ displaystyle S = {s_ {1}, ldots, s_ {n} }}$ a sada umyvadel ${ displaystyle T = {t_ {1}, ldots, t_ {m} }}$ místo pouze jednoho zdroje a jednoho jímky musíme najít maximální průtok napříč ${ displaystyle N}$ . Můžeme transformovat problém s více zdroji s více jímkami na problém s maximálním tokem přidáním a konsolidovaný zdroj připojení ke každému vrcholu v ${ displaystyle S}$ a a konsolidovaný dřez spojeny každým vrcholem v ${ displaystyle T}$ (také známý jako supersource a supersink) s nekonečnou kapacitou na každém okraji (viz obr. 4.1.1.).

Minimální pokrytí cesty v směrovaném acyklickém grafu

Vzhledem k směrovaný acyklický graf ${ displaystyle G = (V, E)}$ , musíme najít minimální počet vrcholové disjunktní cesty pokrýt každý vrchol v ${ displaystyle V}$ . Můžeme sestrojit bipartitní graf ${ displaystyle G '= (V _ { textrm {out}} pohár V _ { textrm {in}}, E')}$ z ${ displaystyle G}$ , kde

${ displaystyle V _ { textrm {out}} = {v _ { textrm {out}} vert v ve V land v { text {má pozitivní out-stupeň}} }}$
${ displaystyle V _ { textrm {in}} = {v _ { textrm {in}} vert v ve V land v { text {má pozitivní stupeň}} }}$
${ displaystyle E '= {(u _ { textrm {out}}, v _ { textrm {in}}) v V_ {out} krát V_ {v} vert (u, v) v E}}$ .

Poté lze zobrazit pomocí Kőnigova věta, že ${ displaystyle G '}$ má shodu ${ displaystyle M}$ velikosti ${ displaystyle m}$ kdyby a jen kdyby ${ displaystyle G}$ má vrcholový disjunktní kryt cesty ${ displaystyle C}$ velikosti ${ displaystyle n-m}$ , kde ${ displaystyle n}$ je počet vrcholů v ${ displaystyle G}$ . Proto lze problém vyřešit nalezením maximální shody mohutnosti v ${ displaystyle G '}$ namísto.

Intuitivně, pokud dva vrcholy ${ displaystyle u _ { mathrm {out}}, v _ { mathrm {in}}}$ jsou spárovány ${ displaystyle M}$ , pak okraj ${ displaystyle (u, v)}$ je obsažen v ${ displaystyle C}$ . To vidět ${ displaystyle C}$ je vrchol-disjunktní, zvažte následující:

Každý vrchol ${ displaystyle v _ { textrm {out}}}$ v ${ displaystyle G '}$ může být neodpovídající v ${ displaystyle M}$ , v takovém případě nezůstanou žádné hrany ${ displaystyle v}$ v ${ displaystyle C}$ ; nebo může být uzavřeno, v takovém případě zbývá právě jedna hrana ${ displaystyle v}$ v ${ displaystyle C}$ . V obou případech žádný vrchol neopustí více než jedna hrana ${ displaystyle v}$ v ${ displaystyle C}$ .
Podobně pro každý vrchol ${ displaystyle v _ { textrm {in}}}$ v ${ displaystyle G '}$ - pokud je uzavřeno, je do něj jediná příchozí hrana ${ displaystyle v}$ v ${ displaystyle C}$ ; v opačném případě ${ displaystyle v}$ nemá v sobě žádné příchozí hrany ${ displaystyle C}$ .

Žádný vrchol tedy nemá dva příchozí nebo dva odchozí okraje ${ displaystyle C}$ , což znamená všechny cesty v ${ displaystyle C}$ jsou vrchol-disjunktní.

Bipartitní shoda s maximální mohutností

Obr. 4.3.1. Transformace problému maximálního bipartitního párování na problém maximálního toku

Vzhledem k bipartitní graf ${ displaystyle G = (X pohár Y, E)}$ , musíme najít a maximální shoda mohutnosti v ${ displaystyle G}$ , to je shoda, která obsahuje největší možný počet hran. Tento problém lze přeměnit na problém s maximálním tokem vytvořením sítě ${ displaystyle N = (X pohár Y pohár {s, t }, E ')}$ , kde

${ displaystyle E '}$ obsahuje hrany v ${ displaystyle G}$ režie od ${ displaystyle X}$ na ${ displaystyle Y}$ .
${ displaystyle (s, x) v E '}$ pro každého ${ displaystyle x v X}$ a ${ displaystyle (y, t) v E '}$ pro každého ${ displaystyle y v Y}$ .
${ displaystyle c (e) = 1}$ pro každého ${ displaystyle e in E '}$ (Viz obr. 4.3.1).

Pak hodnota maximálního průtoku dovnitř ${ displaystyle N}$ se rovná velikosti maximální shody v ${ displaystyle G}$ .

Maximální průtok s kapacitami vrcholů

Obr. 4.4.1. Transformace problému maximálního průtoku s omezením kapacit vrcholů na původní problém maximálního průtoku rozdělením uzlů

Nechat ${ displaystyle N = (V, E)}$ být sítí. Předpokládejme, že v každém uzlu je kromě kapacity hrany také kapacita, tj. Mapování ${ displaystyle c: V to mathbb {R} ^ {+},}$ tak, že tok ${ displaystyle f}$ musí uspokojit nejen omezení kapacity a zachování toků, ale také omezení kapacity vrcholů

{ displaystyle sum _ {i v V} f_ {iv} leq c (v) qquad forall v v V zpětné lomítko {s, t }.}

Jinými slovy, množství toku procházejícího vrcholem nemůže překročit jeho kapacitu. Chcete-li zjistit maximální průtok napříč ${ displaystyle N}$ , můžeme problém transformovat na problém maximálního toku v původním smyslu rozšířením ${ displaystyle N}$ . Nejprve každý ${ displaystyle v ve V}$ je nahrazen ${ displaystyle v _ { text {in}}}$ a ${ displaystyle v _ { text {out}}}$ , kde ${ displaystyle v _ { text {in}}}$ je spojen hranami vstupujícími do ${ displaystyle v}$ a ${ displaystyle v _ { text {out}}}$ je připojen k hranám vycházejícím z ${ displaystyle v}$ , poté přiřaďte kapacitu ${ displaystyle c (v)}$ ke spojovací hraně ${ displaystyle v _ { text {in}}}$ a ${ displaystyle v _ { text {out}}}$ (viz obr. 4.4.1). V této rozšířené síti je omezení kapacity vrcholů odstraněno, a proto lze problém považovat za problém původního maximálního toku.

Maximální počet cest od s do t

Vzhledem k orientovanému grafu ${ displaystyle G = (V, E)}$ a dva vrcholy ${ displaystyle s}$ a ${ displaystyle t}$ , musíme najít maximální počet cest z ${ displaystyle s}$ na ${ displaystyle t}$ . Tento problém má několik variant:

1. Cesty musí být disjunktní. Tento problém lze transformovat na problém s maximálním tokem vytvořením sítě ${ displaystyle N = (V, E)}$ z ${ displaystyle G}$ , s ${ displaystyle s}$ a ${ displaystyle t}$ být zdrojem a jímkou ${ displaystyle N}$ a přiřazení každé hrany kapacitu ${ displaystyle 1}$ . V této síti je maximální tok ${ displaystyle k}$ pokud existují ${ displaystyle k}$ okrajové disjunktní cesty.

2. Cesty musí být nezávislé, tj. Vrchol-disjunkt (kromě ${ displaystyle s}$ a ${ displaystyle t}$ ). Můžeme postavit síť ${ displaystyle N = (V, E)}$ z ${ displaystyle G}$ s kapacitami vrcholů, kde jsou kapacity všech vrcholů a všech hran ${ displaystyle 1}$ . Pak se hodnota maximálního toku rovná maximálnímu počtu nezávislých cest od ${ displaystyle s}$ na ${ displaystyle t}$ .

3. Kromě cest, které jsou disjunktní od okraje a / nebo od vrcholu, mají cesty také omezení délky: počítáme pouze cesty, jejichž délka je přesně ${ displaystyle k}$ , nebo nanejvýš ${ displaystyle k}$ . Většina variant tohoto problému je NP-úplná, s výjimkou malých hodnot ${ displaystyle k}$ .^[13]

Problém s uzavřením

A uzavření směrovaného grafu je sada vrcholů Ctak, aby nezůstaly žádné hrany C. The problém s uzavřením je úkolem najít uzávěr maximální nebo minimální hmotnosti ve vertexově váženém orientovaném grafu. To lze vyřešit v polynomiálním čase pomocí redukce na problém s maximálním průtokem.

Skutečné aplikace

Eliminace baseballu

Konstrukce toku sítě pro problém eliminace baseballu

V baseball eliminační problém existuje n týmy soutěžící v lize. V určité fázi ligové sezóny w_i je počet výher a r_i je počet her zbývajících pro tým i a r_ij je počet zbývajících her proti týmu j. Tým je vyřazen, pokud nemá šanci dokončit sezónu na prvním místě. Úkolem problému eliminace baseballu je určit, které týmy jsou v sezóně vyřazeny v každém bodě. Schwartz^[14] navrhla metodu, která tento problém redukuje na maximální tok sítě. V této metodě je vytvořena síť k určení, zda tým k je vyloučeno.

Nechat G = (PROTI, E) být sítí s s,t ∈ PROTI je zdrojem a umyvadlem. Jeden přidá herní uzel {i,j} s i < j na PROTIa spojuje každou z nich z s o hranu s kapacitou r_ij - což představuje počet her mezi těmito dvěma týmy. Také přidáme týmový uzel pro každý tým a spojíme každý herní uzel {i,j} se dvěma týmovými uzly i a j zajistit, aby jeden z nich vyhrál. Není třeba omezovat hodnotu průtoku na těchto okrajích. Nakonec jsou hrany vytvořeny z uzlu týmu i do uzlu jímky t a kapacita w_k+r_k–w_i je nastaven tak, aby zabránil týmu i od vítězství více než w_k+r_k.Nechat S být souborem všech týmů účastnících se ligy a nechat ${ displaystyle scriptstyle r (S - {k }) = součet _ {i, j v {S - {k } }, i$ . V této metodě je to nárokovaný tým k není vyloučeno, právě když hodnota průtoku o velikosti r(S − {k}) v síti existuje G. V uvedeném článku je prokázáno, že tato hodnota průtoku je maximální hodnotou průtoku od s na t.

Plánování leteckých společností

V leteckém průmyslu je velkým problémem plánování letových posádek. Problém plánování leteckých společností lze považovat za aplikaci rozšířeného maximálního toku sítě. Vstupem tohoto problému je sada letů F který obsahuje informace o tom, kde a kdy každý let odlétá a přilétá. V jedné verzi plánování leteckých společností je cílem vytvořit proveditelný plán s maximálně k posádky.

K vyřešení tohoto problému se používá variace problém oběhu zvaný omezený oběh, což je zobecnění tok sítě problémy s přidaným omezením spodní hranice okrajových toků.

Nechat G = (PROTI, E) být sítí s s,t ∈ PROTI jako zdroj a uzly jímky. Pro zdroj a cíl každého letu i, jeden přidá dva uzly do PROTI, uzel s_i jako zdroj a uzel d_i jako cílový uzel letu i. Jeden také přidá následující hrany E:

Okraj s kapacitou [0, 1] mezi s a každý s_i.
Okraj s kapacitou [0, 1] mezi každým d_i a t.
Okraj s kapacitou [1, 1] mezi každou dvojicí s_i a d_i.
Okraj s kapacitou [0, 1] mezi každým d_i a s_j, pokud zdroj s_j je dosažitelný s přiměřeným časem a náklady z cíle letu i.
Hrana s kapacitou [0, ∞ ] mezi s a t.

Ve zmíněné metodě je tvrzeno a prokázáno, že zjištění hodnoty toku ve výši k v G mezi s a t se rovná nalezení proveditelného rozvrhu letové sady F maximálně k posádky.^[15]

Další verzí plánování leteckých společností je nalezení minimálního počtu posádek potřebných k provedení všech letů. Abychom našli odpověď na tento problém, bipartitní graf $G' = (A \cup B, E)$ je vytvořen tam, kde má každý let v sadě kopii A a nastavit B. Pokud stejné letadlo může provádět let j po letu i, i∈A je připojen k j∈B. Odpovídající $G'$ vyvolává plán pro F a samozřejmě maximální bipartitní shoda v tomto grafu vytváří letový řád s minimálním počtem posádek.^[15] Jak je uvedeno v aplikační části tohoto článku, bipartitní shoda s maximální mohutností je aplikací problému s maximálním tokem.

Problém oběhu a poptávky

Existují továrny, které vyrábějí zboží, a některé vesnice, kam je třeba zboží doručit. Jsou propojeny sítí silnic, přičemž každá silnice má kapacitu $C$ pro maximální zboží, které jím může protékat. Problém je zjistit, zda existuje oběh, který uspokojuje poptávku. Tento problém lze transformovat do problému maximálního průtoku.

Přidejte zdrojový uzel $s$ a přidejte z něj hrany do každého uzlu továrny $F i$ s kapacitou $str i$ kde $str i$ je rychlost výroby v továrně $F i$ .
Přidejte uzel jímky $t$ a přidejte hrany ze všech vesnic $proti i$ na $t$ s kapacitou $d i$ kde $d i$ je míra poptávky vesnice $proti i$ .

Nechat G = (PROTI, E) být touto novou sítí. Existuje oběh, který uspokojuje poptávku právě tehdy, když:

Maximální hodnota průtoku (G)

{ displaystyle = součet _ {i v v} d_ {i}}

.

Pokud existuje oběh, pohled na řešení maximálního toku by poskytl odpověď na to, kolik zboží musí být odesláno na konkrétní silnici, aby byly splněny požadavky.

Problém lze rozšířit přidáním spodní hranice toku na některých okrajích.^[16]

Segmentace obrazu

Zdrojový obrázek o velikosti 8x8.

Síť vytvořená z bitmapy. Zdroj je vlevo, umyvadlo vpravo. Čím je hrana tmavší, tím větší je její kapacita. A_i je vysoká, když je pixel zelený, b_i když pixel není zelený. Trest str_ij jsou si všichni rovni.^[17]

Ve své knize Kleinberg a Tardos představují algoritmus pro segmentaci obrazu.^[18] Představují algoritmus pro nalezení pozadí a popředí v obraze. Přesněji řečeno, algoritmus bere bitmapu jako vstup modelovaný takto: A_i ≥ 0 je pravděpodobnost, že pixel i patří do popředí, b_i ≥ 0 v pravděpodobnosti, že pixel i patří do pozadí a str_ij je trest, pokud jsou dva sousední pixely i a j jsou umístěny jeden v popředí a druhý v pozadí. Cílem je najít oddíl (A, B) sady pixelů, které maximalizují následující množství

{ displaystyle q (A, B) = součet _ {i v A} a_ {i} + součet _ {i v B} b_ {i} - součet _ { začátek {matice} i, j { text {sousední}} | A cap {i, j } | = 1 end {matrix}} p_ {ij}}

,

Ve skutečnosti pro pixely v A (považováno za popředí), získáváme A_i; pro všechny pixely v B (považováno za pozadí), získáváme b_i. Na hranici mezi dvěma sousedními pixely i a j, ztrácíme str_ij. Je to ekvivalentní k minimalizaci množství

{ displaystyle q '(A, B) = součet _ {i v A} b_ {i} + součet _ {i v B} a_ {i} + součet _ { begin {matrix} i, j { text {sousední}} | A cap {i, j } | = 1 end {matrix}} p_ {ij}}

protože

{ displaystyle q (A, B) = součet _ {i v A} a_ {i} + součet _ {i v B} b_ {i} -q '(A, B).}

Minimální řez zobrazený v síti (trojúhelníky VS kruhy).

Nyní vytvoříme síť, jejíž uzly jsou pixel, plus zdroj a umyvadlo, viz obrázek vpravo. Připojíme zdroj k pixelu i o okraj váhy A_i. Spojíme pixel i k dřezu hranou váhy b_i. Spojujeme pixel i na pixel j s váhou str_ij. Nyní zbývá vypočítat minimální snížení v této síti (nebo ekvivalentně maximální tok). Poslední obrázek ukazuje minimální řez.

Rozšíření

1. V problém toku minimálních nákladů, každá hrana (u, v) má také a nákladový koeficient A_uv kromě své kapacity. Pokud je tok přes okraj F_uv, pak jsou celkové náklady A_uvF_uv. Je nutné najít tok dané velikosti ds nejmenšími náklady. Ve většině variant mohou být nákladové koeficienty buď kladné, nebo záporné. Pro tento problém existují různé algoritmy polynomiálního času.

2. Problém s maximálním průtokem lze rozšířit o disjunktivní omezení: a negativní disjunktivní omezení říká, že určitá dvojice hran nemůže mít současně nenulový tok; A pozitivní disjunktivní omezení říká, že u určité dvojice hran musí mít alespoň jedna nenulový tok. S negativními omezeními se problém stává silně NP-tvrdé i pro jednoduché sítě. S pozitivními omezeními je problém polynomiální, pokud jsou povoleny dílčí toky, ale mohou být silně NP-tvrdé když toky musí být integrální.^[19]

Reference

^ ^A ^b ^C Schrijver, A. (2002). "K historii přepravy a problémům s maximálním průtokem". Matematické programování. 91 (3): 437–445. CiteSeerX 10.1.1.23.5134. doi:10,1007 / s101070100259. S2CID 10210675.
^ Gass, Saul I .; Assad, Arjang A. (2005). "Matematický, algoritmický a profesionální vývoj operačního výzkumu od roku 1951 do roku 1956". Komentovaná časová osa operačního výzkumu. International Series in Operations Research & Management Science. 75. str. 79–110. doi:10.1007 / 0-387-25837-X_5. ISBN 978-1-4020-8116-3.
^ ^A ^b Harris, T. E.; Ross, F. S. (1955). „Základy metody pro hodnocení kapacit železniční sítě“ (PDF). Memorandum o výzkumu.
^ ^A ^b Ford, L. R.; Fulkerson, D. R. (1956). Msgstr "Maximální tok sítí". Kanadský žurnál matematiky. 8: 399–404. doi:10.4153 / CJM-1956-045-5.
^ ^A ^b Ford, L.R., Jr.; Fulkerson, D.R., Toky v sítích, Princeton University Press (1962).
^ Sherman, Jonah (2013). "Téměř maximální průtok v téměř lineárním čase". Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science. 263–269. arXiv:1304.2077. doi:10.1109 / FOCS.2013.36. ISBN 978-0-7695-5135-7. S2CID 14681906.
^ Kelner, J. A .; Lee, Y. T .; Orecchia, L .; Sidford, A. (2014). „Algoritmus téměř lineárního času pro přibližný maximální tok v neorientovaných grafech a jeho zobecnění více akomodací“ (PDF). Sborník z dvacátého pátého výročního sympozia ACM-SIAM o diskrétních algoritmech. p. 217. arXiv:1304.2338. doi:10.1137/1.9781611973402.16. ISBN 978-1-61197-338-9. S2CID 10733914. Archivovány od originál (PDF) dne 03.03.2016.
^ Knight, Helen (7. ledna 2014). „Nový algoritmus může dramaticky zefektivnit řešení problému„ maximálního toku ““. Zprávy MIT. Citováno 8. ledna 2014.
^ ^A ^b Orlin, James B. (2013). Msgstr "Maximální tok v čase O (nm) nebo lepší". Sborník ze 45. ročníku sympozia ACM o Sympóziu o teorii výpočetní techniky - STOC '13. STOC '13 Proceedings of the Forty-5th Annual ACM Symposium on Theory of Computing. str. 765–774. CiteSeerX 10.1.1.259.5759. doi:10.1145/2488608.2488705. ISBN 9781450320290. S2CID 207205207.
^ Malhotra, V.M .; Kumar, M. Pramodh; Maheshwari, S.N. (1978). „An ${ displaystyle O (| V | ^ {3})}$ algoritmus pro zjištění maximálních toků v sítích " (PDF). Dopisy o zpracování informací. 7 (6): 277–278. doi:10.1016/0020-0190(78)90016-9.
^ King, V .; Rao, S .; Tarjan, R. (1994). "Rychlejší deterministický algoritmus maximálního průtoku". Journal of Algorithms. 17 (3): 447–474. doi:10.1006 / jagm.1994.1044. S2CID 15493.
^ Goldberg, A. V.; Rao, S. (1998). "Za bariérou proti rozkladu toku". Deník ACM. 45 (5): 783. doi:10.1145/290179.290181. S2CID 96030.
^ Itai, A .; Perl, Y .; Shiloach, Y. (1982). "Složitost hledání maximálních disjunktních cest s omezeními délky". Sítě. 12 (3): 277–286. doi:10,1002 / net. 3230120306. ISSN 1097-0037.
^ Schwartz, B.L. (1966). "Možní vítězové v částečně dokončených turnajích". Recenze SIAM. 8 (3): 302–308. doi:10.1137/1008062. JSTOR 2028206.
^ ^A ^b Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, a Clifford Stein (2001). "26. Maximální průtok". Úvod do algoritmů, druhé vydání. MIT Press a McGraw-Hill. 643–668. ISBN 978-0-262-03293-3.CS1 maint: více jmen: seznam autorů (odkaz)
^ Carl Kingsford. „Rozšíření Max-flow: cirkulace s požadavky“ (PDF).
^ „Project imagesegmentationwithmaxflow, that contains the source code to produce these Illustration“. GitLab. Archivovány od originál dne 2019-12-22. Citováno 2019-12-22.
^ „Návrh algoritmu“. www.pearson.com. Citováno 2019-12-21.
^ Schauer, Joachim; Pferschy, Ulrich (01.07.2013). Msgstr "Problém maximálního toku s disjunktními omezeními". Journal of Combinatorial Optimization. 26 (1): 109–119. CiteSeerX 10.1.1.414.4496. doi:10.1007 / s10878-011-9438-7. ISSN 1382-6905. S2CID 6598669.

Goldberg, A. V.; Tarjan, R. E. (1988). „Nový přístup k problému maximálního průtoku“. Deník ACM. 35 (4): 921. doi:10.1145/48014.61051. S2CID 52152408.

Další čtení

Joseph Cheriyan a Kurt Mehlhorn (1999). Msgstr "Analýza pravidla výběru na nejvyšší úrovni v algoritmu max-flow před-push-push". Dopisy o zpracování informací. 69 (5): 239–242. CiteSeerX 10.1.1.42.8563. doi:10.1016 / S0020-0190 (99) 00019-8.
Daniel D. Sleator a Robert E. Tarjan (1983). "Datová struktura pro dynamické stromy" (PDF). Journal of Computer and System Sciences. 26 (3): 362–391. doi:10.1016/0022-0000(83)90006-5. ISSN 0022-0000.
Eugene Lawler (2001). "4. Toky sítě". Kombinatorická optimalizace: Sítě a matroidy. Doveru. 109–177. ISBN 978-0-486-41453-9.

[:0-1] A ^b ^C Schrijver, A. (2002). "K historii přepravy a problémům s maximálním průtokem". Matematické programování. 91 (3): 437–445. CiteSeerX 10.1.1.23.5134. doi:10,1007 / s101070100259. S2CID 10210675.

[2] Gass, Saul I .; Assad, Arjang A. (2005). "Matematický, algoritmický a profesionální vývoj operačního výzkumu od roku 1951 do roku 1956". Komentovaná časová osa operačního výzkumu. International Series in Operations Research & Management Science. 75. str. 79–110. doi:10.1007 / 0-387-25837-X_5. ISBN 978-1-4020-8116-3.

[:2-3] A ^b Harris, T. E.; Ross, F. S. (1955). „Základy metody pro hodnocení kapacit železniční sítě“ (PDF). Memorandum o výzkumu.

[:1-4] A ^b Ford, L. R.; Fulkerson, D. R. (1956). Msgstr "Maximální tok sítí". Kanadský žurnál matematiky. 8: 399–404. doi:10.4153 / CJM-1956-045-5.

[:3-5] A ^b Ford, L.R., Jr.; Fulkerson, D.R., Toky v sítích, Princeton University Press (1962).

[6] Sherman, Jonah (2013). "Téměř maximální průtok v téměř lineárním čase". Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science. 263–269. arXiv:1304.2077. doi:10.1109 / FOCS.2013.36. ISBN 978-0-7695-5135-7. S2CID 14681906.

[7] Kelner, J. A .; Lee, Y. T .; Orecchia, L .; Sidford, A. (2014). „Algoritmus téměř lineárního času pro přibližný maximální tok v neorientovaných grafech a jeho zobecnění více akomodací“ (PDF). Sborník z dvacátého pátého výročního sympozia ACM-SIAM o diskrétních algoritmech. p. 217. arXiv:1304.2338. doi:10.1137/1.9781611973402.16. ISBN 978-1-61197-338-9. S2CID 10733914. Archivovány od originál (PDF) dne 03.03.2016.

[8] Knight, Helen (7. ledna 2014). „Nový algoritmus může dramaticky zefektivnit řešení problému„ maximálního toku ““. Zprávy MIT. Citováno 8. ledna 2014.

[orlin-9] A ^b Orlin, James B. (2013). Msgstr "Maximální tok v čase O (nm) nebo lepší". Sborník ze 45. ročníku sympozia ACM o Sympóziu o teorii výpočetní techniky - STOC '13. STOC '13 Proceedings of the Forty-5th Annual ACM Symposium on Theory of Computing. str. 765–774. CiteSeerX 10.1.1.259.5759. doi:10.1145/2488608.2488705. ISBN 9781450320290. S2CID 207205207.

[10] Malhotra, V.M .; Kumar, M. Pramodh; Maheshwari, S.N. (1978). „An ${ displaystyle O (| V | ^ {3})}$ algoritmus pro zjištění maximálních toků v sítích " (PDF). Dopisy o zpracování informací. 7 (6): 277–278. doi:10.1016/0020-0190(78)90016-9.

[11] King, V .; Rao, S .; Tarjan, R. (1994). "Rychlejší deterministický algoritmus maximálního průtoku". Journal of Algorithms. 17 (3): 447–474. doi:10.1006 / jagm.1994.1044. S2CID 15493.

[12] Goldberg, A. V.; Rao, S. (1998). "Za bariérou proti rozkladu toku". Deník ACM. 45 (5): 783. doi:10.1145/290179.290181. S2CID 96030.

[13] Itai, A .; Perl, Y .; Shiloach, Y. (1982). "Složitost hledání maximálních disjunktních cest s omezeními délky". Sítě. 12 (3): 277–286. doi:10,1002 / net. 3230120306. ISSN 1097-0037.

[14] Schwartz, B.L. (1966). "Možní vítězové v částečně dokončených turnajích". Recenze SIAM. 8 (3): 302–308. doi:10.1137/1008062. JSTOR 2028206.

[ITA-15] A ^b Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, a Clifford Stein (2001). "26. Maximální průtok". Úvod do algoritmů, druhé vydání. MIT Press a McGraw-Hill. 643–668. ISBN 978-0-262-03293-3.CS1 maint: více jmen: seznam autorů (odkaz)

[16] Carl Kingsford. „Rozšíření Max-flow: cirkulace s požadavky“ (PDF).

[17] „Project imagesegmentationwithmaxflow, that contains the source code to produce these Illustration“. GitLab. Archivovány od originál dne 2019-12-22. Citováno 2019-12-22.

[18] „Návrh algoritmu“. www.pearson.com. Citováno 2019-12-21.

[19] Schauer, Joachim; Pferschy, Ulrich (01.07.2013). Msgstr "Problém maximálního toku s disjunktními omezeními". Journal of Combinatorial Optimization. 26 (1): 109–119. CiteSeerX 10.1.1.414.4496. doi:10.1007 / s10878-011-9438-7. ISSN 1382-6905. S2CID 6598669.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]