Clasele 9-10 lecția 17 - 28 ian 2015

From Algopedia
Revision as of 13:46, 26 January 2015 by Cata (talk | contribs) (Exemplu: problema Regine)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Heaps

Un heap (engl. „grămadă”) este o structură de date care reține n elemente și ne permite următoarele operații:

  • inițializare în O(n)
  • aflarea minimului în O(1)
  • inserare în O(\log n)
  • ștergerea minimului în O(\log n)
  • ștergerea unui element arbitrar în O(\log n), dacă avem un pointer către element (heapul nu admite decât căutări naive în O(n))
  • modificarea valorii unui element arbitrar în O(\log n), dacă avem un pointer către element

Iată un tabel care compară ce vrem de la un heap cu ce putem obține de la structuri de date simple:

operație heap vector neordonat vector ordonat listă înlănțuită ordonată
inițializare O(n) O(1) O(nlogn) O(nlogn) (cum?)
aflarea minimului O(1) O(n) O(1) O(1)
inserare O(\log n) O(1) O(n) O(n)
ștergerea minimului O(\log n) O(n) O(1) O(1)
ștergere O(\log n) O(n) O(n) O(n)
modificare O(\log n) O(1) (cu pointer) O(n) O(n)

Reprezentare

Conceptual, un heap se reprezintă pe un arbore binar complet. Exemplu.

În practică, nu avem nevoie de arbori. Un heap se reprezintă pe un vector.

Analiza complexității. Singurul caz neclar este heapify: de ce este O(n)?

Aplicații

  • sortare (heapsort)
  • coadă de priorități

Extensii

În limita timpului, vom vorbi despre heapuri binomiale. Acestea nu sunt implementabile în timp de concurs. Ele prezintă interes pentru că două heapuri binomiale pot fi reunite în O(\log n), pe când două heapuri binare pot fi reunite doar în O(n).

Probleme

  • De ce lucrăm cu heapuri binare? Nu este mai eficient un heap ternar? Sau cuaternar?
  • Să se interclaseze k vectori sortați a câte n elemente fiecare
    • Există două metode, una cu heap și una fără, ambele de complexitate O(kn log k)
  • Se dă un vector. Să se tipărească, pentru fiecare poziție i, medianul secvenței v[1...i]
  • Se dă un vector nesortat cu n elemente. Să se tipărească cele mai mici k elemente
    • Soluția optimă este prin selecție (găsirea celui de-al k-lea element), dar există două soluții rezonabil de bune, una cu min-heap și una cu max-heap.

Backtracking

Acest capitol reia și expandează noțiunile predate de Cristi acum doi ani.

  • Algoritmul general, implementări recursive versus nerecursive, ideea că orice program recursiv poate fi scris nerecursiv folosind o stivă.
  • Optimizări de backtracking: pe cât posibil alegerea următoarei opțiuni în O(1). Exemplu la problema damelor, folosirea vectorilor de linii, coloane și diagonale.
  • Euristici:
    • un backtracking informat va fi mai eficient decât unul neinformat; optimizările depind de problemă; există unele idei generale.
    • alegerea locului cu număr minim de posibilități (early pruning); exemple:
      • problema calului, selecția în ordinea inversă a numărului posibil de mutări
    • alegerea greedy (drum hamiltonian)
    • funcție de verificare dacă soluția parțială mai are șanse să ducă la o soluție
      • se obține prin relaxarea unora din condiții
      • drum hamiltonian: soluția parțială să fie mai mică decât cel mai bun drum găsit până acum
      • drum hamiltonian: dacă soluția parțială plus numărul de arce rămase ori costul minim al unui arc este mai mare ca soluția optimă găsită până acum, ne putem opri
  • Omorârea backtrackingului. Tehnică folositoare și atunci cînd vreți să măsurați cît timp ruleaza programul vostru:
#include <sys/time.h>

#define MAX_TIME 990 // milisecunde

int startT;
int stop;

void bkt(...) {
  struct timeval tv;

  if (stop) {
    return;
  }
  gettimeofday(&tv, NULL);
  if (tv.tv_sec * 1000 + tv.tv_usec / 1000 - startT > MAX_TIME) {
    stop = 1;
    return;
  }
  for (...) // backtrackingul propriu-zis aici
}

int main() {
  struct timeval tv;

  gettimeofday(&tv, NULL);
  startT = tv.tv_sec * 1000 + tv.tv_usec / 1000; // pastram milisecunde
  stop = 0;
  ... // restul programului aici
  return 0;
}

