Sistemul de seturi disjuncte (disjunctă-set de date strictura) este o colecție de seturi de non-goale disjuncte, în fiecare dintre care este fixat unul dintre elementele - reprezentant (reprezentantul). Mai exact, elementele de seturi sunt obiecte în memorie și lucrul cu ele se realizează cu ajutorul indicatorilor. Trebuie suportate următoarele operații:
- Make-Set (x). Procedura trece un pointer la obiectul (deja existent) x. Creează un nou set, singurul element (și astfel reprezentantul) este specificat de indicatorul x. Din moment ce mulțimile nu trebuie să se intersecteze, este necesar ca x să indice un obiect nou (care nu se află în nici unul din seturile existente).
- Find-Set (x) ("găsiți setul"). Returnează un pointer unui reprezentant al unui set (unic) care conține elementul indicat de x.
- Uniunea (x. Y) ("uniune"). Aplicabil dacă elementele x și y sunt cuprinse în seturi diferite Sx și Sy. și înlocuiește aceste seturi de uniunea Sx ∪ Sy; în acest caz, alegem un reprezentant pentru Sx ∪ Sy. Seturile Sx și Sy sunt șterse.
În orice caz, este esențial ca reprezentantul setului să nu se schimbe, în timp ce mulțimea însăși rămâne neschimbată (nu se unește cu cealaltă). Applet „Sistemul de seturi disjuncte“ vizibilizează funcționarea sistemului de seturi disjuncte pentru cele două implementări mai utile - folosind liste și cu ajutorul pădurilor seturi disjuncte.
Implementarea cu liste
Cea mai simplă versiune a implementării unui sistem de seturi disjuncte stochează fiecare set ca listă. În acest caz, primul element al listei este considerat reprezentantul setului și fiecare element al listei conține referințe la elementul următor al listei și la primul element al listei. Pentru fiecare listă, stocăm indicii la primul și ultimul element (al doilea este necesar atunci când adăugați elemente la sfârșitul listei). Ordinea articolelor din listă poate fi oricare. Cu această implementare, operațiile Make-Set și Find-Set necesită timp O (1): Make-Set creează o listă dintr-un element și Find-Set returnează un pointer la începutul listei.
Cea mai simplă implementare a asociației
Cu o implementare firească, funcționarea Uniunii este costisitoare. Efectuarea Uniunii (x. Y). adăugăm o listă care conține x. la sfârșitul listei care conține y. În acest caz, trebuie să setați indicii corectori la începutul listei pentru toate elementele anterioare ale setului care conțin x. iar timpul pentru efectuarea acestei operațiuni depinde liniar de dimensiunea setului.
Este ușor de dat un exemplu în care timpul de execuție este dependent în mod quadratic de numărul de operațiuni. Fie n elemente x 1. x 2. xn să fie dat. Efectuați operațiile Make-Set (xi) pentru toate i = 1, 2, ..., n. și apoi n - 1 operațiuni Union (x 1. x 2). Uniune (x 2. x 3). ..., Uniune (x n-1. Xn). Deoarece costul operației Uniune (xi xi + 1) este proporțional cu i. costul total al efectuării operațiunilor 2 n - 1 va fi proporțional cu n + (n - 1) + ... + 1 = θ (n 2).
Greutate heuristică
Cea mai simplă implementare a operațiunii Uniunii funcționează lent, deoarece atunci când adăugați o listă lungă la una scurtă, trebuie să atribuiți noi valori unui număr mare de pointeri. Lucrurile vor merge mai bine, în cazul în care să facă acest lucru: se va depozita împreună cu fiecare informație listă cu privire la numărul de elemente din ea, și în timpul Uniunii operațiuni pentru a adăuga o listă scurtă, la sfârșitul unei mai (în cazul în care lungimile sunt egale, procedura poate fi orice). Această tehnică se numește euristică uniune ponderată. Dacă seturile combinate conțin elemente aproximativ egale, atunci nu va exista un câștig mare, dar în ansamblu, după cum arată următoarea teoremă, realizăm economii.
Teorema 1. Să presupunem că un sistem de seturi disjuncte este realizat folosind liste, iar în funcționare se utilizează euristica de greutate a Uniunii. Apoi, costul unei secvențe de operațiuni m Make-Set. Uniunea și setul de căutări. printre care n operațiuni Make-Set. este O (m + n · log n) (se presupune că inițial sistemul de seturi disjuncte a fost gol).
Dovada acestei teoreme este dată în cartea lui Kormen, la pagina 419.
Pădurea seturilor disjuncte
Pentru un sistem de seturi disjuncte există o realizare mai eficientă (în comparație cu cele considerate). Anume, reprezentăm fiecare set de un copac rădăcină în care vârfurile sunt elementele setului, iar rădăcina este reprezentativă. Se dovedește o pădure de păduri dezordonate. După cum puteți vedea, fiecare vârf indică părintele său, iar punctul rădăcină se referă la el însuși. Cu programarea naivă a operațiunilor Find-Set și Union, o astfel de implementare nu va fi mai bună decât o implementare a listei; dacă, totuși, folosim euristicile de "uniune de rang" și "compresie de cale", atunci se va obține cea mai rapidă (din momentul în care se cunoaște) implementarea unui sistem de seturi disjuncte.
punerea în aplicare Naiv a operațiunilor sunt după cum urmează: Asigurați-Set creează un arbore cu un singur vârf, Find-Set (x) este că vom merge de la x pe săgeți (ce indică spre părinte) până când vom ajunge la radacina (calea pe care ne aflăm în același timp treci, am numit calea de căutare. în limba engleză găsi calea), iar Uniunea constă în faptul că vom face rădăcina unui copac pentru a specifica nu pentru sine, ci la rădăcina unui alt copac.
Două euristici
Până în prezent, nu există avantaje mari (comparativ cu implementarea listei): de exemplu, ca urmare a n - 1 operațiuni, Uniunea poate obține un arbore care este un lanț de n noduri. Descriim două euristici care fac posibilă realizarea unei estimări aproape liniare a timpului.
Prima euristică, numită uniune de rang (uniune de rang), care amintește de euristicii de greutate în implementarea de salarizare: combinăm copacii nu sunt la fel de oribil, de asemenea, la rădăcina „mai mică“ a îndreptat copac la rădăcina „mai mare“. Alegerea "mai mare" nu este determinată de dimensiunea arborelui, ci de parametrul special - rangul rădăcinii acestuia. Gradul este definit pentru fiecare nod x din lemn și, în primă aproximație poate fi considerată ca o estimare aproximativă a logaritmului numărului de noduri din subarborele înrădăcinate la x. Definiția exactă a rangului va fi prezentată mai jos.
A doua euristică utilizată în operația Find-Set. se numește compresie de cale. Acesta este după cum urmează: după calea de căutare din partea de sus la rădăcină este trecut, copacul este reconstruit: în fiecare dintre vârfurile indicatorul cale este setat direct pe rădăcină. În același timp, rândurile rămân aceleași.
Următoarele programe de operare Make-Set. Find-Set și Union includ o definiție inductivă a rangului, dar pentru comoditate îl vom retela verbal. Când creați seturi folosind un set-face doar partea de sus a arborelui este atribuit un rang de 0. Operațiunea Find-Set (cu compresie căi) nu schimbă rangul. În Uniunea exploatarea arborilor, care sunt diferite grade de rădăcini este ținut de mână noua rădăcină de rang inferior la rădăcina de rang superior, și se situează din nou, nu se schimba. În cazul în care, în final, funcționarea Uniunii se realizează cu copacii, rădăcinile rândurile sunt egale, atunci unul din rădăcini (în continuare, a) trage o săgeată la alta, și la același rang combinat rădăcină al arborelui este crescut de una (celelalte rândurile nu se schimbă). Este ușor de observat că rangul unui vârf definit astfel este o limită superioară pentru înălțimea subtreei cu rădăcina la acest vârf.
Sub p [x] se indică paternitatea vârfului x. rank [x] este rangul lui; parametrii procedurii Link. care este chemată din procedura Uniunii. sunt rădăcinile a doi copaci (mai precis, indicii pentru ei).
Procedura de recursive Găsiți-set funcționează în două treceri: în primul rând, merge la rădăcina copacului, și apoi trece această rută în ordine inversă „ia săgețile“ de la care apar la rădăcina vârfurile copacilor. Dacă x nu este o rădăcină, Find-set apeluri în sine, dar cu parametrul părinte x. Apoi face parintele lui x rădăcina copacului găsit de acest nou apel găsit (linie 2). Dacă x este o rădăcină, atunci linia 2 nu este executată și un pointer la x se întoarce imediat.
Ce sunt euristicile?
Chiar dacă sunt aplicate separat, uniunea pe rang și comprimarea căilor dau un câștig în timp. Dacă aplicăm rangul uniune fără căi de compresie, estimarea timpului de funcționare va fi de aproximativ aceeași ca atunci când o punere în aplicare enumerate cu euristică greutate, și anume O (m log n) (m - numărul total de tranzacții, n - numărul de operațiuni Make-Set). Această estimare este neimportantă. Dacă aplicați compresia căii fără a combina în funcție de rang, timpul de execuție al fluxului de lucru, inclusiv operațiunile n Make-Set și operațiile Find-Set. este (cel mai rau) θ (f · log1 + f / n n) cu f ≥ n și θ (n + f · log n) la f Chiar și economii mai mari pot fi obținute prin aplicarea ambelor euristici împreună. În acest moment, în cel mai rău caz este O (m α (m n).), Caracterizat prin aceea α - extrem de creștere lentă "funcție inversă Ackerman". În orice aplicații imaginabile inegalitate α (m. N) ≤ 4, astfel încât, în practică, poate fi considerată ca fiind liniar în timp m. Pentru dovezi ale declarațiilor de mai sus și mai multe informații despre sistemul de seturi disjuncte, bun venit în cartea Korma :)
literatură
Trimiteți-le prietenilor: