Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-01-10 18:36:33.
Revizia anterioară   Revizia următoare  

Heavy path decomposition

(Categoria Algoritmi, autor Marius Stroe)

Acest articol prezinta un studiu al unei probleme ce urmareste determinarea eficienta a unei valori de extrem aflata pe lantul elementar dintre doua noduri date dintr-un arbore. Mentionez ca lant va insemna intotdeauna lant elementar in acest articol.

Enunt

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:

Fie G = (V, E) un graf neorientat conex, |E| = |V| - 1. 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 : primul tip cere sa se afiseze suma valorilor tuturor nodurilor ce se afla pe lantul dintre x, y ∈ V (practic, daca P = (x0,x1, x2, ..., xn), x0 = x si xn = y, este lantul ce uneste cele doua noduri, atunci se cere Δ = ∑ value[u], u ∈ P), iar 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
        apeleaza recursiv pentru y;
    sfarsit pentru
    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.

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 = (x0, x1, x2, ..., xn), x0 = x si xn = 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.

Enunt

Acum ne vom concentra asupra sarcinii initiale, de determinare a valorii de maxim/minim. Enuntul este urmatorul:

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 : 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}), iar 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 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:

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

Solutia O(M*log2(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 poate functiona, deoarece informatiile ce le putem retine nu ne pot permite sa obtinem o complexitate mai buna.

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:

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