Kontrakce stromu - Tree contraction - Wikipedia

tento článek je sirotek, jako žádné další články odkaz na to. Prosím zavést odkazy na tuto stránku z související články; zkuste Najít odkaz nástroj pro návrhy. (Prosinec 2015)

v počítačová věda, paralelní kontrakce stromu je široce použitelná technika pro paralelní řešení velkého počtu strom problémů a používá se jako technika návrhu algoritmu pro návrh velkého počtu paralelních graf algoritmy. Paralelní kontrakci stromu zavedl Gary L. Miller a John H. Reif,^[1] a následně byl upraven tak, aby zlepšil účinnost X. On a Y. Yesha,^[2] Hillel Gazit, Gary L. Miller a Shang-Hua Teng^[3] a mnoho dalších.^[4]

Kontrakce stromu byla použita při navrhování mnoha efektivních paralelní algoritmy, počítaje v to výraz hodnocení, nález nejnižší společní předkové, izomorfismus stromů, izomorfismus grafu, maximální izomorfismus podstromu, běžná eliminace subexprese, výpočet 3 spojených komponent grafu a nalezení explicitního rovinného vložení a rovinný graf^[5]

Na základě výzkumu a práce na kontrakci paralelních stromů byly navrženy různé algoritmy zaměřené na zlepšení efektivity nebo jednoduchosti tohoto tématu. Tento článek se tímto zaměřuje na konkrétní řešení, které je variantou algoritmu od Millera a Reifa a jeho aplikace.

Úvod

Během posledních několika desetiletí došlo k významnému výzkumu odvozování nových paralelních algoritmů pro různé problémy s cílem navrhnout vysoce paralelní (polylogaritmická hloubka ), algoritmy efektivní z hlediska práce (lineární v postupné době běhu).^[1] U některých problémů se strom ukazuje jako pěkné řešení. Při řešení těchto problémů můžeme někdy získat více paralelismu jednoduše tím, že náš problém představíme jako strom.

Vzhledem k obecné definici stromu existuje kořenový vrchol a několik podřízených vrcholů připojených ke kořenu.^[6] A dětské vrcholy mohou mít děti samy atd. Atd. Cesty nakonec sestupují k listím, které jsou definovány jako terminál stromu. Na základě tohoto obecného stromu pak můžeme přijít s některými speciálními případy: (1) vyvážený binární strom; (2) spojový seznam.^[7] Vyvážený binární strom má přesně dvě větve pro každý vrchol kromě listů. To dává O (log n) vázané na hloubku stromu.^[8] Propojený seznam je také strom, kde má každý vrchol pouze jedno dítě. Můžeme také dosáhnout O (log n) hloubky pomocí lámání symetrie.^[9]

Vzhledem k obecnému případu stromu bychom chtěli zachovat vazbu na O (log n) bez ohledu na to, zda je nevyvážený nebo podobný seznamu nebo kombinaci obou. K řešení tohoto problému používáme tzv. Algoritmus s názvem součet prefixů pomocí Eulerova prohlídková technika.^[10] S technikou prohlídky Euler by strom mohl být reprezentován v plochém stylu, a tak by mohla být částka předpony použita na libovolný strom v tomto formátu. Ve skutečnosti lze prefixový součet použít na libovolnou sadu hodnot a binární operace, které tvoří skupinu: binární operace musí být asociativní, každá hodnota musí mít inverzní funkci a existuje hodnota identity.

S trochou přemýšlení můžeme najít několik výjimečných případů, kdy se součet prefixů stane neschopným nebo neúčinným. Zvažte příklad násobení, když sada hodnot obsahuje 0. Nebo existují některé běžně požadované operace jsou max () a min (), které nemají inverze. Cílem je hledat algoritmus, který pracuje na všech stromech v očekávané O (n) práci a O (log n) hloubce. V následujících částech bude pro splnění tohoto cíle navržen algoritmus Rake / Compress.^[11]

Definice

Obr.1: Rake operace

Obr. 2: Provoz komprese

