Nejnižší společný předek - Lowest common ancestor

V tomto stromu nejnižší společný předek uzlů X a y je označen tmavě zeleně. Ostatní běžní předkové jsou zobrazeni světle zeleně.

v teorie grafů a počítačová věda, nejnižší společný předek (LCA) dvou uzlů proti a w v strom nebo směrovaný acyklický graf (DAG) T je nejnižší (tj. nejhlubší) uzel, který má obojí proti a w jako potomci, kde každý uzel definujeme jako potomka sebe sama (takže pokud proti má přímé spojení z w, w je nejnižší společný předek).

LCA z proti a w v T je sdíleným předkem společnosti proti a w který je umístěn nejdále od kořene. Výpočet nejnižších společných předků může být užitečný například jako součást postupu pro stanovení vzdálenosti mezi dvojicemi uzlů ve stromu: vzdálenost od proti na w lze vypočítat jako vzdálenost od kořene k protiplus vzdálenost od kořene k wmínus dvojnásobek vzdálenosti od kořene k jejich nejnižšímu společnému předkovi (Djidjev, Pantziou & Zaroliagis 1991 ). v ontologie, nejnižší společný předek je také známý jako nejméně společný předek.

V stromová datová struktura kde každý uzel ukazuje na svého rodiče, lze nejnižšího společného předka snadno určit nalezením prvního průsečíku cest z proti a w do kořene. Obecně je výpočetní čas potřebný pro tento algoritmus Ach) kde h je výška stromu (délka nejdelší cesty od listu ke kořenu). Existuje však několik algoritmů pro zpracování stromů, takže nejnižší společné předky lze najít rychleji. Tarjanův offline nejnižší algoritmus společných předků, například předzpracovává strom v lineárním čase, aby poskytoval LCA dotazy v konstantním čase. Obecně platí, že existují podobné algoritmy, ale se superlineární složitostí.

Dějiny

Nejnižší společný problém předků byl definován Alfred Aho, John Hopcroft, a Jeffrey Ullman  (1973 ), ale Dov Harel a Robert Tarjan  (1984 ) jako první vyvinuli optimálně efektivní nejnižší společnou datovou strukturu předků. Jejich algoritmus zpracovává libovolný strom v lineárním čase pomocí a těžký rozklad cesty, takže na následující nejnižší dotazy společného předka lze odpovídat v konstantním čase na jeden dotaz. Jejich datová struktura je však složitá a obtížně implementovatelná. Tarjan také našel jednodušší, ale méně efektivní algoritmus založený na najít odbor datová struktura pro výpočet nejnižších společných předků offline dávky párů uzlů.

Baruch Schieber a Uzi Vishkin  (1988 ) zjednodušil datovou strukturu Harel a Tarjana, což vedlo k implementovatelné struktuře se stejnými asymptotickými předzpracováním a časovými limity dotazu. Jejich zjednodušení je založeno na principu, že u dvou zvláštních druhů stromů je snadné určit nejnižší společné předky: pokud je strom cestou, lze nejnižšího společného předka vypočítat jednoduše z minima úrovní dvou dotazovaných uzly, zatímco pokud je strom a kompletní binární strom, uzly mohou být indexovány takovým způsobem, že nejnižší společní předkové se redukují na jednoduché binární operace s indexy. Struktura Schiebera a Vishkina rozkládá jakýkoli strom na sbírku cest, takže spojení mezi cestami má strukturu binárního stromu a kombinuje obě tyto dvě jednodušší techniky indexování.

Omer Berkman a Uzi Vishkin (1993 ) objevil zcela nový způsob, jak odpovědět na nejnižší dotazy běžných předků, a znovu dosáhnout lineárního času předzpracování s konstantním časem dotazu. Jejich metoda zahrnuje formování Prohlídka Euler grafu vytvořeného ze vstupního stromu zdvojnásobením každé hrany a pomocí této prohlídky k napsání sekvence čísel úrovní uzlů v pořadí, v jakém je prohlídka navštíví; nejnižší dotaz společného předka lze poté transformovat na dotaz, který hledá minimální hodnotu vyskytující se v nějakém podintervalu této posloupnosti čísel. Pak to zvládnou rozsah minimální dotaz problém kombinací dvou technik, jedné techniky založené na předpočítání odpovědí na velké intervaly, které mají velikosti, které jsou mocninami dvou, a druhé založené na vyhledávání tabulek pro dotazy s malým intervalem. Tuto metodu později ve zjednodušené podobě představili Michael Bender a Martin Farach-Colton  (2000 ). Jak bylo dříve pozorováno Gabow, Bentley & Tarjan (1984), minimální problém rozsahu lze zase převést zpět na problém nejnižšího společného předka pomocí techniky Kartézské stromy.

