h1. LCA: Lowest common ancestor
(Creat de '_wickedman_':user/wickedman la data de _2004-11-08_ categoria _Arbori_, autor(i) _Miron Emilian_)
*Continut scurt:*
Problema luata in discutie este ca, avand un arbore dat sa putem raspunde rapid la multe intrebari de genul care este stramosul comun cel mai apropiat dintre doua noduri din arbore.
==Include(page="template/raw")==
Problema luata in discutie este ca, avand un arbore dat sa putem raspunde rapid la multe intrebari de genul care este stramosul comun cel mai apropiat dintre doua noduri din arbore.
*Continut lung:*
Problema luata in discutie este ca, avand un arbore dat sa putem raspunde rapid la multe intrebari de genul care este stramosul comun cel mai apropiat dintre doua noduri din arbore.
Exemplu
Pentru arborele din imagine, avem ca exemplu urmatoarele query-uri:
lca(2,3) = 1
lca(4,5) = 1
lca(5,6) = 3
lca(1,5) = 1
lca(5,3) = 3
Aplicabilitate
Dandu-se un arbore cu costuri sa se raspunda rapid la intrebari de genul: care este distanta minima intre doua noduri date?
Solutie:
* agatam arborele intr-un nod oarecare si obtinem un arbore cu radacina.
* pentru fiecare nod precalculam dist[i], reprezentand distanta sa pana la radacina.
* precalculam cele necesare pt LCA.
* raspundem la intrebari de forma d(i,j) prin dist[i] + dist[j] * 2 * dist(lca(i,j)).
* Probleme adhoc care se reduc sau folosesc LCA. (de exemplu problema petrol (baraje Slatina 2003).
Mod de calcul
In prima etapa a algoritmului facem o parcurgere euleriana a arborelui dat. O parcurgere euleriana este o parcurgere a arborelui in ordinea din figura: se parcurg fii si se intercaleaza intre ei tatal, obtinand o parcurgere continua.
Mai exact pentru fiecare nod procedam astfel, incepand cu radacina:
* daca nodul curent este frunza il adaugam la parcurgere
* daca are fii atunci il punem la inceput, la sfarsit si intre parcurgerile euler ale fiilor
* Cand facem aceasta parcurgere retinem de asemenea si urmatoarele informatii suplimentare:
* adancimea fiecarui nod din parcurgere, obtinand un sir de adancimi
* una din pozitiile pe care fiecare nod apare in parcurgere
Ideea este ca lca(i, j) este chiar nodul cu cea mai mica adancime intre pozitiile lui i si a lui j in parcurgere. Pentru graful din figura avem:
Euler: 12421353631
Adancimi: 12321232321
^ ^
4 3
lca(4,3)=min(adancimi de la pos[4] la pos[3]) = 1
Am redus problema la aflarea minimului intre doua pozitii a unui sir (RMQ * range minimum query). Aceasta subproblema o putem rezolva optim folosind arbori de intervale, sau o metoda folosind spatiu supraliniar (NlgN) a minimelor pe intervale de puteri de 2, incepand de la pozitia i. Timpul de preprocesare este O(N) pentru arbori de intervale si O(NlgN) pentru a doua metoda. Timpul de interogare este O(lgN);
Vom discuta metoda cu spatiu NlgN. Calculam minimele inductiv, pastrand min[i][k] = minimul pe intervalui i..i + 2^k * 1 (de lungime 2^k), si minpos[i][k] pozitia minimului de pe intervalul i..i + 2^k * 1.
pt k = 0
min[i][0] = a[i], minpos[i][0] = i;
pt k > 0
min[i][k] = minim(min[i][k-1],min[i+2^(k-1)][k-1])
minpos[i][k] = pozitia minimului
(minpos[i][k-1] sau minpos[i+2^(k-1)][k-1])
Pentru query intre pozitiile l, r procedam astfel:
Fie k cel mai mare nr astfel incat 2^k <= lungimea intervalului (r * l + 1)
min(l, r) = minim( min[l][k], min[r * 2^k + 1][k])
pozmin(l, r) = pozitia minimului
Daca l = pos[i], r = pos[j] (pos[i] < pos[j]) la sfarsitul query-ului euler[pozmin] este chiar lca(i, j).
==Include(page="template/raw")==
Problema luata in discutie este ca, avand un arbore dat sa putem raspunde rapid la multe intrebari de genul care este stramosul comun cel mai apropiat dintre doua noduri din arbore.
Exemplu
Pentru arborele din imagine, avem ca exemplu urmatoarele query-uri:
lca(2,3) = 1
lca(4,5) = 1
lca(5,6) = 3
lca(1,5) = 1
lca(5,3) = 3
Aplicabilitate
Dandu-se un arbore cu costuri sa se raspunda rapid la intrebari de genul: care este distanta minima intre doua noduri date?
Solutie:
* agatam arborele intr-un nod oarecare si obtinem un arbore cu radacina.
* pentru fiecare nod precalculam dist[i], reprezentand distanta sa pana la radacina.
* precalculam cele necesare pt LCA.
* raspundem la intrebari de forma d(i,j) prin dist[i] + dist[j] * 2 * dist(lca(i,j)).
* Probleme adhoc care se reduc sau folosesc LCA. (de exemplu problema petrol (baraje Slatina 2003).
Mod de calcul
In prima etapa a algoritmului facem o parcurgere euleriana a arborelui dat. O parcurgere euleriana este o parcurgere a arborelui in ordinea din figura: se parcurg fii si se intercaleaza intre ei tatal, obtinand o parcurgere continua.
Mai exact pentru fiecare nod procedam astfel, incepand cu radacina:
* daca nodul curent este frunza il adaugam la parcurgere
* daca are fii atunci il punem la inceput, la sfarsit si intre parcurgerile euler ale fiilor
* Cand facem aceasta parcurgere retinem de asemenea si urmatoarele informatii suplimentare:
* adancimea fiecarui nod din parcurgere, obtinand un sir de adancimi
* una din pozitiile pe care fiecare nod apare in parcurgere
Ideea este ca lca(i, j) este chiar nodul cu cea mai mica adancime intre pozitiile lui i si a lui j in parcurgere. Pentru graful din figura avem:
Euler: 12421353631
Adancimi: 12321232321
^ ^
4 3
lca(4,3)=min(adancimi de la pos[4] la pos[3]) = 1
Am redus problema la aflarea minimului intre doua pozitii a unui sir (RMQ * range minimum query). Aceasta subproblema o putem rezolva optim folosind arbori de intervale, sau o metoda folosind spatiu supraliniar (NlgN) a minimelor pe intervale de puteri de 2, incepand de la pozitia i. Timpul de preprocesare este O(N) pentru arbori de intervale si O(NlgN) pentru a doua metoda. Timpul de interogare este O(lgN);
Vom discuta metoda cu spatiu NlgN. Calculam minimele inductiv, pastrand min[i][k] = minimul pe intervalui i..i + 2^k * 1 (de lungime 2^k), si minpos[i][k] pozitia minimului de pe intervalul i..i + 2^k * 1.
pt k = 0
min[i][0] = a[i], minpos[i][0] = i;
pt k > 0
min[i][k] = minim(min[i][k-1],min[i+2^(k-1)][k-1])
minpos[i][k] = pozitia minimului
(minpos[i][k-1] sau minpos[i+2^(k-1)][k-1])
Pentru query intre pozitiile l, r procedam astfel:
Fie k cel mai mare nr astfel incat 2^k <= lungimea intervalului (r * l + 1)
min(l, r) = minim( min[l][k], min[r * 2^k + 1][k])
pozmin(l, r) = pozitia minimului
Daca l = pos[i], r = pos[j] (pos[i] < pos[j]) la sfarsitul query-ului euler[pozmin] este chiar lca(i, j).
h1. LCA: Lowest common ancestor
(Categoria _Algoritmi_, Autor _Emilian Miron_)
Problema luata in discutie este ca, avand un arbore dat, sa putem raspunde rapid la multe intrebari de genul: _"Care este stramosul comun cel mai apropiat dintre doua noduri din arbore?"_.
(toc)*{text-align:center} *Continut*
* 'Exemplu':lowest-common-ancestor#exemplu
* 'Aplicabilitate':lowest-common-ancestor#aplicabilitate
* 'Mod de calcul':lowest-common-ancestor#calcul
!> Lowest-common-ancestor?euler.jpg 80%!
h2(#exemplu). Exemplu
Pentru arborele din imagine, avem ca exemplu urmatoarele query-uri:
* $lca(2,3) = 1$
* $lca(4,5) = 1$
* $lca(5,6) = 3$
* $lca(1,5) = 1$
* $lca(5,3) = 3$
h2(#aplicabilitate). Aplicabilitate
Dandu-se un arbore cu costuri sa se raspunda rapid la intrebari de genul: _"care este distanta minima intre doua noduri date?"_. O solutie pentru problema de fata ar fi:
* agatam arborele intr-un nod oarecare si obtinem un arbore cu radacina
* pentru fiecare nod $i$ precalculam {$dist{~i~}$}, reprezentand distanta sa pana la radacina
* precalculam cele necesare pentru algoritmul de _Lowest Common Ancestor_
* distanta dintre doua noduri oarecare $i$ si $j$ va fi egala cu {$dist{~i~} + dist{~j~} - 2*dist{~lca(i,j)~}$}
h2(#calcul). Mod de calcul
In prima etapa a algoritmului facem o parcurgere euleriana a arborelui dat. O parcurgere euleriana este o parcurgere a arborelui in ordinea din figura: se parcurg fiii si se intercaleaza intre ei tatal, obtinand o parcurgere continua.
Mai exact pentru fiecare nod procedam astfel, incepand cu radacina:
* daca nodul curent este frunza il adaugam la parcurgere
* daca are fii atunci il punem la inceput, la sfarsit si intre parcurgerile euler ale fiilor
Cand facem aceasta parcurgere retinem de asemenea si urmatoarele informatii suplimentare:
* adancimea fiecarui nod din parcurgere, obtinand un sir de adancimi
* una din pozitiile pe care fiecare nod apare in parcurgere
Ideea este ca {$lca(i, j)$} este chiar nodul cu cea mai mica adancime intre pozitiile lui $i$ si a lui $j$ in parcurgere. Pentru graful din figura de mai sus avem:
table(example). |_. Euler|_. Adancimi|
|12421353631|12321232321|
Pentru perechea de noduri ({$4, 3$}), avem {$lca(4, 3)$} egal cu nodul care se gaseste intre {$poz{~4~}$} si {$poz{~3~}$} in parcurgerea euler si are adancimea minima. Acest nod este $1$, deci {$lca(4, 3) = 1$}.
Am redus problema la aflarea minimului intre doua pozitii ale unui sir ({_Range Minimum Query_}). Aceasta subproblema o putem rezolva optim folosind arbori de intervale, sau o metoda folosind spatiu supraliniar ({$Nlog{~2~}N$}) a minimelor pe intervale de puteri ale lui {$2$}, incepand de la pozitia {$i$}. Timpul de preprocesare este {$O(N)$} pentru arbori de intervale si {$O(Nlog{~2~}N)$} pentru a doua metoda. In ambele variante timpul de interogare este {$O(log{~2~}N)$}.
Vom prezenta in continuare metoda cu spatiu supraliniar. Calculam minimele inductiv, pastrand:
* {$min{~i,k~}$} = minimul pe intervalul {$[i...i+2^k^-1]$} (de lungime {$2^k^$}), si
* {$minpos{~i,k~}$} = pozitia minimului de pe intervalul {$[i...i+2^k^-1]$}.
Acest tablou va fi construit recursiv astfel: pentru $k = 0$ avem {$min{~i,0~} = a{~i~}$} si {$minpos{~i,0~} = i$}, iar pentru k > 0 avem:
* {$min{~i,k~}$} = minim({$min{~i,k-1~}$}, {$min{~i+2^k-1^,k-1~}$})
* {$minpos{~i,k~}$} = pozitia minimului ({$minpos{~i,k-1~}$} sau {$minpos{~i+2{^k-1^},k-1~}$})
Pentru _query_ intre pozitiile $l$ si $r$ procedam astfel: fie $k$ cel mai mare numar astfel incat {$2^k^$} ≤ lungimea intervalului {$(l, r)$}.
{$min(l, r)$} = minim( {$min{~l,k~}$}, {$minimul pe intervalul (l+2^k^, r)$})
{$pozmin(l, r)$} = pozitia minimului intre $l$ si $r$
Daca {$l = pos{~i~}$} si {$r = pos{~j~}$} ({$pos{~i~} < pos{~j~}$}) la sfarsitul _query_-ului {$euler{~pozmin~}$} este chiar {$lca(i, j)$}.
