Nejlepší odpověď
Rozdíl mezi grafem a stromovou datovou strukturou:
Graf
- V grafu může existovat více než jedna cesta, tj. graf může mít jednosměrné nebo obousměrné cesty mezi uzly.
- V grafu neexistuje žádný takový koncept kořenový uzel.
- Graf může mít smyčky, obvody a může mít také vlastní smyčky.
- V Graphu není žádný takový vztah rodič-dítě.
- Grafy jsou ve srovnání se stromy složitější, protože mohou obsahovat cykly, smyčky atd.
- Grafem prochází DFS : Depth First Search a v BFS : Algoritmus Breadth First Search.
- Graf může být cyklický nebo acyklický.
- Existují hlavně dva typy grafů: Directed a Undirected graphs.
- Graph app přednášky: Zbarvení map, algoritmů, zbarvení grafu, plánování úloh atd.
- V grafu č. hran závisí na grafu.
- Graf je síťový model.
Stromy
- Strom je speciální forma grafu, tj. minimálně propojený graf, který má pouze jednu cestu mezi dvěma vrcholy.
- Strom je speciální případ grafu, který nemá žádné smyčky, žádné obvody a žádné smyčky.
- Ve stromu je přesně jeden kořen uzel a každé dítě má pouze jednoho rodiče.
- Ve stromech existuje vztah rodič-dítě, takže tok může být tam se směrem shora dolů nebo naopak.
- Stromy jsou méně složité než grafy, protože nemají cykly, samy smyčky a jsou stále připojeny.
- Traverz stromů je druh zvláštního případu traversalu grafu. Strom je procházen v předobjednávce , v pořádku a Post-Order (všechny tři v DFS nebo v BFS algorithm)
- Stromy patří do kategorie DAG: Directed Acyclic Graphs je druh orientovaného grafu, který nemá žádné cykly.
- Různé typy stromů jsou: Binární strom , Binární vyhledávací strom, strom AVL, hromady.
- Stromové aplikace : třídění a vyhledávání jako procházení stromů a binární vyhledávání.
- Strom má vždy n-1 hrany.
- Strom je hierarchický model.
Odpověď
Takže kd stromy se na první pohled mohou zdát více teoretické než praktické. Ale to opravdu neplatí.
Stromy kd obsahují řadu důležitých aplikací, z nichž některé zahrnují:
1 . Hledání nejbližšího souseda
Řekněme, že máte v úmyslu vybudovat Social Cop ve smartphonu. Social Cop pomáhá lidem hlásit trestné činy na nejbližší policejní stanici v reálném čase.
Takže co se tady zdá být problémem?
Ano, uhodli jste správně. Než se pokusíme něco nahlásit, musíme vyhledat policejní stanici nejblíže k místu zločinu.
Jak bychom to mohli udělat rychle ?
Zdá se, že stromy k-d vám pomohou najít nejbližšího souseda k bodu na dvourozměrné mapě vašeho města. Musíte pouze zkonstruovat dvourozměrný strom kd z umístění všech policejních stanic ve vašem městě a poté vyhledat strom kd a vyhledat nejbližší policejní stanici k danému místu ve městě.
Dobře, chápu, co mohou dělat. Jak to ale dělají?
Pokud již víte, jak binární vyhledávací stromy fungují, pochopte, jak by kd stromy fungovaly být nic nového. stromy k-d pomáhají při dělení prostoru stejně jako binární vyhledávací stromy pomáhají při dělení skutečné linie . stromy k-d rekurzivně rozdělují oblast prostoru a vytvářejí oddíl binárního prostoru na každé úrovni stromu.
Takto vypadá trojrozměrná oblast prostoru rozdělená na trojrozměrný kd strom [1]:
Trojrozměrný kd strom. První rozdělení (červené) rozřízne kořenovou buňku (bílou) na dva dílčí články, z nichž každý je poté rozdělen (zeleně) na dva dílčí články. Nakonec je každá z těchto čtyř rozdělena (modře) na dva subcells. Jelikož již nedochází ke štěpení, konečných osm se nazývá listové buňky.
A jak je strom konstruován?
Pro začátek máte v k-dimenzionálním prostoru sadu bodů.Uveďme si příklad dvourozměrného stromu kd:
Vstup: (2,3), (5,4), (9,6), (4,7), (8, 1), (7,2)
Výstup: 2rozměrný kd strom [2]:
V případě binárních vyhledávacích stromů je binární oddíl reálného řádku v každém interním uzlu reprezentován bodem na skutečné linii. Podobně v případě 2dimenzionálního kd stromu je binární oddíl 2rozměrné kartézské roviny v každém vnitřním uzlu reprezentován řádek v rovině.
Takže v případě z binárních vyhledávacích stromů slouží bod představovaný interním uzlem jako bod použitý k rozdělení skutečné čáry. Jak zvolíme dělící čáru v případě 2rozměrných kd stromů?
V zásadě , můžete zvolit libovolnou přímku procházející bodem představovaným vnitřním uzlem rozdělit 2rozměrnou kartézskou rovinu.
Výstup stromu kd výše byl sestrojen pomocí jednoduché metody pro výběr dělící čáry v každém interním uzlu stromu: –
Úroveň 0 : – Vyberte dělící čáru kolmou k první dimenzi ( X v tomto případě) a procházení bodem představovaným daným uzlem.
Úroveň 1 : – Vyberte dělicí čáru kolmo k druhé dimenzi (v tomto případě Y ) a procházející bodem reprezentovaným dotyčný uzel.
: : :
Úroveň k-1 : – Vyberte dělicí čáru kolmou k kth dimenze a procházející znázorněným bodem dotyčným uzlem. Úroveň k : – Vyberte dělící čáru kolmou k první dimenzi ( X (v tomto případě) a procházení bodem představovaným daným uzlem.
Takže v zásadě na každé úrovni střídáme dimenzi X a Y za účelem výběru dělicí čáry v každém vnitřním uzlu stromu kd.
Štítky, které vidíte vedle každého z uzlů stromu kd [2], představují volbu dimenze pro dělící čáru v uzlech na této úrovni.
Nechte “ Nyní vidíme, jak náš 2dimenzionální kd strom rozděluje 2dimenzionální rovinu [3]:
Fajn, jak provedu vyhledávání?
Nebudu říkat, že to nechám na vás, ale na vás. Abych tomu úplně porozuměl, musím využít pomoci některých dalších zdrojů. Mohu vám však říci, že toto rozdělení prostoru pomocí stromu kd vám pomůže najít nejbližšího souseda ke konkrétnímu bodu v prostoru bez nutnosti prozkoumávat všechny oddíly , což je to, co jsme potřebovali, dělat přehledy v reálném čase pro sociálního policistu.
Abychom porozuměli algoritmu nejbližšího souseda na stromech kd, máme zde dobrý zdroj: http://www.stanford.edu/class/cs106l/handouts/assignment-3-kdtree.pdf
Dovolte mi, abych vás rychle provedl některými dalšími aplikacemi stromů kd, protože většina pozadí stromů kd již byla zahrnuta v diskusi o první aplikaci.
2. Databázové dotazy zahrnující vícerozměrný vyhledávací klíč
Dotaz s dotazem na všechny zaměstnance ve věkové skupině (40, 50) a výdělkem v rozmezí (15 000, 20000) za měsíc lze transformovat do geometrického problému, kde je věk vykreslen podél osy x a plat je vynesen podél osy y [4]
[4] Osa x označuje věk zaměstnanec za let a osa y označuje měsíční plat v tisících rupií .
2rozměrný kd strom ve složeném indexu (věk, plat) vám pomůže efektivně vyhledat všechny zaměstnance, kteří spadají do obdélníkové oblasti prostoru definované výše popsaným dotazem.
3. Problém n-těla [5]
Jak můžeme efektivně simulovat pohyby kolekce objektů pohybujících se pod vzájemnou gravitační přitažlivostí?
Naivní metoda by zahrnovala výpočet gravitační síly mezi objektem způsobené každým jiným objektem, aby se simuloval jeho pohyb pod gravitační přitažlivostí. Navíc bychom to museli udělat pro každý objekt, kterému by trvalo O (n ^ 2) čas.
Pomocí stromů k-d však můžeme prostor rozdělit a pro každé další rozdělení prostoru zjistit jeho celkový účinek na zbytek prostoru. Níže je uveden pseudokód [6] algoritmu.
Umístěte objekty do stromu. Začněte na spodní úrovni stromu. Pro každou oblast v hloubce d ve stromu: Pokud jsou nějaké podřízené listy, spočítejte interakci přímo Vypočítat “ Vícepólová expanze „Převeďte ji na místní expanzi nadřazeného uzlu a předejte ji. Pokračujte na úroveň d-1. Když se dostaneme na vrchol stromu, vracíme se zpět dolů po stromu a sečteme místní expanze.
4. Redukce barev [7]
Co je inteligentní způsob, jak vybrat 256 barev, které představují plně barevný obrázek?
Naivní metodou může být vyzvednutí barev, které se používají nejčastěji.
Účinnější metoda by však mohla reprezentovat barvy z hlediska jejich RGB a vytvoření trojrozměrného kd stromu za účelem rozdělení prostoru obsahujícího všechny barvy obrázku. Konstrukce stromu k-d by se zastavila, když by se počet uzlů listu rovnal 256. Průměr hodnoty RGB každého z 256 oddílů by pak mohl být použit k získání palety 256 barev pro plný barevný obraz.
Reference: [1], [2], [3]: http://en.wikipedia.org/wiki/Kd-tree [4]: Klasifikace podle nejbližších sousedů [5], [6], [7] : stromy kD