Disjunktní množinový systém

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 22. června 2017; kontroly vyžadují 13 úprav .

Disjoint-set system ( angl. disjoint-set , nebo union-find data structure ) je datová struktura , která umožňuje spravovat sadu prvků, rozdělenou do disjunktních podmnožin. V tomto případě je každé podmnožině přiřazen její zástupce – prvek této podmnožiny. Abstraktní datová struktura je definována sadou tří operací: . ${\displaystyle \{\mathrm {Union} ,\mathrm {Najít} ,\mathrm {MakeSet} \))$

Používá se k ukládání připojených komponent do grafů , zejména Kruskalův algoritmus potřebuje pro efektivní implementaci podobnou datovou strukturu.

Definice

Nechť konečnou množinu rozdělenou na neprotínající se podmnožiny ( třídy ) : $S$ $X_{i}$

S=X_{0}\cup X_{1}\cup X_{2}\cup \ldots \cup X_{k}:X_{i}\cap X_{j}=\varnothing \quad \forall i ,j\in \lbrace 0,1,\ldots ,k\rbrace ,i\neq j

Každé podmnožině je přiřazen zástupce . Odpovídající systém disjunktních množin podporuje následující operace: $X_{i}$ $r_{i}\in X_{i}$

$\mathrm {MakeSet} (x)$ : vytvoří pro prvek novou podmnožinu. Označuje stejný prvek jako zástupce vytvořené podmnožiny. $X$
$\mathrm {Union} (r,s)$ : kombinuje obě podmnožiny patřící zástupcům a a označuje zástupce nové podmnožiny. $r$ $s$ $r$
$\mathrm {Najít} (x)$ : Určuje pro podmnožinu, do které prvek patří, a vrací svého zástupce. $x\in S$

Algoritmická implementace

Triviální implementace ukládá vlastnictví prvků z a zástupců v indexovém poli . V praxi se častěji používají sady stromů . To může výrazně zkrátit čas potřebný pro operaci Najít . V tomto případě je zástupce zapsán do kořene stromu a zbývající prvky třídy jsou zapsány do uzlů pod ním. $S$ $r_{i}$

$\mathrm {Union} (r,s)$ : zavěsí kořen nižšího stromu pod kořen vyššího stromu. Pokud se toto stane potomkem , oba uzly se prohodí. $r$ $s$
$\mathrm {Najít} (x)$ : vezme cestu z ke kořenu stromu a vrátí ji (kořen je v tomto případě zástupce). $X$

Heuristika

K urychlení operací Union a Find lze použít heuristiku Union-By-Size , Union-By-Height , Random-Union a kompresi cest .

V heuristice Union-By-Size je během operace kořen menšího stromu zavěšen pod kořen většího stromu. Tento přístup zachovává rovnováhu stromu. Hloubka každého podstromu nemůže přesáhnout . Pomocí této heuristiky se doba operace Najít v nejhorším případě prodlouží z na . Pro efektivní implementaci se navrhuje ukládat počet uzlů ve stromu do kořene. $\mathrm {Union} (r,s)$ $T$ $\log \left|T\right|$ $O(\log n)$ $Na)$

Heuristika Union-By-Height je podobná jako Union-By-Size , ale místo velikosti používá výšku stromu.

Heuristika Random-Union využívá skutečnosti, že je možné neutrácet další paměť pro uložení počtu uzlů ve stromu: stačí náhodně vybrat kořen - toto řešení poskytuje rychlost na náhodné dotazy, která je zcela srovnatelná s ostatními implementací. Pokud však existuje mnoho dotazů jako „sloučit velkou sadu s malou“, tato heuristika zlepšuje očekávanou hodnotu (tedy průměrnou dobu běhu) pouze o faktor dva, takže se nedoporučuje používat ji bez heuristika komprese cesty. $Na)$

K urychlení operace se používá heuristika komprese cesty . Při každém novém hledání jsou všechny prvky, které jsou na cestě od kořene k požadovanému prvku, zavěšeny pod kořen stromu. V tomto případě bude operace Najít fungovat v průměru , kde je inverzní funkce Ackermanovy funkce . To vám umožňuje výrazně urychlit práci, protože pro všechny v praxi používané hodnoty nabývá hodnoty menší než 5. $\mathrm {Najít} (x)$ $\alpha (n)$ $\alpha$ $\alpha$

Příklad implementace

Implementace v C++:

const int MAXN = 1000 ; int p [ MAXN ], pořadí [ MAXN ]; void MakeSet ( int x ) { p [ x ] = x ; hodnost [ x ] = 0 ; } int Najít ( int x ) { return ( x == p [ x ] ? x : p [ x ] = Najít ( p [ x ]) ); } void Union ( int x , int y ) { if ( ( x = Najít ( x )) == ( y = Najít ( y )) ) vrátit se ; if ( hodnost [ x ] < hodnost [ y ] ) p [ x ] = y ; jinak { p [ y ] = x ; if ( hodnost [ x ] == hodnost [ y ] ) ++ pořadí [ x ]; } }

Implementace ve Free Pascalu:

const MAX_N = 1000 ; var Parent , Rank : array [ 1 .. MAX_N ] of LongInt ; procedura swap ( var x , y : LongInt ) ; var tmp : LongInt ; začít tmp := x ; x : = y y := tmp ; konec ; procedura MakeSet ( x : LongInt ) ; začít Nadřazený [ x ] := x ; Pořadí [ x ] := 0 ; konec ; funkce Najít ( x : LongInt ) : LongInt ; začít if ( Parent [ x ] <> x ) then Rodič [ x ] := Najít ( Rodič [ x ] ) ; Exit ( Parent [ x ] ) ; konec ; procedura Union ( x , y : LongInt ) ; začít x := Najít ( x ) ; y := Najít ( y ) ; if ( x = y ) then exit () ; if ( Pořadí [ x ] < Pořadí [ y ] ) then swap ( x , y ) ; Rodič [ y ] := x ; if ( Pořadí [ x ] = Pořadí [ y ] ) pak inc ( Pořadí [ x ] ) ; konec ;

Viz také

Les disjunktních množin

Literatura

Galler, Bernard A. a Michael J. Fisher. "Vylepšený algoritmus ekvivalence." // Communications of the ACM , 7.5 (1964): 301-303. (Angličtina)
Tarjan, Robert E. a Jan Van Leeuwen. "Analýza nejhoršího případu sjednocovacích algoritmů." // Journal of the ACM 31.2 (1984): 245-281. (Angličtina)
Thomas Kormen a kol. , Algoritmy: Konstrukce a analýza = Úvod do algoritmů. - 2. vyd. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .

Odkazy

Union-Find / Kevin Wayne , Pearson-Addison Wesley
Kapitola 22: Datové struktury pro nesouvislé množiny / Úvod do algoritmů, Thomas H. Cormen, Charles E. Leiserson a Ronald L. Rivest
Vizualizér práce některých datových struktur pro neprotínající se množiny / ITMO
Implementace nesouvislých sad v kolekci C++ Boost Libraries Collection , 2006

Datové struktury
Seznamy	pole jednotlivě propojený seznam dvojitě propojený seznam Seznam průchodů
Stromy	B-strom Binární vyhledávací strom strom AVL Červeno-černý strom halda
Počítání	Orientovaný graf Orientovaný acyklický graf Binární rozhodovací diagram Hypergraf
jiný	Hash tabulka Zásobník