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}), x_{0} = x, x_{n} = y </tex>, atunci se cere <tex> \Delta = Maxim\{value[u]\ /\ u \in P \} </tex>)
* 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}), x_{0} = x, x_{n} = y </tex>, atunci se cere <tex> \Delta = \displaystyle\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>.
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: merg "in sus" in arbore 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-log-sqrt). Solutie $O(M*log(N)*sqrt(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.
Tehnica liniarizarii arborelui nu ne este de folos, deoarece modul de reprezentare a informatiilor nu permite obtinerea unei complexitati mai bune fata de 'solutia lenta':tree-decompositions##solutie-descompunere-brute prezentata mai sus.
O solutie mai buna foloseste asa numita tehnica $longest path decomposition$, tehnica ce necesita cunostine minime despre grafuri si cu care vom obtine complexitatea $O(M*sqrt(N)*log(N))$ urmand pasii de mai jos:
Aceasta solutie foloseste asa numita tehnica $longest path decomposition$, tehnica ce necesita cunostine 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>.
# Elimina cel mai lung lant radacina-frunza din arbore si apeleaza recursiv pentru restul componentelor conexe;
# Retine fiecare lant ca un vector <tex> Path[\ ].array[\ ] </tex> cu noduri ordonate crescator dupa adancime si pastreaza un pointer catre nodul din lantul sau parinte <tex> Path[\ ].parent </tex>;
# Pentru fiecare nod 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!
_Fig. 2: Cazul defavorabil cand sunt $O(sqrt(N))$ lanturi elementare._
p=. _Fig. 2: Cazul defavorabil cand sunt $O(sqrt(N))$ lanturi elementare._
!tree-decompositions?Figura2.jpg!
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 <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.
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 obtine 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-log-sqrt 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:
O imbunatatire la solutia 'precedenta':tree-decompositions#solutie-log-sqrt 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!
_Fig. 3: Fiecare nod apartine unui singur lant. Lanturile sunt reprezentate de muchii solide._
p=. _Fig. 3: Fiecare nod apartine unui singur lant. Lanturile sunt reprezentate de muchii solide._
!tree-decompositions?Figura3.jpg!
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.
