Clasele 9-10 lecția 5 - 15 oct 2014

From Algopedia
Jump to navigationJump to search

Structuri de mulțimi disjuncte (union-find)

Definiția problemei. Operații cerute

Se dă o colecție de obiecte. Inițial, fiecare obiect stă singur în mulțimea lui (în unele aplicații, obiectele încep deja grupate în mai multe mulțimi). Apoi executăm operații de unificare a două mulțimi. La fiecare moment, dorim să aflăm ușor dacă două obiecte x și y sunt în aceeași mulțime sau nu.

Așadar, căutăm o structură de date care să implementeze eficient operațiile:

  • init(n): creează o structură de date cu n obiecte, fiecare în propria mulțime;
  • union(x, y): reunește mulțimile din care fac parte obiectele x și y; dacă obiectele sunt deja în aceeași mulțime, nu face nimic;
  • find(x): găsește mulțimea din care face parte x.

Precizăm că find() poate returna valori arbitrare. Nu ne pasă cum își denumește structura mulțimile, ci doar ca find(x) = find(y) dacă și numai dacă x și y sunt în aceeași mulțime.

Implementare în O(n) per operație

Folosim un vector v cu n elemente. Două elemente x și y sunt în aceeași grupă dacă v[x] = v[y].

  • init(n): v[i] = i pentru i = 0, 1, ... n - 1
  • union(x, y): caută toate pozițiile i în vector pentru care v[i] = v[x] și înlocuiește-le cu v[y]
  • find(x): returnează v[x]

Desigur, operația find() rulează în O(1), iar union(x, y) rulează în O(n).

Implementare în O(log n) per operație

Încercăm să înlănțuim elementele fiecărei mulțimi, ca să nu fie nevoie să iterăm prin n elemente când vrem doar să reunim două dintre ele. Folosim trei vectori cu n elemente fiecare:

  • v[i] stochează numărul mulțimii lui i; acesta este unul dintre elementele din mulțime, ales ca exponent;
  • size[i] stochează numărul de elemente din grupa lui i, doar pentru exponentul mulțimii; pentru celelalte poziții, size este nedefinit;
  • next[i] înlănțuie circular elementele din fiecare mulțime.

Cu aceasta, operațiile sunt:

  void init(int n) {
    for (int i = 0; i < n; i++) {
      v[i] = i;
      size[i] = 1;
      next[i] = i;
    }
  }

  void union(int x, int y) {
    int fx = find(x);
    if (fx != find(y)) {
      size[x] += size[y];   // încorporăm mulțimea lui ''y'' în cea a lui ''x''
      int i = y;            // suprascriem toți y cu x
      do {
        v[i] = fx;
        i = next[i];
      } while (i != y);
      int nx = next[x];     // conectăm listele înlănțuite, inserând traseul next[y]...y între x și next[x]
      next[x] = next[y];
      next[y] = nx;
    }
  }

  int find(int x) {
    return v[x];
  }

Verificați că union(x, y) face înlănțuirea corectă a listelor și atunci când x și/sau y sunt în mulțimi cu un singur element.

Acest algoritm încă poate face O(n) per operație. Dați un exemplu de suită de n operații care necesită timp total O(n2).

Putem să reducem complexitatea unei operații la O(log n) amortizat printr-o modificare ușoară: întotdeauna renumerotăm componenta mai mică. Așadar trebuie să inserăm în union(x, y) codul:

    ...
    if (fx != find(y)) {
      if (size[x] < size[y]) {
        schimbă x cu y
      }
    ...

Acum, oricare element din vector poate fi renumerotat de cel mult ori. Demonstrați de ce!

Deși ultima reuniune poate face n/2 renumerotări, complexitatea amortizată a n - 1 operații de reuniune nu va depăși O(log n) per operație.

Implementare în O(log* n) per operație

În locul listelor circulare de mai sus, vom stoca fiecare mulțime într-un arbore (ca ierarhia unei companii sau a unei armate). Fiecare element va avea exact un părinte (sau șef). Exponentul unei mulțimi este rădăcina arborelui, care prin convenție este propriul său părinte.

Ne este suficient un singur vector, să zicem p de la „părinte”.

  void init(int n) {
    for (int i = 0; i < n; i++) {
      p[i] = i;
    }
  }

  void union(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx != ry) {
      p[rx] = ry;    // unim rădăcinile între ele
    }
  }

  int find(int x) {
    while (p[x] != x) {
      x = p[x];
    }
    return x;
  }

