<h1>Heavy path decomposition</h1>
h1. Tree decompositions
(Categoria _Algoritmi_, Autor _Marius Stroe_)
(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
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).
h2(#liniarizare). Liniarizare
Un enunt care apare frecvent la concursurile de informatica este urmatorul:
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:
* 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.
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 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
==
p=. !tree-decompositions?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._
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(#descompunere-in-lanturi). Descompunere in lanturi
Acum ne vom concentra asupra urmatoarei sarcini, de determinare a valorii maxime / minime. Sa urmarim enuntul de mai jos.
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 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.
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 <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>.
h3(#solutie-sqrt-log). Solutie $O(M*sqrt(N)*log(N))$
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.
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:
# 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))$.
p=. !tree-decompositions?Figura2.jpg!
p=. _Fig. 2: Cazul defavorabil cand sunt $O(sqrt(N))$ lanturi elementare._
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]
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
altfel
ret = Maxim(ret, QUERYAi(Path[whatPath[y]], 1, whatPos[y]))
y = Path[whatPath[y]].parent
sfarsit daca
sfarsit cat timp
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 <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 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:
p=. !tree-decompositions?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 inconvenient este numarul mare de linii de cod scrise.
h2(#aplicatii). Aplicatii
* "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). Bibliografie
* 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