Další zjednodušení provedla Alstrup a kol. (2004) a Fischer & Heun (2006).

Varianta problému je dynamický problém LCA, ve kterém by měla být připravena datová struktura pro zpracování LCA dotazů smíchaných s operacemi, které mění strom (tj. Přeskupit strom přidáním a odebráním hran). Tuto variantu lze vyřešit v ${ displaystyle O ( log N)}$ čas^{[je třeba další vysvětlení ]} pro všechny úpravy a dotazy. To se provádí udržováním doménové struktury pomocí datové struktury dynamických stromů s rozdělením podle velikosti; to pak udržuje těžký rozklad každého stromu a umožňuje LCA dotazy provádět v logaritmickém čase ve velikosti stromu.^{[Citace je zapotřebí ]}

Rozšíření o směrované acyklické grafy

DAG se společnými předky X a y ve světle zelené barvě a jejich nejnižší společní předkové v tmavě zelené barvě.

Zatímco původně byl studován v kontextu stromů, pojem nejnižších společných předků lze definovat pro směrované acyklické grafy (DAG) pomocí jedné ze dvou možných definic. V obou se předpokládá, že okraje DAG směřují od rodičů k dětem.

• Dáno G = (PROTI, E), Aït-Kaci a kol. (1989) definovat a poset (PROTI, ≤) takhle X ≤ y iff X je dosažitelný z y. Nejnižší společní předkové X a y jsou pak minimální prvky pod ≤ společné množiny předků {z ∈ PROTI | X ≤ z a y ≤ z}.
• Bender a kol. (2005) dal ekvivalentní definici, kde nejnižší společné předky X a y jsou uzly out-stupeň nula v podgraf z G vyvolané množinou společných předků X a y.

Ve stromu je nejnižší společný předek jedinečný; v DAG z n uzly, každá dvojice uzlů může mít tolik jako n-2 LCA (Bender a kol. 2005 ), zatímco existence LCA pro pár uzlů není zaručena ani v libovolných připojených DAG.

Algoritmus hrubé síly pro hledání nejnižších společných předků je dán vztahem Aït-Kaci a kol. (1989): najít všechny předky X a y, pak vraťte maximální prvek křižovatky dvou sad. Existují lepší algoritmy, které analogicky k algoritmům LCA na stromech předzpracovávají graf, aby umožňovaly dotazy LCA v konstantním čase. Problém LCA existence lze optimálně vyřešit pro řídké DAG pomocí O (|PROTI||E|) algoritmus kvůli Kowaluk & Lingas (2005).

Dash a kol. (2013) představit jednotný rámec pro předzpracování řízených acyklických grafů pro výpočet nejnižších společných předků v konstantním čase. Jejich rámec může dosáhnout téměř lineárních časů předběžného zpracování pro řídké grafy a je k dispozici pro veřejné použití.^[1]

Aplikace

Problém výpočtu nejnižších společných předchůdců tříd v hierarchie dědičnosti vzniká při provádění objektově orientované programování systémy (Aït-Kaci a kol. 1989 ). Problém LCA také nachází uplatnění v modelech složité systémy nalezen v distribuované výpočty (Bender a kol. 2005 ).

Viz také

• Úroveň problému předků
• Semilattice

Reference

