Úroveň problému předků - Level ancestor problem

v teorie grafů a teoretická informatika, problém předků na úrovni je problém předzpracování daná zakořeněný strom T do datová struktura které mohou určit předka daného uzlu v dané vzdálenosti od kořene stromu.

Přesněji řečeno T být zakořeněný strom s n uzly, a nechat proti být libovolným uzlem T. Dotaz na předka úrovně LA (proti,d) požaduje předka uzluproti v hloubce d, kde je hloubka uzlu proti ve stromu je počet hran na nejkratší cesta od kořene stromu k uzluprotiJe možné tento problém vyřešit v konstantním čase na dotaz po algoritmu předzpracování, který trvá O (n) a která vytváří datovou strukturu, která používá O (n) úložný prostor.[1][2]

Naivní metody

Předchůdce úrovně (proti, 2) a cesta z root r do uzluproti.

Nejjednodušší způsob, jak najít předka úrovně uzlu, je vylézt na strom směrem ke kořeni stromu. Na cestě ke kořenu stromu lze navštívit každého předka uzlu, a proto jej nahlásit. V tomto případě nemusí být strom předzpracován a čas na zodpovězení dotazu je O (h), kde „h“ je výška stromu. Tento přístup není proveditelný v situacích, kdy strom může mít velkou výšku a je potřeba zpracovat velký počet dotazů.

Alternativně mohou být všechna možná řešení předpočítaný a uloženy v tabulce. V tomto případě lze na dotazy odpovědět v O (1), ale prostor a doba předzpracování je O (n2).

Nejjednodušší dotazy, na které lze odpovídat v konstantním čase bez předzpracování, jsou LA (proti, 0) a LA (proti, hloubka (proti)). V prvním případě je odpovědí vždy kořen stromu a v druhém případě je odpovědí uzel proti sám. Každý z těchto výsledků trvá O (1).

Ukládání cest skrz strom do zkoseného binárního seznamu náhodných přístupů umožňuje, aby byl strom stále rozšiřován směrem dolů o jeden O (1) krok po druhém, ale nyní umožňuje hledání pokračovat v O (log (str)), kde „p“ je vzdálenost od proti do požadované hloubky. Tento přístup je proveditelný, když je strom zvlášť široký nebo bude rozšířen online, a proto jej nelze účinně předzpracovat, protože doba úložiště a přístupu je čistě určena délkou cesty.[3]

Algoritmus skokového ukazatele

Algoritmus skokového ukazatele[1] předběžně zpracuje strom v O (n logn) čas a odpovědi na úrovni předků v O (logn) čas. Algoritmus skokového ukazatele se přidruží k přihlášenín ukazatele na každý vrchol stromu. Tyto ukazatele se nazývají skokové ukazatele, protože vyskočí nahoru ke stromu směrem ke kořeni stromu. Pro daný uzel proti stromu, algoritmus ukládá pole délky propojky kde . The ith prvek tohoto pole ukazuje na 2ith předchůdceproti. Použití takové datové struktury nám pomáhá vyskočit z jakéhokoli daného uzlu do poloviny stromu. Když je algoritmus vyzván ke zpracování dotazu, opakovaně vyskočíme na strom pomocí těchto ukazatelů. Počet skoků bude maximálně logn a proto lze na dotazy odpovídat v protokolun čas.

Žebříkový algoritmus

Algoritmus žebříku [1] je založen na myšlence zjednodušení stromu do sbírky cesty. Důvodem je skutečnost, že cesty se snadněji dotazují, pokud jde o dotazy předků na úrovni. Uvažujme cestu P skládající se z n uzlů zakořeněných v uzlu r. Cestu můžeme uložit do pole velikosti n zvaného Ladder a můžeme rychle odpovědět na dotaz předka úrovně LA (v, d) vrácením Ladder [d] if depth (v) ≤d. To bude trvat O (1). To však bude fungovat, pouze pokud je daný strom cesta. Jinak to musíme rozložit na cesty. To se děje ve dvou fázích: rozklad dlouhé cesty a prodloužení dlouhých cest do žebříků.

Fáze 1: rozklad na dlouhé cestě

Tohle je rekurzivní metoda, která rozloží daný strom na cesty. Tato fáze začíná nalezením nejdelší cesty od kořene k listu ve stromu. Poté tuto cestu odebere rozbitím vazeb ze stromu, což rozbije zbývající část stromu podrostliny a poté rekurzivně zpracuje každý podstrom. Pokaždé, když je cesta rozložena, an pole je vytvořen ve spojení s cestou, která obsahuje prvky na cestě od kořene k listu. Základní případ této rekurze je, když je strom cestou, v takovém případě jeho odstranění ponechá prázdný graf. Každý vrchol v má jedinečný žebřík, kterým je žebřík, který jej obsahuje, a my mu říkáme „v's ladder“. Po této fázi předběžného zpracování však na dotazy nelze rychle odpovědět. Ve skutečnosti, aby bylo možné odpovědět na dotaz předka úrovně, musí algoritmus přeskočit z cesty na jinou, dokud nedosáhne kořene a může existovat Θ (√n) takových cest na cestě typu list-kořen. To nás vede k algoritmu, který dokáže předem zpracovat strom v O (n) dotazy na čas a odpovědi v O (√n). Abychom dosáhli optimální doby dotazu, musíme výsledky zpracovat ve druhé fázi popsané níže.

