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
.
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í:
. Tok mezi u a v převyšuje kapacitu.
. Udžujeme tok sítě.
pro všechny vrcholy
. 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.
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:
- Tak dlouho, pokud je možné dělat operace zvedání nebo přeznačení
- Zvedni, nebo
- 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á:
- Pokud prebytek(u) > 0:
- Jestli jsme neskusili všechny sousedy od posledního přeznačení:
- Pokusíme se zvednout tok k sousedům, které jsme neskusili.
- Jinak:
- Přeznač u
- Jestli jsme neskusili všechny sousedy od posledního přeznačení:
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í:
- Pošli tok z 's kolik se jen dá.
- Vytoř seznam všech vrcholů kromě s a t.
- Pokud neprojdeme celý seznam:
- Vyprázni současný vrchol.
- Jestli se výška současného vrcholu změnila:
- Posuň současný vrchol na začátek seznamu
- 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:
- 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. 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é
,
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.

