h1. Heavy path decomposition
h1. Tree decompositions
(Categoria _Algoritmi_, autor _Marius Stroe_)
(Categoria _Algoritmi_, Autor _Marius Stroe_)
Acest articol prezinta studiul unei probleme ce urmareste determinarea eficienta a valorii maxime/minime aflata pe lantul elementar dintre doua noduri date dintr-un arbore. Mentionez ca, in acest articol, _lant_ va insemna intotdeauna _lant elementar_ (un nod poate aparea cel mult odata).
(toc){width: 20em}*{text-align:center} *Continut:*
* 'Liniarizare':tree-decompositions#liniarizare
** '{*} Solutie $O((M+N)*log(N))$':tree-decompositions#solutie-liniarizare
* 'Descompunere in lanturi':tree-decompositions#descompunere-in-lanturi
** '{*} Solutie $O(M*N)$':tree-decompositions#solutie-brute
** '{*} Solutie $O(M*sqrt(N)*log(N))$':tree-decompositions#solutie-sqrt-log
** '{*} Solutie $O(M*log^2^(N))$':tree-decompositions#solutie-log-log
* 'Aplicatii':tree-decompositions#aplicatii
* 'Bibliografie':tree-decompositions#bibliografie
h2. Enunt
Acest articol prezinta modalitati de prelucrare a unui arbore pentru calcularea eficienta a unei sume si a valorii maxime / minime aflate pe lantul elementar dintre doua noduri. Mentionez ca, in acest articol, $lant$ va insemna intotdeauna $lant elementar$ (un nod poate aparea cel mult o data).
In continuare voi prezenta enuntul unui tip de problema ce a aparut la multe dintre concursurile de informatica. Motivul pentru care am ales acest lucru este ca unii participanti pot fi tentati sa incerce sa adapteze rezolvarea acesteia la rezolvarea problemei ce necesita _heavy path decomposition_. Lucru ce nu este posibil, pierzand astfel timp pretios. Iata enuntul:
h2(#liniarizare). Liniarizare
Fie $G = (V, E)$ un graf neorientat conex, $|E| = |V| - 1$ (pe scurt, un arbore). Vom considera ca fiecare nod $x ∈ V$ are asociata o valoare $value[x]$ din multimea numerelor reale. Se dau $M$ instructiuni, $M <= 200000$, de doua tipuri:
Un enunt care apare frecvent la concursurile de informatica este urmatorul:
* primul tip cere sa se afiseze suma valorilor tuturor nodurilor ce se afla pe lantul dintre $x, y ∈ V$ (practic, daca $P = (x{~0~},x{~1~}, x{~2~}, ..., x{~n~}), x{~0~} = x si x{~n~} = y$, este lantul ce uneste cele doua noduri, atunci se cere $Δ = ∑ value[u]$, $u ∈ P$)
* al doilea tip modifica valoarea atasata unui nod.
Fie <tex> G = (V, E) </tex> un graf neorientat conex, <tex> |E| = |V| - 1 </tex> (pe scurt, un arbore). Vom considera ca fiecare nod <tex> x \in V </tex> are asociata o valoare <tex> value[x] </tex> din multimea numerelor reale. Se dau $M$ instructiuni, $M ≤ 200000$, de doua tipuri:
h2. Solutia $O((M+N)log(N))$
* instructiunile de primul tip cer sa se afiseze suma valorilor tuturor nodurilor ce se afla pe lantul dintre <tex> x, y \in V </tex> (practic, daca <tex> P = (x_{0}, x_{1}, x_{2}, ..., x_{n}) </tex>, <tex> x_{0} = x </tex>, <tex> x_{n} = y </tex>, este lantul ce uneste cele doua noduri, atunci se cere <tex> \Delta = \displaystyle\sum_{u \in P} value[u] </tex>)
* cele de al doilea tip modifica valoarea atasata unui nod.
Solutia se foloseste de o tehnica numita liniarizarea arborelui. Aceasta presupune o parcurgere in adancime si retinerea unor informatii necesare pentru interogare si actualizare: $seq[]$, $firstPos[]$, $lastPos[]$. Iata pseudocodul acestei parcurgeri:
h3(#solutie-liniarizare). Solutie $O((M+N)*log(N))$
Solutia se foloseste de o tehnica numita liniarizarea arborelui. Aceasta presupune o parcurgere in adancime si retinerea unor informatii necesare pentru interogare si actualizare: <tex> seq[\ ] </tex>, <tex> firstPos[\ ] </tex>, <tex> lastPos[\ ] </tex>. Iata pseudocodul acestei parcurgeri:
== code(c) |
PARCURGE(x)
seq_len ++;
seq[seq_len] = value[x];
firstPos[x] = seq_len;
pentru fiecare fiu y al lui x executa
PARCURGE(y); // apeleaza recursiv pentru y
seq_len++
seq[seq_len] = value[x]
firstPos[x] = seq_len
pentru fiecare fiu nevizitat y al lui x executa
PARCURGE(y) // apeleaza recursiv pentru y
sfarsit pentru
seq_len ++;
seq[seq_len] = -value[x];
lastPos[x] = seq_len;
seq_len++
seq[seq_len] = -value[x]
lastPos[x] = seq_len
==
_Fig. 1: Pentru arborele din figura alatura si vectorul de valori $value[] = {3, 5, 7, 1, 2, 4}$, $seq[]$ construit este ilustrat mai jos. Se observa usor ca tot subarborele unui nod se anuleaza cand este explorat in intregime._
p=. !tree-decompositions?fig1.jpg!
p=. !heavy-path-decomposition?fig1.jpg!
p=. _Fig. 1: Pentru arborele de mai sus si vectorul de valori_ <tex> value[\ ] = \{3, 5, 7, 1, 2, 4\} </tex>, <tex> seq[\ ] </tex> _construit este ilustrat in figura. Se observa usor ca tot subarborele unui nod se anuleaza cand este explorat in intregime._
Astfel, s-a construit vectorul $seq[]$ care are urmatoarea proprietate: "daca $Δ = ∑ seq[i]$, $firstPos[x] <= i <= firstPos[y]$, x fiind un stramos al lui y, atunci Δ reprezinta $∑ value[u]$, $u ∈ P$, $P = (x{~0~}, x{~1~}, x{~2~}, ..., x{~n~}), x{~0~} = x si x{~n~} = y"$. Conform acesteia, daca vom determina cel mai apropiat stramos comun dintre doua noduri, atunci nu va fi nevoie decat de un cost cat mai mic pentru calcularea eficienta a sumei pe un interval si modificarea unei valori din acest vector $seq[]$. Cu ajutorul structurii de date numita arbori de intervale putem obtine costul $O(log(N))$ pe fiecare din cele doua operatii. Pentru determinarea eficienta a celui mai apropiat stramos comun consultati bibliografia.
S-a construit, astfel, vectorul <tex> seq[\ ] </tex> care are urmatoarea proprietate: "daca <tex> \Delta = \displaystyle\sum_{i = firstPos[x]}^{firstPos[y]} seq[i] </tex>, <tex> x </tex> fiind un stramos al lui <tex> y </tex>, atunci <tex> \Delta = \displaystyle\sum_{u \in P} value[u] </tex>, <tex> P = (x_{0}, x_{1}, x_{2}, ..., x_{n}) </tex>, <tex> x_{0} = x </tex>, <tex> x_{n} = y </tex>". Conform acesteia, daca vom determina cel mai apropiat stramos comun pentru doua noduri, atunci nu va fi nevoie decat de o structura de date ce permite calcularea intr-un mod eficient a sumei pe un interval din <tex> seq[\ ] </tex> si modificarea unei valori din acest vector. Putem obtine complexitatea $O(log(N))$ pe fiecare din cele doua operatii folosind structura de date numita $arbori de intervale$. Pentru determinarea eficienta a celui mai apropiat stramos comun si pentru detalii despre arborii de intervale consultati 'bibliografia':tree-decompositions#bibliografie.
h2. Enunt
h2(#descompunere-in-lanturi). Descompunere in lanturi
Acum ne vom concentra asupra sarcinii initiale, de determinare a valorii de maxim/minim. Enuntul este urmatorul:
Acum ne vom concentra asupra urmatoarei sarcini, de determinare a valorii maxime / minime. Sa urmarim enuntul de mai jos.
Fie $G = (V, E)$ un graf neorientat conex, $|E| = |V| - 1$. Vom considera, bineinteles, ca fiecare nod $x ∈ V$ are asociata o valoare $value[x]$ din multimea numerelor reale. Se dau $M$ instructiuni, $M <= 200000$, de doua tipuri:
Fie <tex> G = (V, E) </tex> un graf neorientat conex, <tex> |E| = |V| - 1 </tex> (tot un arbore). Vom considera, bineinteles, ca fiecare nod <tex> x \in V </tex> are asociata o valoare <tex> value[x] </tex> din multimea numerelor reale. Se dau $M$ instructiuni, $M ≤ 200000$, de doua tipuri:
* primul tip cere sa se scrie maximul dintre valorile nodurilor ce se afla pe lantul dintre $x, y ∈ V$ (daca $P = (x{~0~},x{~1~}, x{~2~}, ..., x{~n~}), x{~0~} = x si x{~n~} = y$, atunci se cere $Δ = Maxim {value[u] | u ∈ P}$)
* primul tip de instructiuni cere sa se scrie maximul dintre valorile nodurilor ce se afla pe lantul dintre <tex> x, y \in V </tex> (daca <tex> P = (x_{0}, x_{1}, x_{2}, ..., x_{n}) </tex>, <tex> x_{0} = x </tex>, <tex> x_{n} = y </tex>, atunci se cere <tex> \Delta = \max \{value[u]\ /\ u \in P \} </tex>)
* al doilea tip modifica valoarea asociata unui nod.
h2. Solutia $O(M*N)$
h3(#solutie-brute). Solutie $O(M*N)$
Sunt o multitudine de solutii simple ce ne pot trece prin minte. Pentru cea aleasa de mine voi retine un vector $parent[]$ semnificand parintele unui nod calculat printr-un depth-search, si $depth[]$ ce retine adancimea, adica numarul de muchii de la radacina pana la nodul interogat. Cu ajutorul lor, urmatorul pseudocod rezolva primul tip de cerinta:
Sunt o multitudine de solutii simple ce ne pot trece prin minte. Pentru cea aleasa de mine voi retine un vector <tex> parent[\ ] </tex>, semnificand parintele unui nod calculat printr-o parcurgere in adancime, si un vector <tex> depth[\ ] </tex> ce retine adancimea, adica numarul de muchii de la radacina pana la nodul interogat. Cu ajutorul lor, prima cerinta se rezolva in $O(N)$ astfel: pornesc din cele doua noduri si merg "in sus" pe arbore, in paralel (raportat la <tex> depth[\ ] </tex>), pana cand ajung in cel mai apropiat stramos comun, retinand pe parcurs valoarea maxima ceruta. Rezolvarea cerintei a doua se face simplu in $O(1)$, modificand direct <tex> value[\ ] </tex>.
== code(c) |
QUERY(x, y)
ret = Maxim(value[x], value[y]);
cat timp x diferit de y executa
daca depth[x] > depth[y] atunci
x = parent[x];
ret = Maxim(ret, value[x]);
altfel
y = parent[y];
ret = Maxim(ret, value[y]);
sfarsit daca
sfarsit cat timp
returneaza ret;
==
Rezolvarea cerintei a doua se face simplu in $O(1)$.
h2. Solutia $O(M*log^2^(N))$
h3(#solutie-sqrt-log). Solutie $O(M*sqrt(N)*log(N))$
Voi prezenta intr-un mod indirect cum se ajunge la aceasta complexitate, intrucat exista o solutie relativ asemanatoare celei pe care mi-am propus sa o prezint, insa nu la fel de rapida, numita _longest path decomposition_. Si, desigur, nu este rau daca stim ceva in plus. :)
Tehnica liniarizarii arborelui nu ne este de folos in acest caz, deoarece modul de reprezentare a informatiilor nu permite obtinerea unei complexitati mai bune fata de 'solutia lenta':tree-decompositions#solutie-brute prezentata mai sus.
Tehnica liniarizarii arborelui este inapta functionarii, deoarece informatiile pe care le putem retine nu permit obtinerea unei complexitati mai bune.
O solutie mai buna foloseste asa numita tehnica $longest path decomposition$, tehnica ce necesita cunostinte minime despre grafuri si cu care vom obtine complexitatea $O(M*sqrt(N)*log(N))$ urmand pasii de mai jos:
Insa, cu _longest path_decomposition_, tehnica ce necesita cunostine minime despre grafuri, vom obtine complexitatea $O(M*sqrt(N)*log(N))$ urmand pasii de mai jos:
# Elimina cel mai lung lant radacina-frunza din arbore si apeleaza recursiv pentru restul componentelor conexe ;
# Retine fiecare lant ca un vector $Path[].array[]$ cu noduri ordonate crescator dupa adancime si pastreaza un pointer catre nodul din lantul sau parinte $Path[].parent$;
# Pentru fiecare nod retine lantul caruia apartine $whatPath[]$ si pozitia in vectorul lantului $whatPos[]$.
# Se elimina cel mai lung lant radacina-frunza din arbore si se apeleaza recursiv pentru restul componentelor conexe;
# Se retine fiecare lant ca un vector <tex> Path[\ ].array[\ ] </tex> cu noduri ordonate crescator dupa adancime si se pastreaza un pointer catre nodul din lantul sau parinte <tex> Path[\ ].parent </tex>;
# Pentru fiecare nod se retine lantul caruia apartine <tex> whatPath[\ ] </tex> si pozitia in vectorul lantului <tex> whatPos[\ ] </tex>.
Este evident ca memoria ocupata este $O(N)$, fiecare nod fiind inclus intr-un singur lant. Numarul maxim de lanturi prin care putem trece pornind din radacina pana intr-una din frunze, este $O(sqrt(N))$.
_Fig. 2: Cazul defavorabil cand sunt $O(sqrt(N))$ lanturi elementare._
p=. !tree-decompositions?Figura2.jpg!
!heavy-path-decomposition?Figura2.jpg!
p=. _Fig. 2: Cazul defavorabil cand sunt $O(sqrt(N))$ lanturi elementare._
Fie {$x, y ∈ V, x stramos al lui y$}. Functia care determina valoarea maxima pe lantul dintre $x$ si $y$ este prezentata in urmatorul pseudocod:
Fie <tex> x, y \in V </tex>, <tex> x </tex> stramos al lui <tex> y </tex>. Functia care determina valoarea maxima pe lantul dintre <tex> x </tex> si <tex> y </tex> este prezentata in urmatorul pseudocod:
== code(c) |
QUERY(x, y)
ret = value[x];
ret = value[x]
cat timp x diferit de y executa
daca whatPath[x] = whatPath[y] atunci
ret = Maxim(ret, QUERYAi(Path[ whatPath[y] ], whatPos[x], whatPos[y]));
y = x;
ret = Maxim(ret, QUERYAi(Path[whatPath[y]], whatPos[x], whatPos[y]))
y = x
altfel
ret = Maxim(ret, QUERYAi(Path[ whatPath[y] ], 1, whatPos[y]));
y = Path[ whatPath[y] ].parent;
ret = Maxim(ret, QUERYAi(Path[whatPath[y]], 1, whatPos[y]))
y = Path[whatPath[y]].parent
sfarsit daca
sfarsit cat timp
returneaza ret;
returneaza ret
==
Functia $QUERYAi(Path[], lo, hi)$ returneaza in $O(log(N))$, cu ajutorul structurii de date arbori de intervale, maximul dintre valorile cuprinse in intervalul $[lo, hi]$.
Raspunsul cerintei de primul tip va fi {$Maxim(QUERY (lca, x), QUERY (lca, y))$}, variabila $lca$ fiind cel mai apropiat stramos comun al lui $x$ si $y$.
Pentru rezolvarea cerintei de tipul doi, vom folosi aceeasi arbori de intervale care vor obtine un cost de $O(log(N))$ per operatie. Nu voi prezenta aceasta functie aici, ea fiind in detaliu prezentata in una din sursele afisate in Bibliografie.
Complexitatea finala: $O(M*sqrt(N)*log(N))$.
Functia $QUERYAi(Path[], lo, hi)$ returneaza in $O(log(N))$, cu ajutorul structurii de date $arbori de intervale$, maximul dintre valorile cuprinse in intervalul $[lo, hi]$. Raspunsul cerintei de primul tip va fi {$Maxim(QUERY (lca, x), QUERY (lca, y))$}, variabila <tex> lca </tex> fiind cel mai apropiat stramos comun al lui <tex> x </tex> si <tex> y </tex>. Pentru rezolvarea cerintei de tipul doi, vom folosi aceiasi arbori de intervale care vor avea un cost de $O(log(N))$ pe operatie. Nu voi prezenta aceasta functie, ea fiind in detaliu prezentata in una din sursele afisate in 'bibliografie':tree-decompositions#bibliografie.
Complexitatea finala: $O(M*sqrt(N)*log(N))$. Cel mai rau caz pentru un query este cand se trece prin toate lanturile (in numar de $sqrt(N)$) efectuandu-se cate un query pe fiecare arbore de intervale asociat ({$O(log(N))$}).
h3(#solutie-log-log). Solutie $O(M*log^2^(N))$
O imbunatatire pentru aceasta metoda o reprezinta $heavy path decomposition$, care se foloseste de acelasi algoritm, cu exceptia faptului ca fiul ales pentru determinarea unui lant este cel cu numar maxim de noduri in subarborele sau (heavy) si nu cel cu inaltimea maxima (longest). Prin urmare, numarul maxim de lanturi prin care se trece pentru a ajunge de la un nod la radacina este cel mult $O(log(N))$ dupa cum se poate vedea si in figura urmatoare:
O imbunatatire la solutia 'precedenta':tree-decompositions#solutie-sqrt-log o reprezinta $heavy path decomposition$, care se foloseste de acelasi algoritm, cu exceptia faptului ca fiul ales pentru determinarea unui lant este cel cu numar maxim de noduri in subarborele sau ({$heavy$}), si nu cel cu inaltimea maxima ({$longest$}). Prin urmare, numarul maxim de lanturi prin care se trece pentru a ajunge de la un nod la radacina este cel mult $O(log(N))$ dupa cum se poate vedea si din figura urmatoare:
_Fig. 3: Fiecare nod apartine unui singur lant. Lanturile sunt reprezentate de muchii solide._
p=. !tree-decompositions?Figura3.jpg!
!heavy-path-decomposition?Figura3.jpg!
p=. _Fig. 3: Fiecare nod apartine unui singur lant. Lanturile sunt reprezentate de muchii solide._
Complexitatea finala: $O(M log^2(N))$. In practica, aceasta tehnica se comporta foarte bine si poate fi folosita cu succes. Singurul dezavantaj este ca trebuie scrise multe linii de cod. Voi incerca sa obtin o solutie cat mai scurta cu _heavy path decomposition_ si o voi atasa acestei pagini pentru cei curiosi. :)
Complexitatea finala: $O(M*log^2^(N))$. In practica, aceasta tehnica se comporta foarte bine si poate fi folosita cu succes. Singurul inconvenient este numarul mare de linii de cod scrise.
h2. Aplicatii
h2(#aplicatii). Aplicatii
* "Query on a tree":http://www.spoj.pl/problems/QTREE/ - spoj, 375
* "Caves and tunnels":http://acm.timus.ru/problem.aspx?space=1&num=1553 - timus, Novosibirsk SU Contest, Petrozavodsk training camp, September 2007
* "Delay":problema/delay - pregatirea lotului national de informatica, 2002.
* "Omizi":problema/omizi - .campion 2005
* "Arbfind":problema/arbfind - pregatirea lotului national de informatica, 2006.
* "CT":problema/ct - Happy Coding 2006
* "Query on a tree":http://www.spoj.pl/problems/QTREE/
* "Caves and tunnels":http://acm.timus.ru/problem.aspx?space=1&num=1553 - Petrozavodsk training camp, 2007
* "Delay":problema/delay - Lotul National de Informatica, 2002
* "Omizi":problema/omizi - .campion, 2005
* "Arbfind":problema/arbfind - Lotul National de Informatica, 2006
* "CT":problema/ct - Happy Coding, 2006
h2. Bibliografie
h2(#bibliografie). Bibliografie
* "Introducere in algoritmi", autori Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest
* "Arbori de intervale si aplicatii in geometrie":arbori-de-intervale, autor Dana Lica
* "Range Minimum Query and Lowest Common Ancestor":http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor, autor Daniel Pasaila
* "LCA: Lowest Common Ancestor":LCA-Lowest-common-ancestor, autor Emilian Miron
* Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest - _"Introducere in Algoritmi"_
* Dana Lica - "_Arbori de intervale si aplicatii in geometria computationala_":arbori-de-intervale
* Daniel Pasaila - "_Range Minimum Query and Lowest Common Ancestor_":http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
* Emilian Miron - "_Lowest Common Ancestor_":lowest-common-ancestor
* Michael A. Bender, Martin Farach-Colton - "_The level ancestor problem simplified_":http://cs.sunysb.edu/~bender/pub/latin02-level.ps
* Oren Weimann - "_Advanced data structures_":http://courses.csail.mit.edu/6.851/spring07/scribe/lec09.pdf
