Clasa VII/VIII lecția 20 - 11 mar 2014

From Algopedia
Jump to: navigation, search

Tema - discuţie

Mică discuţie despre cum v-aţi făcut sau nu temele şi despre problema arrows.

Lecţie

Concurs

Concurs clasele 7/8

Algoritmul union-find

Acestă problemă, precum şi rezolvarea ei, este o unealtă foarte utilă din trusa de scule a algoritmistului. Să definim problema:

Dată o mulţime A de valori de la 1 la N definim submulţimi disjuncte pe această mulţime, astfel încît aceste submulţimi să acopere mulţimea originală A. Apoi începem să reunim unele dintre aceste mulţimi. Reuniunea se face menţionînd două elemente ale submulţimilor ce se doresc reunite (dacă elementele se găsesc deja în aceeaşi submulţime nu vom face nimic). După ce efectuăm aceste operaţii de reuniune dorim să răspundem la întrebarea 'ce submulţimi avem?'.

Cu alte cuvinte, cunoscînd N şi ştiind că iniţial fiecare număr face parte din propria submulţime şi apoi dîndu-se mai multe perechi de numere (ai, aj) cu semnificaţia "mulţimea din care face parte ai se reuneşte cu mulţimea din care face parte aj" trebuie ca în final să spunem ce submulţimi există.

Pentru a implementa algoritmul vom avea nevoie de două operaţii:

  • reuneşte două mulţimi (union)
  • găseşte mulţimea unui element (find)

De aici şi denumirea problemei union-find. În română se regăseşte sub numele de colecţie de mulţimi disjuncte, dar denumirea de union-find tinde să fie mai folosită în cercurile de algoritmişti.

Structura de date

Nu voi elabora decît varianta optimală. Vom memora submulţimile într-un mod ingenios: fiecare element al unei submulţimi va ţine mine un şef al său din mulţime. Întocmai ca într-o companie, fiecare element al unei submulţimi va raporta unui şef, şefii vor raporta altor şefi şi aşa mai departe pînă ce se ajunge la şeful unic, conducătorul submulţimii. El nu are şef şi este considerat reprezentantul acelei submulţimi. Cum memorăm acest lucru? Printr-un simplu vector de şefi în care elementul sef[i] este numărul din mulţimea 1..N care este şeful lui i. Ce punem în elementele şefi? Pentru a le distinge de elementele subalterni fiecare şef este propriul lui şef. Dacă elementul i este şef atunci sef[i] = i. O alternativă la această reprezentare, dacă "sacrificăm" elementul 0, este să memorăm zero ca şef fictiv pentru elementele reprezentative ale mulţimilor.

Find

Cum aflăm care este mulţimea din care face parte un element i? Răspunsul este destul de simplu, vom merge la şeful lui i, apoi la şeful şefului lui şi aşa mai departe pînă ce găsim reprezentantul mulţimii.

Union

Cum efectuăm reuniunea a două mulţimi? Şi aici răspunsul este cel aşteptat: găsim uber-şefii, reprezentanţii celor două mulţimi, folosind Find, iar apoi îl facem pe unul din şefi să fie subalternul direct al celuilalt şef. În acest fel oricare element din noua mulţime formată va raporta la un singur şef, reprezentantul noii mulţimi.

Compresia căii

Din lipsă de timp nu voi analiza complexităţile celor două operaţii. Poate într-o nouă iteraţie a acestei pagini :) E suficient să spunem că soluţia prezentată este O(N2). Putem îmbunătăţi această complexitate la O(N log N) cu mici modificări.

Tot din lipsă de timp voi sări direct la algoritmul care, din punct de vedere al oricărei valori utile a lui N, este liniară, O(N), fără a demonstra acest lucru. Aş vrea să învinuiesc tot lipsa de timp, dar nu este cazul, căci demonstraţia mă depăşeşte (nici măcar nu am căutat-o, deoarece funcţia lui Ackermann mă intimidează - prea mulţi n).

Pentru a obţine cel mai eficient algoritm cunoscut avem nevoie de două optimizări, din care, în experienţa mea, una este necesară, drept pentru care o voi sări pe a doua. Optimizarea importantă este denumită compresia căii şi face un lucru foarte simplu: schimbă puţin funcţia Find ca, atunci cînd dorim să aflăm care este şeful nodului i, să lege toţi şefii parcurşi direct la şeful suprem. Cu alte cuvinte vom parcurge aceiaşi şefi intermediari pînă la şeful suprem, dar odată găsit va trebui să ne întoarcem la şefii intermediari şi să le schimbăm şeful. Aceasta duce aproximativ la o dublare a opreaţiilor efectuate de Find. Dar, precum spunea astronatul Neil Armstrong, un pas mic pentru un om poate fi un pas uriaş pentru omenire. O mică modificare ce duce la dublarea timpului lui Find duce la o scurtare fantastică a următoarelor operaţiuni Find.