Exemplu: problema Regine

Pentru a optimiza problema Regine, veți avea nevoie de operații pe biți. Până când le vom discuta și noi, puteți citi lecția de la clasele 11-12.

Varianta neoptimizată

Nu am implementat această variantă, dar merită enumerată. Este un bactracking care pur și simplu generează permutări într-un vector p. Faptul că p[l] = c semnifică amplasarea unei regine la coordonatele (l, c). La fiecare nivel testăm legalitatea amplasării verificând regina de pe linia l cu fiecare regină de pe liniile anterioare. Dacă p[l2] == c2, trebuie ca

  • c ≠ c2 (reginele să nu fie pe aceeași coloană)
  • c - l ≠ c2 - l2 (reginele să nu fie pe aceeași diagonală)
  • c + l ≠ c2 + l2 (reginele să nu fie pe aceeași antidiagonală).

Mă aștept ca varianta neoptimizată să meargă de n (deci 10-15) ori mai lent decât următoarea.

Varianta „naivă”

Cod sursă: Media:nqueens1.cpp

Prima variantă este un backtracking simplu, recursiv. El este deja optimizat în câteva sensuri:

  • La nivelul k din backtracking programul așază o damă pe linia k, deci include deja informația că trebuie să existe exact o damă pe fiecare linie;
  • Programul reține ocuparea pe fiecare coloană, diagonală și antidiagonală. Astfel, legalitatea unui pătrat poate fi testată în O(1).

Programul face efort O(n) pe fiecare linie, căci trebuie să itereze și prin pătratele ilegale. Acest program răspunde la n = 14 în circa 3.3 secunde.

Varianta cu măști

Cod sursă: Media:nqueens2-mask.cpp

Marea problemă a primei variante este că pe ultimele linii, unde mai sunt doar 2-3 pătrate legale, programul încă face un efort O(n) pentru a le găsi. Iată cum procedăm pentru a reduce efortul la O(1) per pătrat legal. În locul vectorului de ocupare pe coloană vom stoca o mască binară, să o numim col, pe n biți. La intrarea în backtracking, masca are valoarea 111...111 (n biți), semnificând că toate coloanele sunt libere. Când amplasăm o damă pe linia l și coloana c, curățăm bitul al c-lea în modul următor:

  col ^= (1 << c);
  backtracking(l + 1);
  col ^= (1 << c);

Așadar, la orice nivel din backtracking masca col reține coloanele încă disponibile (codificate prin bitul 1). Cum putem itera prin această mască în O(1) per bit setat? Prin metoda lui Kernighan de a extrage rapid ultimul bit setat:

  unsigned mask = col; // creăm o copie pe care o vom distruge
  while (mask) {
    unsigned lsb = mask & (-(signed)mask); // lsb este cel mai din dreapta bit 1
    col ^= lsb;                            // marcăm coloana ca ocupată
    backtracking(l + 1);
    col ^= lsb;
    mask ^= lsb;                           // eliminăm bitul din mască
  }

Numai cu această optimizare, timpul de execuție scade la 2,2 secunde.

Desigur, putem proceda la fel și pentru diagonale și antidiagonale. Trebuie să avem grijă, căci numărul acestora este de 2 * n - 1, deci vom opera pe numere cu 2 * n - 1 biți. Dintre aceștia, trebuie să-i alegem pe cei n care ne interesează pe linia curentă. În final, iată cum obținem masca pătratelor care sunt legale pe linia l, adică au libere și coloana, și ambele diagonale:

  unsigned mask = col & (anti >> l) & (diag >> (n - 1 - l));

După optimizarea diagonalelor, timpul de execuție scade la 0,7 secunde.

Varianta cu măști și simetrie

Cod sursă: Media:nqueens3-mask-symmetry.cpp

Putem reduce în continuare timpul de execuție observând că nu are sens să încercăm toate amplasările reginei de pe prima linie. Prin oglindire, este suficient să parcurgem doar prima jumătate a liniei, apoi să înmulțim rezultatul cu 2. Trebuie să avem grijă la table de mărime impară, unde coloana din mijloc nu are pereche și doar coloanele anterioare ei trebuie înmulțite cu doi.

Cu această optimizare, timpul de execuție scade la 0,36 secunde. Programul optimizat merge de 9 ori mai repede!

Desigur, din punct de vedere teoretic am reușit doar să împingem valoarea-limită a lui n cu o unitate mai încolo. Dar din punct de vedere practic, un factor de 9 este uriaș.

Temă