Note de curs, clasele 11-12, 13 martie 2014
Discutarea temei
Pentru problema prepost există două soluții, una recursivă (cu o parcurgere) și una nerecursivă (cu o stivă). Parcurgerea recursivă necesită atenție sporită, căci riscă să depășească stiva.
Range Minimum Query (RMQ) și Lowest Common Ancestor (LCA)
Definiții
- Range Minimum Query: se dă un vector V cu n elemente. Să se preproceseze vectorul pentru a răspunde eficient la interogări de forma: pentru 1 ≤ i ≤ j ≤ n, care este indicele elementului minim din subvectorul V[i...j]?
- Lowest Common Ancestor: se dă un arbore T cu n noduri. Să se preproceseze arborele pentru a răspunde eficient la interogări de forma: pentru două noduri u și v, care este nodul cel mai depărtat de rădăcină care este strămoș atât al lui u, cât și al lui v?
Aceste două probleme sunt aparent diferite, dar în realitate înrudite: nu doar că se reduc una la cealaltă în timp liniar, dar unele soluții pentru RMQ se bazează pe LCA și invers. De aceea, ele sunt de obicei tratate împreună.
Problemele se încadrează în clasa mai generală a problemelor de preprocesare + interogare (query). Observăm că pentru acest gen de probleme calitatea soluției nu se mai poate măsura printr-un singur termen (complexitatea asimptotică), ci prin doi termeni: complexitatea preprocesării și, separat, a interogărilor. Notăm aceasta prin expresia < f(n), g(n) >, unde f(n) este complexitatea preprocesării, iar g(n) cea a interogării.
Ocazional vom folosi un triplet de funcții < f(n), g(n), mem(n) >, unde mem(n) este memoria folosită. Și acesta este un considerent important.
O clasificare importantă a problemelor de preprocesare + interogare este:
- probleme offline: toate interogările sunt date în avans. Atunci putem preprocesa structura știind exact la ce trebuie să răspundem.
- probleme online: fiecare interogare ne este prezentată doar după ce am răspuns la interogarea anterioară.
Aplicații
- analiza ADN a două specii pentru a afla strămoșul comun din care au evoluat
- click pe două noduri într-o pagină HTML, highlight pe strămoșul comun
- algoritmi de merge în sisteme de control al versiunilor (cred că Bazaar).
Desigur, algoritmii prezentați mai jos devin cu adevărat utili doar atunci când numărul de interogări este mare.
Algoritmi naivi
Pentru RMQ, algoritmul naiv nu face niciun fel de preprocesare. Pentru interogarea (i, j), el parcurge pur și simplu subvectorul V[i...j] în timp O(j - i) = O(n). Așadar, complexitatea este < O(1), O(n) >.
La polul opus se află precalcularea completă, care află răspunsul la toate cele O(n2) interogări posibile. Acest algoritm calculează o matrice Min prin metoda programării dinamice (cum?). Complexitatea sa este < O(n2), O(1), O(n2) >. Memoria necesară îl face nepractic.
Similar, pentru LCA există un algoritm cu zero preprocesare în < O(1), O(n) > și unul cu preprocesare completă în < O(n2), O(1), O(n2) >.
Algoritmul offline pentru LCA (Tarjan)
Algoritmul lui Tarjan se bazează pe structuri de mulțimi disjuncte. Când toate interogările sunt cunoscute, algoritmul creează liste de interogări pentru fiecare nod din arbore (o interogare (u, v) va apărea și în lista lui u și în lista lui v.
Vedeți Wikipedia (sau Cormen) pentru pseudocod.
Cum funcționează, în esență, acest algoritm? Observăm că el răspunde la (unele din) întrebările legate de un nod u imediat după ce termină de vizitat nodul u și îl colorează cu negru. Apoi răspunde la toate interogările (u, v) pentru care și v este negru. Dar, știind că nodul u este negru, unde altundeva în arbore ar putea fi v ca să fie și el negru?
- într-un subarbore al lui u. În acest caz, răspunsul la interogare este u.
- într-un subarbore deja vizitat al tatălui lui u. În acest caz, răspunsul la interogare este tatăl lui u.
- într-un subarbore deja vizitat al bunicului lui u. În acest caz, răspunsul la interogare este bunicul lui u.
- etc.
Complexitatea algoritmului, pentru n noduri și q interogări, este < O(n α(n)), O(α(n)), O(n + q) >. Remarcați însă că preprocesarea și răspunsurile la interogări sunt amestecate. De asemenea, algoritmul folosește memorie suplimentară pentru fiecare interogare.
Algoritmi în < O(n), O() >
Există o metodă cu aplicabilitate largă pentru a reduce timpul de rulare cu un factor de :
- se împarte problema în k subprobleme (buckets) de dimensiune l = n / k.
- se precalculează răspunsul pentru fiecare bucket în timp O(l), respectiv în timp total O(n)
- răspundem la fiecare interogare combinând trei răspunsuri:
- numărul întreg de buckets cuprinse în interogare: O(k)
- analizăm prin forță brută începutul și sfârșitul interogării, care se suprapun doar parțial cu un bucket: O(l)
- complexitatea interogărilor este O(k + n / k), iar minimul este când
Pentru RMQ, împărțim așadar vectorul în bucăți a câte elemente fiecare și calculăm naiv minimul fiecărei bucăți.
Pentru LCA, reducerea la este mai puțin evidentă. Trebuie stratificat arborele pe verticală în felii de câte muchii. Fiecare nod va reține un pointer către strămoșul lui de la limita de sus a feliei. De asemenea, trebuie să calculăm nivelul fiecărui nod. Apoi, pentru două noduri u și v, găsim întâi stratul în care cele două noduri se unifică, apoi iterăm naiv pe verticală prin strat.
Algoritmul pentru RMQ în <O(n log n), O(1), O(n log n) >
Pentru RMQ, precalculăm un tabel A[n][log n] unde A[i][j] este minimul subvectorului V[i...i + 2j-1]. Acesta necesită, evident, O(n log n) memorie și poate fi calculat în O(1) per celulă (cum?).
Odată precalculat acest tabel, putem răspunde la orice interogare (i, j) în O(1). Trebuie să găsim două segmente de lungime 2k care, suprapuse, să acopere tot intervalul (i, j). Desigur, vom lua . Primul segment începe la poziția i, iar al doilea se termină la poziția j. Faptul că cele două segmente nu sunt disjuncte nu schimbă rezultatul operației min.
Atenție, avem nevoie să putem calcula logaritmul binar în O(1). Vedeți o scurtă explicație de la clasele 9-10 despre acest gen de operații pe biți.
Acest algoritm se numește algoritmul matricei rare, sau sparse table, sau pe scurt ST.
Algoritmul pentru LCA în <O(n log n), O(log n), O(n log n) >
Pentru LCA, soluția similară stochează un tabel A[n][log n] unde A[i][j] este părintele lui i la 2j noduri înălțime. Putem construi acest tabel în O(1) per celulă folosind recurența:
Această soluție este limitată la O(log n) per interogare.
Reducerea de la LCA la RMQ și invers
Generalități despre reducerea problemelor
Reducerea problemei A la problema B presupune 3 pași:
- formularea problemei A ca o instanță a problemei B
- rezolvarea problemei B
- convertirea soluției la problema B înapoi la o soluție pentru problema A
Toți acești pași trebuie analizați pentru aflarea complexității finale a unei soluții la problema A bazată pe reducerea la problema B
Reducerea LCA la RMQ
- parcurgere Euler
- exemplu
- observăm că reducem nu doar la RMQ, ci la problema RMQ restricționată, unde două numere consecutive diferă prin exact ±1.
- pentru a reconstitui soluția, ne trebuie nu doar parcurgerea Euler propriu-zisă, ci și un vector paralel cu înălțimile nodurilor vizitate.
- tehnic vorbind, o problemă LCA de mărime n se reduce la o problemă RMQ de mărime 2*n.
Reducerea de la RMQ la LCA
- arbore cartezian
Ce învățăm de aici? Că RMQ se reduce la RMQ restricționată folosind LCA. Nu este o reducere frumoasă, căci la fiecare pas apar structuri noi de date, iar constanta crește, dar reducerile RMQ - LCA - RMQ restricționat se pot face în O(n), iar convertirea soluțiilor în O(1).
O soluție în < O(n), O(1), O(n) > pentru RMQ restricționat
Problema RMQ restricționată este problema RMQ în care două elemente consecutive din vector diferă prin exact ±1. Vă reamintesc că reducerea LCA → RMQ conduce, de fapt, la problema RMQ restricționat.
- Împărțim vectorul în k intervale (buckets) de lungime l = n / k.
- Precalculăm minimul fiecărui bucket în O(n).
- Punem aceste minime într-un vector W.
- Precalculăm RMQ pe W folosind o matrice rară (vezi secțiunea 2.6), în complexitate și cu memorie O(k log k).
Avem nevoie să calculăm și răspunsuri în interiorul fiecărui bucket.
- Observăm că putem descrie un bucket prin primul element și o secvență de l cifre binare (±1).
- Deducem că există cel mult 2l tipuri de bucket.
- Le precalculăm pe toate cu programare dinamică în timp și memorie O(2l * l2).
- Stocăm, pentru fiecare bucket, tipul său, pentru a-l putea folosi la interogare.
Apoi putem răspunde la fiecare interogare prin trei operații, toate în O(1):
- minimul din intervalele complet acoperite de interogare, folosind matricea rară precalculată;
- minimul din porțiunile de interval de la început și de la sfârșit, cunoscând tipurile de interval.
Mai există și cazul particular când o interogare este cuprinsă complet într-un interval.
Complexitatea totală a este < O(n + 2l * l2), O(1), O(n + 2l * l2 + k log k).
Alegem pentru a obține complexitatea < O(n), O(1), O(n) >.
Repet că această soluție este complicată și, aproape sigur, inutilă în condiții de concurs. Pentru a răspunde la RMQ, trebuie implementați corect pașii:
- reducerea RMQ → LCA;
- reducerea LCA → RMQ restricționat;
- implementarea RMQ restricționat;
- reconstituirea soluției pentru LCA din soluția la RMQ restricționat;
- reconstituirea soluției pentru RMQ din soluția la LCA.
În afară de cazul în care nu aveți memorie O(n log n), intuiesc că algoritmul cu matrice rară merge la fel de bine în practică, deoarece are constantă mult mai mică.
Resurse
Există pagini din abundență care discută LCA și RMQ. Vă recomand:
- articolul de la TopCoder -- foarte schematic
- problema LCA de la infoarena -- face o comparație în termeni de punctaje între diversele soluții
- The LCA Problem Revisited, Bender & Farach-Colton, 2000