Clasa VII/VIII lecția 25 - 17 mar 2015

Tema lecţia 22 - rezolvări

Rezolvări aici [1]

Tema lecţia 24 - rezolvări

Rezolvări aici [2]

Lecţie

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 (a_i, a_j) cu semnificaţia "mulţimea din care face parte a_i se reuneşte cu mulţimea din care face parte a_j" 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(N²). Putem îmbunătăţi această complexitate la O(N log N) cu mici modificări, dar nu le vom prezenta aici.

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.

Temă

Clasa a 7-a

• Tema 25 clasa a 7^a
  • disjoint
  • bile3
• Opţional: Tema 25 clasa a 7^a opţională
  • flota
  • ruine
• Opțional: tema de la clasa a 8^a (probleme date la baraj gimnaziu)

Clasa a 8-a

• Tema 25 clasa a 8^a
• Opţional: tema opţională de la clasa a 7^a
  • joc7
  • 2numere