Această optimizare poartă denumirea de compresia căii, sau, în engleză, path compression.

Memoizare

Memoizarea este o metodă de a face un program mai rapid fără a-i schimba modul în care el funcționează. Ideea ei este ca atunci cînd efectuăm un calcul scump să păstrăm valoarea calculată într-un tablou pentru a economisi timp în cazul cînd în viitor vom avea din nou nevoie de acea valoare. Să o învățăm prin exemple.

Exemplul 1

Să presupunem că ni se dau n numere a0, a1, ..., an-1 și ni se cere să afișăm factorialele acelor numere modulo k. O soluție naivă ar putea fi următoarea:

for ( i = 0; i < n; i++ ) {
  p = 1;
  for ( j = 2; j < a[i]; j++ )
    p = (p * j) % k;
  printf( "%d ", p );
}

Să calculăm complexitatea tipului de execuție: pentru fiecare număr ai vom face O(ai) înmulțiri, drept pentru care complexitatea soluției este O(suma(ai)). Desigur că putem face un program mai eficient care calculează un vector fact[i] unde fact[i] este i! (i factorial). Acest vector se poate calcula în O(max(ai)), după care printr-o parcurgere a numerelor ai vom putea calcula rezultatul ceea ce duce la o complexitate optimă de O(n + max(ai)).

Însă în unele cazuri nu este ușor să schimbăm radical programul pentru a scrie o soluție mai eficientă decît soluția naivă. Cum putem folosi tehnica memoizării pentru a modifica foarte puțin soluția brută și a o aduce la complexitate optimă? Am putea ca de fiecare dată cînd calculăm ai! să păstrăm rezultatul într-un vector la poziția ai. Vom păstra, de asemenea și toate factorialele intermediare calculate pe parcurs. Atunci cînd vom avea nevoie de calculul unui factorial vom merge în jos pînă la primul factorial calculat. Iată implementarea:

fact[1] = 1; // pentru a ne opri la final
for ( i = 0; i < n; i++ ) {
  j = a[i];
  while ( fact[j] == 0 )      // cautam in jos primul factorial calculat
    j--;
  p = fact[j];
  for ( j++; j <= a[i]; j++ ) // calculam toate valorile pina la a[i]
    fact[j] = (fact[j-1] * j) % k;
  printf( "%d ", fact[j] );
}

Ce complexitate în timp are această soluție? Deoarece ea nu repetă calcule în vectorul fact rezultă că fiecare element al vectorului va fi calculat cel mult odată, în timp O(1), deci soluția va fi optimă, O(n+max(ai)). Observați că am obținut aceeași complexitate optimă dar fără a schimba structura algoritmului nostru naiv, ci doar memorînd rezultate parțiale într-un vector. Aceasta este exact ideea memoizării.

Exemplul 2

Un exemplu clasic este funcția recursivă bine cunoscută care calculează al n-ulea număr din șirul lui Fibonacci. Un mod naiv și direct de a scrie funcția este:

int fib( int n ) {
  if ( n == 1 || n == 2 )
    return 1;
  return fib( n-1 ) + fib( n-2 );
}

Problema cu această implementare este că va chema de multe ori funcția fib cu aceleași valori, refăcînd frecvent aceleași calcule. De exemplu, fib(n-2) se va calcula de două ori, fib(n-3) se va calcula de 3 ori, iar fib(n-4) se va calcula de 5 ori! Faceți desenul și convingeți-vă. Numărul de apeluri crește exponențial.

O soluție ar fi să implementăm funcția nerecursiv, așa cum deja știm. În unele cazuri acest lucru complică foarte mult codul, deoarece implică o schimbare radicală. Putem însă modifica puțin funcția fib pentru a memora valoarea o dată calculată, astfel încît la un următor apel să o returneze direct. Pentru aceasta vom folosi un vector de valori, să-i spunem val, în care vom memora valorile șirului lui Fibonacci gata calculate. Iată modifcarea:

int val[1000] = { 1, 1 };

// exemplu de funcție fibonacci implementată folosind memoizare
int fib( int n ) {
  if ( val[n] == 0 ) // inca necalculat
    val[n] = fib( n-1 ) + fib( n-2 ); // il calculam in tabel
  return val[n]; // returnam valoarea din tabel
}

Exemplul 3

O astfel de problemă este și problema creioane. Rezolvarea forță brută este relativ ușor de scris, dar nu se va încadra în timp pentru teste mari deoarece are complexitate O(n2). O putem însă modifica ca atunci cînd calculăm înălțimea unei grămezi de creioane să calculăm înălțimea fiecărui creion din grămadă. În acest fel vom avea O(1) calcule per element, ceea ce duce la o soluție optimală liniară, O(n).

Temă

Tema 20 clasele 78

Rezolvări aici [1]