Goldbergův algoritmus

Goldbergův algoritmus hledá maximální tok v síti v čase $O(V^{3})$ . Patří do třídy algoritmů s operacemi přemístění přebytku a zvedání vrcholu na nalezení maximálního toku, které mají $O(V^{2}E)$ . Pro husté grafy je efektivnější než Edmonds-Karpův algoritmus, který má časovou složitost $O(VE^{2})\subseteq O(V^{5})$ . V anglické literatuře se Goldbergův algoritmus též nazývá algoritmem preflow-push nebo relabel-to-front.

Algoritmus editovat

Je dána síť $G(V,E)$ s kapacitou z vrcholu u do vrcholu v danou jako $c(u,v)$ , zdroj z a spotřebič s. Chceme najít maximální tok, který můžeme poslat přes síť ze z do s. Na vrcholech se provádějí dva typy operací: přemístění přebytku a zvedání vrcholu. Během algoritmu dále udržujeme:

pro každou hranu hodnotu $f(u,v)$ , reprezentující současný tok hranou z u do v.
pro každou hranu volnou kapacitu, danou výrazem $c(u,v)-f(u,v)$ .
pro každý vrchol hodnotu $vyska(u)$ . Operaci přemístění přebytku z vrcholu u do vrcholu v provádíme, pouze když $vyska(u)>vyska(v)$ .
pro každý vrchol hodnotu $prebytek(u)$ , dánu jakou rozdíl součtu toků z u minus součet toků do u (případně pouze jako součet toků do u při zavedení pomocného značení, viz níže).

Z důvodů zjednodušení zápisu popisu algoritmu a implementace přidáme do grafu dočasně pro každou hranu opačně orientovanou hranu s nulovou kapacitou. Během výpočtu pak budeme vyžadovat, aby byl pro každou hranu vždy splněn vztah $f(u,v)=-f(v,u)$ . Přidání pomocných hran lze samozřejmě udělat pouze v případě, že graf neobsahuje orientované smyčky. V případě existence smyček bychom museli postupovat o trochu opatrněji, rozmyšlení tohoto zřídkakdy se vyskytujícího případu ponecháme čtenáři za domácí cvičení :-). Na hodnoty f(u,v) dále klademe během výpočtu následující podmínky:

$\ f(u,v)\leq c(u,v)$ . Tok mezi $u$ a $v$ nepřevyšuje kapacitu.
$\ f(u,v)=-f(v,u)$ . Udržujeme korektní tok (vlnu) sítě.
$\ \sum _{v}f(u,v)=prebytek(u)\geq 0$ pro všechny vrcholy $u\neq z$ . Pouze zdroj může generovat tok.

Zobrazení $f$ splňující tyto podmínky nenazýváme přípustným tokem, tak jak je používán například ve Ford-Fulkensonově metodě, ale pouze vlnou. Rozdíl je v tom, že vlna povoluje kladný přebytek. Vlnu používáme pouze během výpočtu, výstupem algoritmu je přípustný tok (speciální případ vlny). Všimněte si, že poslední podmínka pro přebytek je odvozená z korespondující podmínky pro přípustný tok v běžné síti.

Pozorujeme, že nejdelší možná cesta ze z do s je $|V|$ vrcholů dlouhá. Proto pro každý přípustný tok existuje přiřazení výšky vrcholům splňující, že $vyska(z)=|V|$ a $vyska(t)=0$ , a je-li tok hranou z u do v kladný, pak $vyska(u)>vyska(v)$ . Během přemisťování přebytku vrcholů se vlna chová stejně jako vodní vlna v přírodě—přebytek se přelévá pouze z vrcholů s větší výškou do níže položených. Na rozdíl od Ford-Fulkersonova algoritmu, tok (vlna) v síti nemusí nutně být přípustným tokem během výkonu algoritmu.

Zjednodušeně, nejprve naplníme všechny hrany vedoucí ze zdroje. Dále během výpočtu zvyšujeme výšky vrcholů (kromě z a s) a přebytky se jako vlna šíří mezi vrcholy, dokud veškeré přebytky nedosáhnou spotřebiče. Poté pokračujeme ve zvyšování výšky vnitřních vrcholů sítě, až dokud se přebytky, které nedosáhly spotřebiče, nevrátí zpět do zdroje. Vrchol může dosáhnout nejvýše výšky $2|V|-1$ , protože nejdelší možná cesta z libovolného vrcholu kromě s zpátky do z je $|V|-1$ dlouhá a $vyska(z)=|V|$ . Výška s se udržuje na 0.

Přemístění přebytku editovat

Přemístění přebytku z u do v znamená přemístit část přebytku v u do v. Pro přemísťování přebytku musí být splněny tři podmínky:

$prebytek(u)>0$ . Zatím do vrcholu více vtéká, než z vrcholu vytéká.
$c(u,v)-f(u,v)>0$ . Je dostupná kapacita z u do v.
$vyska(u)>vyska(v)$ . Přebytek můžeme poslat pouze nižšímu vrcholu.

Posíláme pouze množství rovné $\min(prebytek(u),c(u,v)-f(u,v))$ .

Zvedání vrcholů editovat

Zvedání vrcholu u je zvětšení jeho výšky, dokud není vyšší než alespoň jeden vrchol s volnou kapacitou. Podmínky pro zvedání vrcholu:

$prebytek(u)>0$ . Zvedání vrcholu u musí mít smysl.
$vyska(u)\leq vyska(v)$ pro všechna v, pro která platí $c(u,v)-f(u,v)>0$ . Jedině vyšší vrcholy mají volnou kapacitu.

