Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-12-10 09:42:14.
Revizia anterioară   Revizia următoare  

Tree decompositions

(Categoria Algoritmi, autor Marius Stroe)

Acest articol prezinta studiul transformarii unui arbore pentru calcularea eficienta a unei insumari si a valorii maxime/minime aflata pe lantul elementar dintre doua noduri. Mentionez ca, in acest articol, lant va insemna intotdeauna lant elementar (un nod poate aparea cel mult odata).

Liniarizare

Un enunt care apare frecvent la concursurile de informatica este urmatorul:

Fie  G = (V, E) un graf neorientat conex,  |E| = |V| - 1 (pe scurt, un arbore). Vom considera ca fiecare nod  x \in V are asociata o valoare  value[x] din multimea numerelor reale. Se dau M instructiuni, M <= 200000, de doua tipuri:

  • primul tip cere sa se afiseze suma valorilor tuturor nodurilor ce se afla pe lantul dintre  x, y \in V (practic, daca  P = (x_{0}, x_{1}, x_{2}, ..., x_{n}), x_{0} = x, x_{n} = y , este lantul ce uneste cele doua noduri, atunci se cere  \Delta = \displaystyle\sum_{u \in P} value[u]
  • al doilea tip modifica valoarea atasata unui nod.

Solutia 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:  seq[] ,  firstPos[] ,  lastPos[] . Iata pseudocodul acestei parcurgeri:

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
    sfarsit pentru
    seq_len ++;
    seq[seq_len] = -value[x];
    lastPos[x] = seq_len;

Fig. 1: Pentru arborele din figura de mai jos 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.

Astfel, s-a construit vectorul  seq[] care are urmatoarea proprietate: "daca  \Delta = \displaystyle\sum_{i = firstPos[x]}^{firstPos[y]} seq[i] ,  x fiind un stramos al lui  y , atunci  \Delta reprezinta  \Delta = \displaystyle\sum_{u \in P} value[u] ,  P = (x_{0}, x_{1}, x_{2}, ..., x_{n}), x_{0} = x, x_{n} = y ". Conform acesteia, daca vom determina cel mai apropiat stramos comun dintre 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  seq[] 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.

Descompunere in lanturi

Acum ne vom concentra asupra urmatoarei sarcini, de determinare a valorii de maxim/minim. Sa urmarim enuntul de mai jos.

Fie G = (V, E) un graf neorientat conex, |E| = |V| - 1 (yup, tot arbore). 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:

  • primul tip cere sa se scrie maximul dintre valorile nodurilor ce se afla pe lantul dintre x, y ∈ V (daca P = (x0,x1, x2, ..., xn), x0 = x si xn = y, atunci se cere Δ = Maxim {value[u] | u ∈ P})
  • al doilea tip modifica valoarea asociata unui nod.

Solutia 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 un vector depth[] 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 voi ajunge in cel mai apropiat stramos comun, retinand pe parcurs valoarea maxima ceruta. Rezolvarea cerintei a doua se face simplu in O(1) modificand direct value[].

Solutia O(M*log(N)*sqrt(N))

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 prezentata mai sus.

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:

  1. Elimina cel mai lung lant radacina-frunza din arbore si apeleaza recursiv pentru restul componentelor conexe;
  2. 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;
  3. Pentru fiecare nod retine lantul caruia apartine whatPath[] si pozitia in vectorul lantului whatPos[].

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.

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:

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 lca fiind cel mai apropiat stramos comun al lui x si y.
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.

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))).

Solutia O(M*log2(N))

O imbunatatire la solutia precedenta 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.

Complexitatea finala: O(M log2(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.

Aplicatii

  • Query on a tree - spoj, 375
  • Caves and tunnels - timus, Novosibirsk SU Contest, Petrozavodsk training camp, September 2007
  • Delay - pregatirea lotului national de informatica, 2002.
  • Omizi - .campion 2005
  • Arbfind - pregatirea lotului national de informatica, 2006.
  • CT - Happy Coding 2006

Bibliografie