Totuși, în forma aceasta, algoritmul poate ajunge la complexitate amortizată O(n) per operație. Din nou, dați exemplu de suită de n operații defavorabile. Pentru a ajunge la timp (aproape) constant, facem două optimizări.

Compresia căii

Funcția find(), pe lângă că urcă până la rădăcina unui arbore, modifică toate elementele întâlnite pe parcurs, legându-le direct de rădăcină. Acest lucru se face în două iterații. Intenția este ca, la căutările viitoare, drumul spre rădăcină să fie mult mai scurt.

  int find(int x) {
    int r = x;
    while (p[r] != r) {
      r = p[r];
    }
    while (p[x] != r) {
      int tmp = p[x];
      p[x] = r;
      x = tmp;
    }
    return r;
  }

Reuniunea după înălțime

Stocăm, pentru fiecare rădăcină din arbore, înălțimea subarborelui său, adică distanța maximă între rădăcină și oricare din descendenții ei. Această funcție nu este exactă, căci funcția find() comprimă în permanență arborii, dar este o limită superioară a înălțimii. Când unificăm doi arbori, îl facem pe cel mai scund descendent al celui mai înalt.

  void init(int n) {
    for (int i = 0; i < n; i++) {
      p[i] = i;
      h[i] = 1;
    }
  }

  void union(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx != ry) {
      if (h[rx] < h[ry]) {
        p[rx] = ry;
      } else if (h[rx] > h[ry]) {
        p[ry] = rx;
      } else {
        p[rx] = ry;
        h[ry]++;
      }
    }
  }

Complexitate

Există două limite calculate teoretic pentru complexitatea amortizată a operațiilor union() și find(). Ambele sunt greu de digerat (eu nu le-am citit niciodată până la capăt).

Prima este este , unde definiția funcției este „de câte ori pot aplica logaritmului unui număr până ajung la 1”. De exemplu, pentru că , iar .

A doua limită, calculată de Tarjan, este dată de inversul funcției Ackermann. Cum funcția Ackermann crește incredibil de repede, inversul ei crește foarte încet, având valori mai mici decât 5 pentru orice valori practice ale lui n.

În afara unor discuții savante, considerăm complexitatea structurii de păduri disjuncte ca O(1) amortizat per operație.

Aplicații

Structura de mulțimi disjuncte are aplicații foarte variate, dar pe o temă comună: menținerea informațiilor de conexitate între elemente dintr-un set în care adăugăm legături între elemente. Aceasta se mai numește și conexitate online.

Iată întâi câteva probleme care momentan sunt deasupra cunoștințelor noastre, dar la care vom reveni până la sfârșitul anului școlar.

Conexitate în grafuri: Într-un graf neorientat adăugăm muchii și dorim să știm, în permanență, care din noduri sunt conectate cu care.

Exemplu: pe o hartă sunt n orașe, inițial izolate. Construim străzi care leagă perechi de orașe și dorim să știm, la orice moment și pentru orice pereche de orașe, dacă se poate circula între ele.

Arbori parțiali minimi: Dintr-un graf neorientat vrem să extragem un arbore parțial de cost minim.

Exemplu: Pe o hartă sunt n orașe. Se cunosc distanțele între oricare două orașe. În orașul 1 există o centrală electrică. Dorim să tragem cabluri, cu lungime totală minimă, astfel încât să electrificăm toate orașele.