Při zvednutí vrcholu u přiřadíme $vyska(u)$ nejnižší hodnotu tak, aby $vyska(u)>vyska(v)$ pro nějaké v, kde $c(u,v)-f(u,v)>0$ .

Algoritmus přemísťování přebytku a zvedání vrcholu editovat

Algoritmus přemísťování přebytku a zvedání vrcholu má ve všeobecnosti tento postup:

Tak dlouho, dokud je možné provádět operace přemístění přebytku nebo zvedání vrcholu
1. Přemísti přebytek, nebo
2. Zvedni vrchol.

Obecná časová složitost pro algoritmy používající tento postup je $O(V^{2}E)$ . Golbergův algoritmus přidává další modifikace, které časovou složitost zlepší na $O(V^{3})$ .

Odstranění přebytku editovat

Odstranění přebytku vrcholu u znamená:

Pokud $prebytek(u)>0$ :
1. Pokud existuje soused, ke kterému lze přemístit přebytek:
  1. Pokusíme se přemístit přebytek k sousedovi s nižší výškou a volnou kapacitou.
2. Jinak:
  1. Zvedni vrchol u

Goldbergův algoritmus editovat

Goldbergův algoritmus určuje pořadí operací přemístění přebytku a zvedání vrcholu:

Pošli tok z vrcholu z, kolik se jen dá.
Vytvoř seznam všech vrcholů kromě z a s.
Dokud neprojdeme celý seznam:
1. Odstraň přebytek současného vrcholu.
2. Pokud se výška současného vrcholu změnila:
  1. Přesuň současný vrchol na začátek seznamu
  2. Začni znovu prohledávání seznamu od začátku

Časová složitost Goldbergova algoritmu je $O(V^{3})$ (důkaz vynechán).

Ukázková implementace editovat

Implementace v programovacím jazyku Python verze 2:

def goldberg(C, zdroj, spotrebic):
    n = len(C) # C je matice kapacit
    F = [[0] * n for _ in xrange(n)]
    # zbytková kapacita z u do v je C[u][v] - F[u][v]

    vyska = [0] * n # výška vrcholu
    prebytek = [0] * n # rozdíl toku do a z vrcholu
    vyzkousen = [0] * n # sousedi vyzkoušení od posledního zvedání vrcholu
    # "seznam" vrcholů
    seznam   = [i for i in xrange(n) if i != zdroj and i != spotrebic]

    def zvedni(u, v):
        posli = min(prebytek[u], C[u][v] - F[u][v])
        F[u][v] += posli
        F[v][u] -= posli
        prebytek[u] -= posli
        prebytek[v] += posli

    def zvedni(u):
        # najdi nejmenší novou výšku a udělej přemístění přebytku možným,
        # jestli je vůbec možné něco zvednout
        min_vyska = vyska[u]
        for v in xrange(n):
            if C[u][v] - F[u][v] > 0:
                min_vyska = min(min_vyska, vyska[v])
                vyska[u] = min_vyska + 1

    def vyprazdni(u):
        while prebytek[u] > 0:
            if vyzkousen[u] < n: # zkontroluj dalšího souseda
                v = vyzkousen[u]
                if C[u][v] - F[u][v] > 0 and vyska[u] > vyska[v]:
                    zvedni(u, v)
                else:
                    vyzkousen[u] += 1
            else: # zkontrolovali jsme všechny sousedy. musíme ho zvednout
                zvedni(u)
                vyzkousen[u] = 0

    vyska[zdroj] = n   # nejdelší cesta ze zdroje do spotřebiče je kratší než n
    prebytek[zdroj] = Inf # pošli tolik toku, kolik se jen dá sousedovi zdroje
    for v in xrange(n):
        zvednout(zdroj, v)

    p = 0
    while p < len(seznam):
        u = seznam[p]
        old_vyska = vyska[u]
        vyprazdni(u)
        if vyska[u] > old_vyska:
            seznam.insert(0, seznam.pop(p)) # přesuň na začátek seznamu
            p = 0 # začni ze začátku seznamu
        p += 1

    return sum([F[zdroj][i] for i in xrange(n)])

Všimněte si, že tato implementace není moc efektivní. Je pomalejší než Edmonds-Karpův algoritmus dokonce pro hodně husté grafy. Pro zrychlení můžete udělat nejméně dvě věci:

Udělejte seznam sousedů pro každý vrchol a nechť je index vyzkousen[u] iterátor, místo intervalu $0..n-1$ .
Použijte heuristiku mezer. Jestli existuje $k$ , že pro žádný vrchol $u$ neplatí $vyska(u)=k$ , můžete přiřadit $vyska(u)=\max(vyska(u),vyska(z)+1)$ pro všechny vrcholy kromě $z$ , pro které $vyska(u)>k$ , protože takové $k$ reprezentuje minimální řez grafu a mezi vrcholy $Z=\{u|vyska(u)>k\}$ a $T=\{v|vyska(v)<k\}$ už nepřeteče víc. Kdyby $(Z,S)$ nebyl minimální řez, existovala by hrana $(u,v)$ , pro niž by $u\in Z$ , $v\in S$ a $c(u,v)-f(u,v)>0$ . Ale pak by $vyska(u)$ nebyla zvětšena víc než $vyska(v)+1$ , což je v rozporu s předpoklady $vyska(u)>k$ a $vyska(v)<k$ .