Goldbergův algoritmus

Z Wikipedie, otevřené encyklopedie

Goldbergův algoritmus hledá maximální tok v síti v čase O(V3). Patří do třídy algoritmů s operacemi zvedání a přeznačování na nalezení maximálního toku, které mají O(V2E). Pro husté grafy je efektivnejší než Edmonds-Karpův algoritmus, který má časovou složitost O(VE^2) \sube O(V^5).

Obsah

[editovat] Algoritmus

Je daná síť G(V,E) s kapacitou z vrcholu u do vrcholu v danou jako c(u,v), zdroj s a spotřebič t. Chceme najít maximální tok, který můžeme poslat přes síť z s do t. Na vrcholech se převádějí dva typy operací: zvedání a přeznačení, kterými udržujeme:

  • f(u,v). Tok z u do v. Volná kapacita je c(u,v) − f(u,v).
  • vyska(u). Jenom zvedáme u do v když vyska(u) > vyska(v)
  • prebytek(u). Součet toku do a z u.

Po každém kroku algoritmu platí:

  • \ f(u,v) \leq c(u,v). Tok mezi u a v převyšuje kapacitu.
  • \ f(u,v) = - f(v,u). Udžujeme tok sítě.
  • \ \sum_v f(u,v) = prebytek(u) \geq 0 pro všechny vrcholy u \neq s. Jenom zdroj může generovat tok.

Všimněte si, že poslední podmínka pro přestok je odvozená z korespondující podmínky pro povolený tok v běžné síti.

Pozorujeme, že nejdelší možná cesta z s do t je | V | vrcholů dlouhá. Proto je možné přiřadit vrcholům výšku jako pro každý povolený tok, že vyska(s) = | V | a vyska(t) = 0, a když existuje kladný tok z u do v, vyska(u) > vyska(v). Počas zvedání vrcholů jde tok přes síť stejně jako voda přes krajinu. Na rozdíl od Ford-Fulkersonovho algoritmu, tok v síti nemusí nutně být povolený tok počas výkonu algoritmu. Povolený znamená v mezích všech kapacit.

Jednoduše, výška vrcholů (kromě s a t) je upravovaná a tok se šíří mezi vrcholy, pokud všechny možné toky dosáhli t. Pak pokračujeme ve zvedání vnitřních vrcholů, až kým se všechny toky rozšířené v síti, které nedosáhli t, vrátí na s. Vrchol může dosáhnout výšku 2 | V | − 1 před koncem jako nejdelší možná cesta zpátky do s vyjímajíc toho, že t je | V | − 1 dlouhá a vyska(s) = | V | . Výška t se udržuje na 0.

[editovat] Zvedání

Zvedání z u do v znamená poslat část přebytku v u do v. Pro zvedání musí být splněny tři podmínky:

  • prebytek(u) > 0. Zatím víc toku jde do vrcholu než z něj vytéká.
  • c(u,v) − f(u,v) > 0. Dostupná kapacita z u do v.
  • vyska(u) > vyska(v). Může poslat jenom nižšímu vrcholu.

Posíláme jenom množství rovné min(prebytek(u),c(u,v) − f(u,v)).

[editovat] Přeznačení

Přeznačení vrcholu u je zvečšení jeho výšky pokým není vyšší než alespoň jeden vrchol s volnou kapacitou. Podmínky pro přeznačení:

  • prebytek(u) > 0. Přeznačování 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 přeznačení u, přiřadíme vyska(u) nejnižší hodnotu aby vyska(u) > vyska(v) pro nejake v kde c(u,v) − f(u,v) > 0.

[editovat] Algoritmus zvedání a přeznačování

Algoritmus zvedání a přeznačování má ve všeobecnosti tenhle postup:

  1. Tak dlouho, pokud je možné dělat operace zvedání nebo přeznačení
    1. Zvedni, nebo
    2. přeznač.

Časová složitost pro tyhle algoritmy je ve všeobecnosti O(V2E) (vynechán argument).

[editovat] Vypráznení

Vypráznení vrcholu u znamená:

  1. Pokud prebytek(u) > 0:
    1. Jestli jsme neskusili všechny sousedy od posledního přeznačení:
      1. Pokusíme se zvednout tok k sousedům, které jsme neskusili.
    2. Jinak:
      1. Přeznač u

Tohle si vyžaduje pamatovat pro každý vrchol, jestli jsme ho zkusili od posledního přeznačení.

[editovat] Goldbergův algoritmus

Goldbergův algoritmus, určuje pořadí operací zvedání a přeznačení:

  1. Pošli tok z 's kolik se jen dá.
  2. Vytoř seznam všech vrcholů kromě s a t.
  3. Pokud neprojdeme celý seznam:
    1. Vyprázni současný vrchol.
    2. Jestli se výška současného vrcholu změnila:
      1. Posuň současný vrchol na začátek seznamu
      2. Začni znovu prohledávání seznamu od začátku

Časová složitost Goldberga je O(V3) (důkaz vynechán).

[editovat] Ukázková implementace

Implementace v programovacím jazyku Python:

def goldberg(C, zdroj, spotrebic):
    n = len(C) # C je matice kapacit
    F = [[0] * n for _ in xrange(n)]
    # zvyšková 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 přeznačování
    # "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 preznac(u):
        #  najdi nejmenší novou výšku a udělej zvedání možným,
        # jestli je vůbec možné neco 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 přeznačit
                preznac(u)
                vyzkousen[u] = 0

    vyska[zdroj] = n   # nejdelší cesta ze zdroje to spotřebiče je dlouhá míň než n
    prebytek[zdroj] = Inf # pošli tolik toku, kolik se jen dá sousedovi zdroje
    for v in xrange(n):
        zvedni(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 tahle implementace není moc efektivní. Je pomalejší než Edmonds-Karpův algoritmus dokonce pro hodně husté grafy. Pro zrychlení, můžete udělat nejmíň dvě věci:

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


[editovat] Reference

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 26.4: Push-relabel algorithms, and section 26.5: The relabel-to-front-algorithm.
V jiných jazycích