Diszjunkt készletrendszer

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2017. június 22-én felülvizsgált verziótól ; az ellenőrzések 13 szerkesztést igényelnek .

A diszjunkt halmazrendszer ( eng. disjoint-set , vagy union-find adatstruktúra ) egy olyan adatstruktúra , amely lehetővé teszi egy diszjunkt részhalmazokra osztott elemkészlet adminisztrálását. Ebben az esetben minden részhalmazhoz hozzá van rendelve a képviselője - ennek a részhalmaznak egy eleme. Egy absztrakt adatszerkezetet három műveletből álló halmaz határoz meg: . ${\displaystyle \{\mathrm {Union} ,\mathrm {Find} ,\mathrm {MakeSet} \))$

Az összekapcsolt komponensek gráfokban való tárolására szolgál , különösen a Kruskal-algoritmusnak hasonló adatszerkezetre van szüksége a hatékony megvalósításhoz.

Definíció

Legyen egy véges halmaz, amely nem metsző részhalmazokra ( osztályokra ) van felosztva : $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

Minden részhalmazhoz hozzá van rendelve egy képviselő . A megfelelő diszjunkt halmazrendszer a következő műveleteket támogatja: $X_{i}$ $r_{i}\in X_{i}$

$\mathrm {MakeSet} (x)$ : új részhalmazt hoz létre az elemhez. Ugyanazt az elemet jelöli ki a létrehozott részhalmaz képviselőjeként. $x$
$\mathrm {Union} (r,s)$ : egyesíti a képviselőkhöz tartozó mindkét részhalmazt és a -t , és kijelöli az új részhalmaz képviselőjét. $r$ $s$ $r$
$\mathrm {Find} (x)$ : Megadja azt a részhalmazt, amelyhez az elem tartozik, és visszaadja a képviselőjét. $x\in S$

Algoritmikus megvalósítás

Egy triviális megvalósítás egy indextömbben tárolja az elemek és a képviselők tulajdonjogát . A gyakorlatban gyakrabban használnak facsoportokat . Ez jelentősen csökkentheti a Keresés művelethez szükséges időt . Ebben az esetben a reprezentáns a fa gyökerébe, az osztály többi eleme pedig az alatta lévő csomópontokba kerül. $S$ $r_{i}$

$\mathrm {Union} (r,s)$ : alacsonyabb fa gyökere a magasabb fa gyökere alá lóg. Ha ez lesz a gyermeke , mindkét csomópont felcserélődik. $r$ $s$
$\mathrm {Find} (x)$ : felveszi a fa gyökeréig tartó utat, és visszaadja azt (a gyökér ebben az esetben reprezentatív). $x$

Heurisztika

Az Unió méret szerint , Magasság szerinti egység , Véletlenszerű unió heurisztika és útvonaltömörítés használható az egyesítési és keresési műveletek felgyorsításához .

Az Union-By-Size heurisztikában a művelet során a kisebb fa gyökere a nagyobb fa gyökere alá kerül. Ez a megközelítés megőrzi a fa egyensúlyát. Az egyes részfák mélysége nem haladhatja meg a . Ezzel a heurisztikával a legrosszabb eset keresési műveletének ideje ról -ra nő . A hatékony megvalósítás érdekében javasolt a fa csomópontjainak számát a gyökérben tárolni. $\mathrm {Union} (r,s)$ $T$ $\log \left|T\right|$ $O(\log n)$ $Tovább)$

Az Union-By-Height heurisztika hasonló a Union-By-Size -hoz , de a méret helyett a fa magasságát használja.

A Random-Union heurisztika azt a tényt használja fel, hogy nem lehet több memóriát költeni a fa csomópontjainak elmentésére: elég véletlenszerűen kiválasztani a gyökért - ez a megoldás a véletlenszerű lekérdezésekhez olyan sebességet biztosít, amely összehasonlítható a többivel. megvalósítások. Ha azonban sok olyan lekérdezés van, mint a "nagy halmaz egyesítése kicsivel", akkor ez a heurisztika csak kétszeresére javítja a várható értéket (vagyis az átlagos futási időt), ezért nem ajánlott anélkül használni. az útvonal tömörítési heurisztika. $Tovább)$