• Aho, Alfrede; Hopcroft, Johne; Ullman, Jeffrey (1973), „O hledání nejnižších společných předků ve stromech“, Proc. 5. ACM Symp. Theory of Computing (STOC), str. 253–265, doi:10.1145/800125.804056.
• Aït-Kaci, H .; Boyer, R .; Lincoln, P .; Nasr, R. (1989), „Efektivní implementace mřížových operací“ (PDF), Transakce ACM v programovacích jazycích a systémech, 11 (1): 115–146, CiteSeerX  10.1.1.106.4911, doi:10.1145/59287.59293.
• Alstrup, Stephen; Gavoille, Cyril; Kaplan, Haim; Rauhe, Theis (2004), „Nejbližší společní předkové: průzkum a nový algoritmus pro distribuované prostředí“, Teorie výpočetních systémů, 37 (3): 441–456, CiteSeerX  10.1.1.76.5973, doi:10.1007 / s00224-004-1155-5. Předběžná verze se objevila ve SPAA 2002.
• Bender, Michael A .; Farach-Colton, Martin (2000), „Problém LCA se vrátil“, Sborník ze 4. latinskoamerického symposia o teoretické informatice, Přednášky z informatiky, 1776, Springer-Verlag, str.88–94, doi:10.1007/10719839_9, ISBN  978-3-540-67306-4.
• Bender, Michael A .; Farach-Colton, Martín; Pemmasani, Giridhar; Skiena, Steven; Sumazin, Pavel (2005), „Nejnižší společní předkové na stromech a směrované acyklické grafy“ (PDF), Journal of Algorithms, 57 (2): 75–94, doi:10.1016 / j.jalgor.2005.08.001.
• Berkman, Omer; Vishkin, Uzi (1993), "Rekurzivní paralelní datová struktura hvězdného stromu", SIAM Journal on Computing, 22 (2): 221–242, doi:10.1137/0222017.
• Dash, Santanu Kumar; Scholz, Sven-Bodo; Herhut, Stephan; Christianson, Bruce (2013), „Škálovatelný přístup k výpočtu reprezentativního nejnižšího společného předka v řízených acyklických grafech“ (PDF), Teoretická informatika, 513: 25–37, doi:10.1016 / j.tcs.2013.09.030, hdl:2299/12152
• Djidjev, Hristo N .; Pantziou, Grammati E .; Zaroliagis, Christos D. (1991), „Výpočet nejkratších cest a vzdáleností v rovinných grafech“, Automaty, jazyky a programování: 18. mezinárodní kolokvium, Madrid, Španělsko, 8. – 12. Července 1991, sborník, Přednášky v informatice, 510, Springer, str. 327–338, doi:10.1007/3-540-54233-7_145, ISBN  978-3-540-54233-9.
• Fischer, Johannes; Heun, Volker (2006), „Teoretická a praktická vylepšení problému RMQ s aplikacemi pro LCA a LCE“, Sborník 17. výročního sympozia o kombinatorickém porovnávání vzorů, Přednášky v informatice, 4009, Springer-Verlag, str. 36–48, CiteSeerX  10.1.1.64.5439, doi:10.1007/11780441_5, ISBN  978-3-540-35455-0.
• Gabow, Harold N .; Bentley, Jon Louis; Tarjan, Robert E. (1984), "Škálování a související techniky pro geometrické problémy", STOC '84: Proc. 16. ACM Symposium on Theory of Computing, New York, NY, USA: ACM, s. 135–143, doi:10.1145/800057.808675, ISBN  978-0897911337.
• Harel, Dov; Tarjan, Robert E. (1984), „Rychlé algoritmy pro hledání nejbližších společných předků“, SIAM Journal on Computing, 13 (2): 338–355, doi:10.1137/0213024.
• Kowaluk, Miroslaw; Lingas, Andrzej (2005), „LCA dotazy v řízených acyklických grafech“, Caires, Luís; Italiano, Giuseppe F.; Monteiro, Luís; Palamidessi, Catuscia; Yung, Moti (eds.), Automata, Languages ​​and Programming, 32. mezinárodní kolokvium, ICALP 2005, Lisabon, Portugalsko, 11. – 15. Července 2005, sborník, Přednášky v informatice, 3580, Springer, str.241–248, CiteSeerX  10.1.1.460.6923, doi:10.1007/11523468_20, ISBN  978-3-540-27580-0
• Schieber, Baruch; Vishkin, Uzi (1988), „O hledání nejnižších společných předků: zjednodušení a paralelizace“, SIAM Journal on Computing, 17 (6): 1253–1262, doi:10.1137/0217079.

externí odkazy

• Nejnižší společný předek binárního vyhledávacího stromu Kamal Rawat
• Pythonská implementace algoritmu Bender a Farach-Colton pro stromy tím, že David Eppstein
• Implementace Pythonu pro libovolné směrované acyklické grafy
• Poznámky k přednášce o LCA z kurzu MIT Data Structures 2003. Kurz od Erik Demaine, poznámky napsané Loizosem Michaelem a Christosem Kapoutsisem. Poznámky z roku 2007 nabízející stejný kurz, napsaná Alison Cichowlas.
• Nejnižší společný předek v binárních stromech v C. Zjednodušená verze Schieber – Vishkinovy ​​techniky, která funguje pouze pro vyvážené binární stromy.
• Video z Donald Knuth vysvětlující techniku ​​Schieber – Vishkin
• Rozsah Minimální dotaz a článek Nejnižší společný předek v Topcoderu
• Dokumentace k balíčku lca pro Haskell Edward Kmett, který zahrnuje algoritmus seznamu náhodných přístupů se zkoseným binárním přístupem. Čistě funkční datové struktury pro online LCA snímky pro stejný balíček.