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) \sube O(V^5). V anglické literatuře se Goldbergův algoritmus též nazývá algoritmem preflow-push nebo relabel-to-front.

Algoritmus

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. +more 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). +more 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. +more 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). +more 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. +more 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

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. +more 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ů

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. +more 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

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 ## Přemísti přebytek, nebo ## 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

Odstranění přebytku vrcholu u znamená: # Pokud prebytek(u) > 0: ## Pokud existuje soused, ke kterému lze přemístit přebytek: ### Pokusíme se přemístit přebytek k sousedovi s nižší výškou a volnou kapacitou. ## Jinak: ### Zvedni vrchol u

Goldbergův algoritmus

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. +more # Dokud neprojdeme celý seznam: ## Odstraň přebytek současného vrcholu. ## Pokud se výška současného vrcholu změnila: ### Přesuň současný vrchol na začátek seznamu ### 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

Implementace v programovacím jazyku Python verze 2:

def goldberg(C, zdroj, spotrebic): n = len(C) # C je matice kapacit F =

* 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 . +more= 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] 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 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. +more 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. +more # 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) 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) .

Související články

Tok v síti * Fordův-Fulkersonův algoritmus * Dinicův algoritmus

Reference

Thomas H. +more Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. . Section 26. 4: Push-relabel algorithms, and section 26. 5: The relabel-to-front-algorithm. * Jakub Černý: [url=https://web. archive. org/web/20071018060717/http://kam. mff. cuni. cz/~kuba/ka/]Základní grafové algoritmy[/url] * Martin Mareš, Tomáš Valla: [url=https://knihy. nic. cz/files/edice/Pruvodce_labyrintem_algoritmu. pdf]Průvodce labyrintem algoritmů[/url].

Kategorie:Toky v sítích