Než se pustíme do samotného algoritmu, nejprve se podíváme na několik terminologií, které budou použity později.

• Hrábě^[12] - Rake step spojuje každý levý list binárních uzlů s rodičem. Spojením myslíme, že prochází funkčním procesem, který dosahuje operace, kterou chceme provést. Příklad shrnovače je uveden na obrázku 1.
• Komprimovat^[12] - Krok komprese je ve skutečnosti sled několika událostí: (1) Najděte nezávislou sadu unárních uzlů. (Nezávislost je zde definována tak, že žádné dva nejsou sousedé, což znamená, že neexistuje vztah rodič-dítě) (2) Připojte každý uzel v nezávislé množině s podřízenou (všimněte si, že nezávislá sada není jedinečná). Příklad komprese je uveden na obrázku 2.

A aby bylo možné vyřešit skutečné problémy pomocí kontrakce stromu, má algoritmus strukturu:

Opakujte, dokud se strom nestane unárním uzlem {Rake; Komprimovat;}

Analýza

Prozatím předpokládejme, že všechny uzly mají méně než tři děti, a to binární. Obecně lze říci, že pokud je stupeň ohraničený, hranice bude platit.^[13] Ale pro jednoduchost budeme analyzovat binární případ. Ve dvou „zvrhlých“ případech uvedených výše je rake nejlepším nástrojem pro řešení vyvážených binárních stromů a komprimace je nejlepší pro propojené seznamy. Libovolné stromy však budou muset vyžadovat kombinaci těchto operací. Touto kombinací tvrdíme větu, která

• Teorém: Po O (log n) očekávaných rake a kompresních krocích se strom sníží na jediný uzel.

Nyní přeformulujte algoritmus kontrakce stromu následujícím způsobem:

• Vstup: Binární strom zakořeněný v r
• Výstup: Jeden uzel
• Provoz: Posloupnost kontrakčních kroků, z nichž každý sestává z operace hrabání a operace komprese (v libovolném pořadí). Rake operace odstraní všechny listové uzly paralelně. Operace komprimace najde nezávislá sada unárních uzlů a rozdělit vybrané uzly.

Abychom se přiblížili teorému, nejprve se podíváme na vlastnost binárního stromu. Vzhledem k binárnímu stromu T můžeme rozdělit uzly T do 3 skupin: ${ displaystyle T_ {0}}$ obsahuje všechny listové uzly, ${ displaystyle T_ {1}}$ obsahuje všechny uzly s 1 dítětem a ${ displaystyle T_ {2}}$ obsahuje všechny uzly se 2 dětmi. Je snadné vidět, že: ${ displaystyle V (T) = T_ {0} pohár T_ {1} pohár T_ {2}}$. Nyní navrhujeme:

• Nárok: ${ displaystyle | T_ {0} | = | T_ {2} | +1}$

Toto tvrzení lze prokázat silnou indukcí počtu uzlů. Je snadné vidět, že základní případ n = 1 triviálně platí. A dále předpokládáme, že deklarace platí také pro jakýkoli strom s maximálně n uzly. Poté, co dostal strom s n + 1 uzly zakořeněnými v r, se zdá, že existují dva případy:

1. Pokud má r pouze jeden podstrom, zvažte podstrom r. Víme, že podstrom má stejný počet binárních uzlů a stejný počet listových uzlů jako samotný strom. To je pravda, protože kořen je unární uzel. A na základě předchozího předpokladu se nezmění ani unární uzel ${ displaystyle T_ {0}}$ nebo ${ displaystyle T_ {2}}$.
2. Pokud má r dva podstromy, definujeme je ${ displaystyle T_ {0} ^ {L}, T_ {2} ^ {L}}$ být listovými uzly a binárními uzly v levém podstromu. Podobně definujeme totéž ${ displaystyle T_ {0} ^ {R}, T_ {2} ^ {R}}$ pro pravý podstrom. Z předchozího je ${ displaystyle | T_ {0} ^ {L} | = | T_ {2} ^ {L} | +1}$ a ${ displaystyle | T_ {0} ^ {R} | = | T_ {2} ^ {R} | +1}$. Také víme, že T má ${ displaystyle | T_ {0} ^ {L} | + | T_ {0} ^ {R} |}$ listové uzly a ${ displaystyle | T_ {2} ^ {L} | + | T_ {2} ^ {R} | +1}$ binární uzly. Můžeme tedy odvodit:

${ displaystyle | T_ {0} ^ {L} | + | T_ {0} ^ {R} | = | T_ {2} ^ {L} | +1+ | T_ {2} ^ {R} | +1 = (| T_ {2} ^ {L} | + | T_ {2} ^ {R} | +1) +1}$

který prokazuje nárok.

Po tvrzení potom dokážeme lemma, které nás vede k teorému.

• Lemma: Počet uzlů po kroku kontrakce se snižuje o konstantní faktor očekávání.

Předpokládejme, že počet uzlů před kontrakcí bude ma am 'po kontrakci. Podle definice operace rake odstraní všechny ${ displaystyle T_ {0}}$ a operace komprimace odstraní alespoň 1/4 z ${ displaystyle T_ {1}}$ v očekávání. Všechno ${ displaystyle T_ {2}}$ Zůstává. Proto vidíme:

${ displaystyle E [m '] leq | T_ {2} | + { tfrac {3} {4}} * | T_ {1} | leq { tfrac {3} {4}} + { tfrac {3} {4}} * | T_ {1} | + { tfrac {3} {2}} * | T_ {2} | = { tfrac {3} {4}} (1+ | T_ {1 } | + 2 * | T_ {2} |) = { tfrac {3} {4}} (| T_ {0} | + | T_ {1} | + | T_ {2} |) = { tfrac { 3} {4}} m}$

Nakonec na základě tohoto lemmatu můžeme dojít k závěru, že pokud jsou uzly redukovány konstantním faktorem v každé iteraci, po ${ displaystyle O ( log n)}$, zbude pouze jeden uzel.^[14]

Aplikace

Vyhodnocení výrazu

Vyhodnotit výraz daný jako binární strom (tento problém také známý jako binární výrazový strom ),^[15] zvažte, že: Aritmetický výraz je strom, kde listy mají hodnoty z nějaké domény a každý vnitřní vrchol má dvě podřízené položky a štítek z {+, x,%}. A dále předpokládejme, že tyto binární operace lze provádět v konstantním čase.

Nyní ukážeme, že vyhodnocení lze provést s kontrakcí paralelního stromu.^[16]

• Krok 1. Přiřaďte výrazy každému uzlu. Výraz listu je jednoduše hodnota, kterou obsahuje. Napište L + R, L - R nebo L × R pro operátory, kde L a R jsou hodnoty výrazů v levém a pravém podstromu.
• Krok 2. Když je levé (pravé) dítě s 0 dětmi sloučeno do operátoru, nahraďte L (R) hodnotou dítěte.
• Krok 3. Pokud má uzel 1 dítě, má výraz, který je funkcí jedné proměnné. Když je levé (pravé) dítě s 1 dítětem sloučeno do operátoru, nahraďte L (R) výrazem a případně změňte proměnnou ve výrazu na L (R).

V uzlu s 2 dětmi jsou operandy ve výrazu f (L) a g (R), kde f a g jsou lineární funkce, a v uzlu s 1 dítětem je výraz h (x), kde h je lineární funkce a x je buď L nebo R. Tuto invariantnost dokazujeme indukcí. Na začátku je invariant jednoznačně spokojen. Existují tři typy sloučení, jejichž výsledkem není plně vyhodnocený výraz. (1) 1-podřízený uzel je sloučen do 2-podřízeného uzlu. (2) List je sloučen do uzlu 2 dětí. (3) 1-podřízený uzel je sloučen do 1-podřízeného uzlu. Všechny tři typy sloučení nemění invariant. Každé sloučení proto jednoduše vyhodnotí nebo vytvoří lineární funkce, což zabere konstantní čas ^[17]

Reference

externí odkazy

• 6.851: Pokročilé datové struktury Erik Demaine