Fáze 2: prodloužení dlouhých cest do žebříků

První fáze algoritmu rozkládá strom na řadu disjunktních cest. Ve druhé fázi algoritmu je každá cesta prodloužena, a proto se výsledné cesty nebudou vzájemně vylučovat. V první fázi algoritmu je každá cesta spojena s polem velikosti h ' . Tuto cestu rozšiřujeme přidáním h ' bezprostřední předkové v horní části cesty ve stejném poli. Tím se každé pole rozšíří maximálně o dvojnásobek původní velikosti, což povede k 2n celkový počet uzlů ve všech žebřících. Všimněte si, že počet žebříků se nezmění a žebřík každého uzlu zůstane stejný. Ačkoli uzel v může být nyní uveden ve více cestách, ale jeho žebřík je ten, který byl přidružen k v v první fázi algoritmu. Tyto dvě fáze mohou být procesy v O (n), ale čas dotazu ještě není konstantní. Zvažte dotaz předka úrovně na uzlu u výšky h. Cestou na vrchol žebříčku u, minimálně vrchol výšky 2h bude dosaženo. Všimněte si, že všechny uzly mají výšku alespoň 1, a proto poté, co to uděláme i krát, dosáhneme uzlu výšky alespoň 2i a proto to musíme udělat maximálně logn krát. To nám dává čas dotazu O (log n).

Fáze 3: kombinace těchto dvou přístupů

Ukázalo se, že žebříkový algoritmus tento trik sám nedělá. Ve skutečnosti se algoritmus skokového ukazatele a žebříkový algoritmus navzájem doplňují. Tyto dva algoritmy fungují v opačných směrech: Algoritmus skokového ukazatele umožňuje exponenciálně klesající chmel a žebříkový algoritmus exponenciálně zvyšuje chmel. Kombinace těchto dvou algoritmů může odpovídat na dotazy v O (1) čas. Jediný ukazatel skoku vezme jakýkoli dotaz alespoň do poloviny stromu, po kterém zodpoví dotaz vylézáním pouze na jeden žebřík. Výsledkem je O (n logn) doba předběžného zpracování a O (1) čas dotazu. Předběžné zpracování lze dále snížit na O (n) čas aplikací Metoda čtyř Rusů, ve kterém je strom zmenšen na menší strom s lineárním předzpracováním a sbírka velmi malých stromů, které jsou dostatečně malé na to, aby vyčerpávající výčet všech stromů a předzpracování těchto stromů bylo stále O (n) čas. Stromy velikosti (log n) / 4 dostačující.

Berkmanovo a Viškinovo řešení

Odlišné řešení je způsobeno Berkmanem a Vishkinem.[2][4] Toto řešení je založeno naProhlídka Euler technika zpracování stromů. Hlavní pozorování je, že LA (proti,d) je první uzel hloubkyd který se objeví v Eulerově turné po posledním vystoupení proti. Tím, že se vytvoří Eulerova prohlídka a související informace o hloubce, se problém sníží na dotaz na pole s názvem najít menší (FS) .Pro pole Aa platný index i, FS (i,X) vrátí první index j>i takhle A[i]<X (zde používáme X=d+1). Efektivní řešení problému FS je obecně těžké, ale jednodušší pro speciální případ, který vyplývá z prohlídek Euler; v tomto případě se sousední prvky liší o ± 1. Tato myšlenka poskytuje čas dotazu O (1) s algoritmem předzpracování složitosti O (n logn). Doba předzpracování je vylepšena na O (n) aplikací Metoda čtyř Rusů.

Viz také

Reference

  1. ^ A b C Bender, Michael A .; Farach-Colton, Martin (2004). "Problém předků úrovně se zjednodušil". Teor. Comput. Sci. 321: 5–12. doi:10.1016 / j.tcs.2003.05.002.
  2. ^ A b Berkman, Omer; Vishkin, Uzi (duben 1994). "Nalezení předků úrovně na stromech". J. Comput. Syst. Sci. 2. 48 (2): 214–230. doi:10.1016 / S0022-0000 (05) 80002-9.
  3. ^ Kmett, Edward. „O (log n) trvalý online výpočet nejnižšího společného předka bez předzpracování“. Citováno 8. května 2013.
  4. ^ Ben-Amram, Amir M. (2009). „Eulerova cesta ke statickým předkům na úrovni“. arXiv:0909.1030v1 [cs.DS ].