Az útvonal-tömörítési heurisztika a művelet felgyorsítására szolgál . Minden új keresésnél a gyökértől a kívánt elemig tartó útvonalon lévő összes elem a fa gyökere alá kerül. Ebben az esetben a Find művelet átlagosan működik , ahol az Ackerman függvény inverz függvénye . Ezzel jelentősen felgyorsíthatja a munkát, mivel a gyakorlatban használt összes értékhez 5-nél kisebb érték szükséges. $\mathrm {Find} (x)$ $\alpha (n)$ $\alpha$ $\alpha$

Megvalósítási példa

Megvalósítás C++ nyelven:

const int MAXN = 1000 ; int p [ MAXN ], rang [ MAXN ]; void MakeSet ( int x ) { p [ x ] = x ; rang [ x ] = 0 ; } int Keresés ( int x ) { return ( x == p [ x ] ? x : p [ x ] = Find ( p [ x ]) ); } void Unió ( int x , int y ) { if ( ( x = Keresés ( x )) == ( y = keresés ( y )) ) visszatérés ; if ( rang [ x ] < rang [ y ] ) p [ x ] = y ; else { p [ y ] = x ; if ( rang [ x ] == rang [ y ] ) ++ rang [ x ]; } }

Megvalósítás Free Pascalban:

const MAX_N = 1000 ; var Szülő , Rank : LongInt [ 1..MAX_N ] tömbje ; _ _ _ eljáráscsere ( var x , y : LongInt ) ; _ var tmp : LongInt ; kezdődik tmp := x ; x : = y y := tmp ; vége ; eljárás MakeSet ( x : LongInt ) ; kezdődik Szülő [ x ] := x ; Helyezés [ x ] := 0 ; vége ; függvény Keresés ( x : LongInt ) : LongInt ; kezdődik if ( Szülő [ x ] <> x ) akkor Szülő [ x ] := Keresés ( Szülő [ x ] ) ; Kilépés ( szülő [ x ] ) ; vége ; eljárás Unió ( x , y : LongInt ) ; kezdődik x := Find ( x ) ; y := Find ( y ) ; if ( x = y ) akkor kilép () ; if ( Rang [ x ] < Rank [ y ] ) then swap ( x , y ) ; Szülő [ y ] := x ; if ( Rang [ x ] = Rang [ y ] ) akkor inc ( Ranghely [ x ] ) ; vége ;

Lásd még

Diszjunkt halmazok erdeje

Irodalom

Galler, Bernard A. és Michael J. Fisher. "Egy továbbfejlesztett ekvivalencia-algoritmus." // Communications of the ACM , 7.5 (1964): 301-303. (Angol)
Tarjan, Robert E. és Jan Van Leeuwen. "A halmazegyesítő algoritmusok legrosszabb eset elemzése." // Journal of the ACM 31.2 (1984): 245-281. (Angol)
Thomas Kormen és munkatársai Algoritmusok: Konstrukció és elemzés = Introduction to Algorithms. - 2. kiadás - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .

Linkek

Union-Find / Kevin Wayne , Pearson-Addison Wesley
22. fejezet: Adatstruktúrák diszjunkt halmazokhoz / Bevezetés az algoritmusokba, Thomas H. Cormen, Charles E. Leiserson és Ronald L. Rivest
Egyes adatszerkezetek működésének megjelenítője nem metsző halmazokhoz / ITMO
Disjunkt készletek megvalósítása a C++ Boost Libraries gyűjteményben , 2006

Adatstruktúrák
Listák	sor egyenként linkelt lista duplán linkelt lista Pass list
fák	B-fa Bináris keresőfa AVL fa Vörös-fekete fa halom
Számít	Irányított grafikon Irányított aciklikus gráf Bináris döntési diagram Hipergráf
Egyéb	Hash táblázat Kazal