Cel mai jos strămoș comun: Se dă un arbore și q interogări de forma (x, y), cu x și y noduri. Să se spună, pentru fiecare pereche, care este cel mai jos strămoș comun al ei.

Exemplu: Se dă ierarhia arborescentă a unei companii și q perechi de angajați certați. Doi angajați certați se pot împăca doar dacă se duc la un șef comun pentru mediere. Pentru a nu-l supraîncărca pe președinte, fiecare pereche trebuie trimisă la cel mai jos șef comun.

Detaliem două aplicații care ne sunt la îndemână:

Generarea de labirinturi

Un labirint aleator

Această aplicație este foarte utilă pentru multe jocuri 2D. Să spunem că dorim să generăm un labirint aleator într-o matrice cu m linii și n coloane, astfel încât între oricare două camere să existe un drum unic (circulând pe cele patru direcții NSEV).

Un algoritm este: Pornim cu o matrice cu toți pereții trasați. (În camerele (1,1) și (m, n) lăsăm câte un perete exterior liber, dar aceasta este doar conceptual. Algoritmul nostru se ocupă numai de pereții interiori.) Inițializăm o structură union-find cu m x n elemente izolate.

Apoi, cât timp labirintul nu este conex, alegem un perete la întâmplare și îl demolăm, cu condiția ca prin aceasta să nu închidem un ciclu. Echivalent, pereții acceptabili pentru demolare sunt cei care separă camere din componente conexe diferite.

O implementare în O()) creează un vector cu toți cei pereți, pe care îl randomizează. Apoi îl parcurge de la stânga la dreapta până găsește pereți buni de demolat. Întrucât inițial există mulțimi izolate, iar o unificare reduce cu 1 acest număr, știm sigur că este nevoie de demolări.

Desigur, putem introduce variații. De exemplu, dacă demolăm câțiva pereți în plus față de strictul necesar, în labirint vor începe să apară cicluri.

Jocuri de conexitate

În unele jocuri abstracte, condiția de câștig este conectarea a două porțiuni de pe tabla de joc. Un program care joacă un astfel de joc poate întreține online informații de conexitate pentru a afla rapid dacă a câștigat sau a pierdut.

Jocul Hex se joacă pe o tablă romboidală formată din hexagoane. Albul încearcă să conecteze laturile E-V, iar negrul laturile N-S. Vezi pagina Wikipedia pentru o poziție câștigătoare.

Jocul Havannah se joacă pe o tablă hexagonală. Ambii jucători încearcă să completeze o structură câștigătoare:

  • fie să unească oricare două colțuri ale tablei;
  • fie să unească oricare trei laturi ale tablei (colțurile nu aparțin niciunei laturi);
  • fie să închidă o buclă care să conțină înăuntru un număr nenul de hexagoane.

Vezi pagina Wikipedia pentru imagini cu aceste structuri. Primele două tipuri de structuri pot fi menținute cu structuri de păduri disjuncte. Aparent, jocul Havannah este interesant și pentru că nu există programe bune pentru el. Spațiul de mutări este uriaș, ceea ce îl face greu de tratat algoritmic (ca și la Go sau table).

Inversarea sensului

Ocazional veți întâlni problema inversă: se pornește cu o structură conexă care, treptat, este deconectată. Pe parcurs, se cer informații despre conexitate. Aceasta este o problemă de partiționare, care nu admite o soluție directă la fel de simplă.

Dar, când memoria permite stocarea șirului de operații, o soluție este:

  • Executăm toate operațiile de deconectare, obținând structura finală.
  • Executăm în ordine inversă operațiile, care acum reconectează structura. Putem face aceste operații cu structuri de mulțimi disjuncte.
  • Notăm răspunsurile la interogările de conexitate.
  • Tipărim aceste răspunsuri în ordine inversă.

Exemplu: problema Bile3, problema Ruine.

Temă