Sa ne imaginam ca parcurgem arborele dat in preordine si numerotam muchiile
incepand cu 1, in ordinea parcurgerii. Ca sa nu ametim, am numerotat nodurile
cu numere si muchiile cu cifre. Pentru arborele din enunt, vom obtine
urmatoarea ordine:
5
/ | \
A/ E| F/
/ | \
2 3 0
/ \
C/ D/
/ \
1 4
|
B|
|
6
Observatia cheie este ca timpul unei muchii este mai mare decat timpii tuturor
muchiilor de sub ea si mai mic decat timpul muchiei de deasupra ei. Sa spunem
acum ca vrem sa aflam LCA(4,6). Ce avem de facut? Sa aflam calea (unica) dintre
4 si 6, sa gasim muchia cu timpul cel mai mare de pe aceasta cale, si sa
tiparim nodul superior al acestei muchii. In cazul nostru, vom gasi calea
6-1-3-4, cu muchiile etichetate cu B, C si D. Muchia cu timpul cel mai mare
este D, iar nodul ei superior este 3. Asadar LCA(4, 6)=3. Pentru a afla
LCA(4,5), gasim calea 4-3-5, cu muchiile D si E. Muchia de cost maxim este E,
iar nodul ei superior este 5, deci LCA(4,5)=5.
Va puteti convinge singuri ca algoritmul functioneaza pentru orice alte noduri.
O exceptie trebuie facuta cand se cauta LCA(X,X), pentru ca nu exista o cale
intre X si X. In acest caz raspunsul este evident X. Pentru a fi si mai
concisi, si pentru a elimina si acest caz particular, putem reformula metoda
astfel: cautam calea intre X si Y, iar LCA(X,Y) este cel mai inalt nod de pe
aceasta cale.
Cateva cuvinte despre detaliile practice, inainte de a vedea care este
"scursura" (the flaw) acestui algoritm. Nu trebuie in nici un caz sa construim
efectiv calea de la X la Y. Ne intereseaza numai sa gasim nodul cel mai inalt
de pe aceasta cale. Ne putem folosi de faptul ca muchiile sunt etichetate
crescator de la frunze spre radacina. Daca pomenim si cuvantul "interclasare",
cred ca totul se lamureste. Algoritmul (in termeni naivi) este:
0. Pune un deget pe X si unul pe Y
1. Cat timp cele doua degete nu indica acelasi nod
a) daca muchia de deasupra lui X are cost mai mic decat muchia de
deasupra lui Y, atunci misca degetul de pe X pe tatal lui X
b) altfel muta degetul de pe Y pe tatal lui Y.
2. LCA(X,Y) este nodul pe care imi tin cele doua degete.
De exemplu, pentru X=4 si Y=6,
0. Punem un deget pe 4 si unul pe 6
1. Comparam muchia (4,3) cu muchia (6,1) si mutam degetul de pe 6 pe 1
1'. Comparam muchia (4,3) cu muchia (1,3) si mutam degetul de pe 1 pe 3
1". Comparam muchia (4,3) cu muchia (3,5) si mutam degetul de pe 4 pe 3
2. Intrucat ambele degete il indica pe 3, LCA(4,6)=3.
Sa analizam complexitatea acestui algoritm. Preprocesarea (adica etichetarea
muchiilor) costa O(N), fiind vorba despre o simpla parcurgere in postordine.
Desigur, nu este suficient sa tinem minte numai tatal unui nod, ci este nevoie
sa ii construim si lista copiilor, dar si aceasta dureaza tot O(N).
Partea mai proasta este ca raspunsul la LCA(X,Y) se poate da in O(L), unde L
este lungimea caii dintre X si Y. Dar L poate fi O(N) pentru un arbore
degenerat (un lant). Deci M intrebari bine (sau rau) alese pot necesita un
timp O(M*N).
Ce ne facem? Scoatem din buzunar inca un cuvant cheie, "structura de multimi
disjuncte". Va trebui sa reorganizam arborele nostru in asa fel incat
inaltimea sa sa nu depaseasca log N nivele. In acest caz, calea cea mai lunga
nu va depasi 2*log N muchii, si vom putea raspunde la M intrebari in
O(M*log N). Desigur, reorganizarea arborelui va da peste cap relatiile de
"stramos" si "stramos comun", deci va trebui sa retinem si informatii despre
forma initiala. Sa privim parcurgerea in postordine ca pe un proces care
porneste cu N noduri separate si la fiecare pas adauga o muchie in arbore,
unind in acest fel arbori din ce in ce mai mari:
5
. . .
. . .
. . .
2 3 0
. . T = 0
. . Toate nodurile sunt deconectate
. . Avem arborii 0, 1, 2, 3, 4, 5, 6
1 4
.
.
.
6
5
/ . .
A/ . .
/ . .
2 3 0
. . T = 1
. . Nodurile 2 si 5 devin conectate
. . Avem arborii 0, 1, (2,5), 3, 4 si 6
1 4
.
.
.
6
5
/ . .
A/ . .
/ . .
2 3 0
. . T = 2
. . Nodurile 6 si 1 devin conectate
. . Avem arborii 0, (1,6), (2,5), 3, 4
1 4
|
B|
|
6
.... si asa mai departe ....
Pentru a afla LCA(X,Y) trebuie sa "pandim" momentul cand o muchie completeaza
o cale intre X si Y. De exemplu, calea intre 6 si 2 se va completa in momentul
adaugarii muchiei 3-5. Fie "e" aceasta muchie importanta. Atunci LCA(X,Y) este
nodul superior al lui "e". In exemplul nostru, LCA(6,2)=5.
Cei care cunosc notiunea de "structura de multimi disjuncte" pot sari
urmatoarele randuri, pana la "******".
Vom numi structura de multimi disjuncte "DS", de la denumirea in engleza
"Disjoint Sets". Ea furnizeaza doua operatii rapide asupra unor multimi de
obiecte, oricare doua multimi fiind disjuncte:
1) Reuniunea a doua multimi (UNION)
2) Aflarea multimii din care face parte un obiect (FIND)
Sa consideram chiar exemplul de mai sus, in care obiectele sunt nodurile
grafului. Adaugam pe rand muchiile grafului, in postordine, adaugarea unei
muchii insemnand reunirea obiectelor de la cele doua capete ale muchiei.
0 1 2 3 4 5 6 Toate obiectele sunt separate
0 1 3 4 5 6 UNION(2,5).
| Acum obiectele 2 si 5 sunt in aceeasi
2 multime.
0 1 3 4 5 UNION(1,6)
| |
6 2
0 1 4 5 UNION(1,3)
/ \ |
6 3 2
Hop! A aparut o diferenta fata de forma arborelui! Dar pe noi nu ne intereseaza
sa pastram forma arborelui, ci ne intereseaza numai sa indicam ca la momentul
T=3, nodurile 6, 1 si 3 fac parte din aceeasi componenta. Deci dorim numai
sa legam cumva un nod din multimea lui 1 cu un nod din multimea lui 3.
0 1 5 UNION(4,3)
/|\ | La momentul T=4 al postordinii,
6 3 4 2 obiectele 1, 3, 4 si 6 au fost unite.
0 5 UNION(3,5)
/ \
1 2
/|\
6 3 4
5 UNION(0,5)
/|\
1 2 0
/|\
6 3 4
Acum sa formalizam ideile, precum si implementarile pentru UNION si FIND,
si sa vedem care e castigul. Pentru fiecare multime alegem un EXPONENT al
ei, un element privilegiat, o "eticheta". Intrucat am reprezentat multimile
ca pe niste arbori, este natural ca exponentul sa fie radacina arborelui.
Operatia FIND(X) nu are decat sa intoarca valoarea radacinii arborelui din
care face parte X. Vom recunoaste ca doua elemente X si Y sunt in aceeasi
multime daca FIND(X)=FIND(Y).
Operatia UNION(X,Y) nu are voie sa traseze o muchie directa intre X si Y,
pentru ca aceasta ar da peste cap structura arborescenta. Dar, daca tot nu
tinem mortis sa unim obiectul X cu obiectul Y, ci multimea lui X cu multimea
lui Y, ce-ar fi sa unim radacina lui X cu radacina lui Y? De fapt, asta am
facut mereu in imaginile de mai sus. De exemplu UNION(3,5) a tras o muchie
intre 1 si 5, pentru ca 1 este radacina arborelui lui 3.
Cum implementam asa ceva? Simplu, cu un vector si doua proceduri. Vectorul
va retine legatura de tip "tata" a fiecarui nod. Am botezat acest vector
DSF de la "Disjoint Set Father". In imaginea finala a lui DS, DSF[3]=1,
DSF[1]=5 s.a.m.d. Initial F[X]=-1 pentru fiecare X, insamnand ca X este singur
in componenta lui si nu este subordonat nimanui.
Atunci:
1) FIND(X) trebuie sa porneasca de la X si sa mearga din tata in tata pana
ajunge la un nod Y cu F[Y]=-1, caz in care Y este exponentul multimii
2) UNION(X,Y) trebuie sa afle:
TataX=FIND(X), TataY=FIND(Y)
si sa seteze F[TataX]=TataY, sau F[TataY]=TataX.
In acest fel radacinile celor doua multimi sunt legate.
Complexitatea acestor operatii. Se vede ca UNION efectueaza doua operatii
FIND si o operatie in timp constant. La randul ei, FIND(X) parcurge calea
de la X la radacina arborelui sau din DS. Avem deci interesul sa legam
nodurile in asa fel incat arborii din DS sa ramana cat mai "turtiti". Printr-o
imbunatatire intuitiva, ne putem asigura ca arborii nu depasesc inaltimea
O(log N). Ideea este ca la o operatie UNION sa legam intotdeauna radacina
arborelui mai scund de radacina arborelui mai inalt. De exemplu, la operatia
UNION(0,5) de mai sus, l-am legat pe 0 de 5 si am obtinut un arbore de inaltime
3. Daca l-am fi legat pe 5 de 0 am fi obtinut un arbore de inaltime 4.
Asadar complexitatea ambelor operatii este O(log N).
***************************************************************************
Pentru a da lovitura de gratie programului nostru si a va lasa in sfarsit sa
va duceti pe la treburile voastre, avem nevoie de urmatoarele structuri de
date:
1) O asemenea structura DS in care muchiile sunt etichetate cu momentul
adaugarii lor:
5
/ | \
E/ A| \F
/ | \
1 2 0
/ | \
B/ C| D/
/ | \
6 3 4
2) Un vector cu postordinea nodurilor in arborele original.
T = A B C D E F G
P = 2 6 1 4 3 0 5
Remarcam din nou ca muchiile in DS sunt etichetate crescator de la frunze
spre radacina. Algoritmul functioneaza astfel:
LCA(X,Y):-
o Cauta in DS muchia cea mai tarzie pe calea dintre X si Y
o Fie Tz momentul la care aceasta muchie a fost adaugata
o Returneaza parintele (in arborele original) al nodului P[Tz].
Exemple:
o X=2, Y=4
Muchiile dintre 2 si 4 in DSF sunt A, D si E. Cea mai tarzie este E
La momentul E a fost parcurs nodul 3, tatal acestuia fiind nodul 5
Raspuns: 5
o X=4, Y=6
Observati in primul rand ca raspunsul trebuie sa fie 3, dar nodul 3 nici nu
apare pe calea dintre 4 si 6 in DS!
Muchiile dintre 4 si 6 sune B si D. Cea mai tarzie este D.
La momentul D a fost vizitat nodul 4, tatal acestuia fiind 3
Raspuns: 3
Complexitate:
1) Preprocesarea inseamna o parcurgere in postordine a arborelui, dar la
fiecare pas se executa o operatie UNION (nodul X care este vizitat este
reunit cu tatal sau). Intrucat UNION costa O(log N), preprocesarea costa
O(N log N)
2) Aflarea lui LCA(X,Y): Aflarea celei mai tarzii muchii dintre X si Y se face
de asemenea prin interclasare, deci raspunsul se da in O(lungimea caii
dintre X si Y), care de data aceasta este O(log N).
3) Complexitatea totala pentru preprocesare + M query-uri:
O(N log N + M log N). Lasam ca tema pentru acasa descoperirea optimizarii
care permite o preprocesare in numai O(N).
Acesta este un exemplu destul de tipic in care e bine sa pierd mult timp
cu preprocesarea ca sa castig pe urma atunci cand mi se pun multe intrebari.
Daca as fi avut de raspuns la o singura intrebare (M=1), primul algoritm ar fi
raspuns in O(N), iar al doilea in O(N log N).
Daca tot am scris tone de explicatii, sper sa fi meritat si sa ma fi facut
clar. OBSERVATIE - sursa e cam de trei ori mai mica decat explicatiile :)
|
|
