Legjobb válasz
Különbség a grafikon és a fa adatstruktúrája között:
Grafikon
- A gráfban több út is lehet, azaz a gráfnak lehet egyirányú vagy kétirányú útja a csomópontok között.
- A gráfban nincs ilyen gyökér csomópont.
- A gráfban lehetnek hurkok, áramkörök és önhurkok is.
- A grafikonban ilyen nincs szülő-gyermek kapcsolat.
- A grafikonok bonyolultabbak a fákkal összehasonlítva, mivel lehetnek ciklusai, hurkok stb.
- A grafikont DFS : A mélység első keresése és a BFS fájlban: a Breadth First Search algoritmus.
- A grafikon lehet ciklikus vagy aciklikus.
- A grafikonoknak főleg két típusa van: Irányított és Irányítatlan grafikonok.
- Grafikon alkalmazás likációk: Térképek, algoritmusok, grafikonok színezése, munkaütemezés stb. színezése.
- A Graph-ban nem. az élek függenek a gráftól.
- A grafikon egy hálózati modell.
Fák
- A fa a gráf speciális formája, azaz minimálisan összekapcsolt gráf, amelynek két csúcsa között csak egy útja van.
- A fa a gráf speciális esete, amelyben nincsenek hurkok, áramkörök és önhurkok.
- A fában pontosan egy gyökér van csomópontnak és minden gyermeknek csak egy szülője van.
- A fákban van szülő-gyermek kapcsolat, így az áramlás irányban lehet fentről lefelé vagy fordítva.
- A fák kevésbé bonyolultak, mint a grafikonok, mivel nincsenek ciklusaik, nincsenek önhurkok és még mindig kapcsolódnak.
- A fák bejárása a bejárás egyfajta speciális esete. grafikon. A fát előrendelés , rendben és Rendelés utáni (mindhárom a DFS vagy a BFS algoritmus)
- A fák a DAG kategóriájába tartoznak: A Directed Acyclic Graphs egyfajta irányított gráf, amelynek nincsenek ciklusai.
- A fák különböző típusai: bináris fa , bináris keresési fa, AVL fa, halmok.
- fa alkalmazások : rendezés és keresés, mint a fa bejárása és a bináris keresés.
- A fának mindig n-1 élei vannak.
- Fa hierarchikus modell.
Válasz
Tehát a kd fák első ránézésre inkább elméleti, mint gyakorlati jellegűnek tűnhetnek. De ez valójában nem így van.
A kd fák számos fontos alkalmazást tartalmaznak, amelyek közül néhány a következőket tartalmazza:
1 . A legközelebbi szomszéd keresés
Mondjuk, hogy Közösségi rendőr az okostelefonon. A Social Cop segít az embereknek valós időben jelenteni a bűncselekményeket a legközelebbi rendőrkapitányságon.
Tehát mi tűnik itt problémának?
Igen, jól sejtette. Meg kell keresnünk a bűncselekmény helyszínéhez legközelebb eső rendőrállomást, mielőtt bármit is megpróbálnánk bejelenteni.
Hogyan tehetnénk gyorsan ?
Úgy tűnik, hogy a k-d fák segítenek megtalálni a legközelebbi szomszédot a város kétdimenziós térképének egy pontján. Mindössze annyit kell tennie, hogy elkészít egy kétdimenziós kd fát a város összes rendőrőrsének helyszíneiből, majd megkérdezi a kd fát, hogy megtalálja a legközelebbi rendőrőrsöt a város adott helyéhez. > Rendben, értem, amit tehetnek. De hogyan csinálják?
Ha már tudja, hogyan működnek a bináris keresési fák , megértette, hogyan működnek a kd fák ne legyen semmi új. A k-d fák ugyanúgy segítenek a tér particionálásában, mint a bináris keresési fák a valós vonal felosztásában. A k-d fák rekurzívan particionálnak egy térrészt, létrehozva egy bináris térpartíciót a fa minden szintjén.
Így néz ki egy háromdimenziós kd fával particionált tér háromdimenziós régiója [1]:
Háromdimenziós kd fa. Az első hasítás (piros) a gyökérsejtet (fehér) két részsejtre vágja, amelyek mindegyikét ezután két (zöld) részre osztjuk. Végül mind a négyet két részre osztják (kék). Mivel nincs több hasítás, az utolsó nyolcat levélcellának hívjuk.
És hogyan épül fel a fa?
Kezdésként egy k-dimenziós térben van egy sor pont.Adjunk példát egy kétdimenziós kd fára:
Bevitel: (2,3), (5,4), (9,6), (4,7), (8, 1), (7,2)
Kimenet: Kétdimenziós kd fa [2]:
Bináris keresési fák esetén az egyes belső csomópontok valós vonalának bináris partícióját egy pont a valós vonalon. Hasonlóképpen, egy kétdimenziós kd fa esetén a kétdimenziós derékszögű sík bináris partícióját minden belső csomópontban egy vonal a síkban.
Tehát, abban az esetben A bináris keresési fák közül a belső csomópont által képviselt pont szolgál a valós vonal particionálásához. Hogyan válasszuk ki a particionáló vonalat kétdimenziós kd fák esetén?
Lényegében , választhat bármelyik vonalat, amely áthalad a belső csomópont által képviselt ponton a 2 dimenziós derékszög felosztására.
A fenti kd fa kimenet egyszerű módszerrel készült a partíciós sor kiválasztására a fa minden belső csomópontjában: –
Szint 0 : – Válassza ki az első dimenzióra merőleges particionálási vonalat ( X ebben az esetben) és áthalad a kérdéses csomópont által képviselt ponton.
1 szint: – Válassza ki a particionálási sort merőleges a második dimenzióra (ebben az esetben Y ) és áthalad a a kérdéses csomópont.
: : :
k-1 szint: – Válassza ki a div id = “870698b623”> k. dimenzió és áthalad a képviselt ponton a kérdéses csomópont által. k szint: – Válassza ki a első dimenzióra merőleges particionálási vonalat ( X ) és áthalad a kérdéses csomópont által képviselt ponton.
Tehát alapvetően minden szinten váltakozunk az X és Y dimenziók között hogy a kd fa minden belső csomópontjánál választhassunk partíciós vonalat.
A kd fa [2] csomópontjai mellett látható címkék a partíciós vonal dimenziójának megválasztását jelentik az adott szintű csomópontokban.
Let ” s most megnézzük, hogyan osztja kétdimenziós kd fánk a 2 dimenziós síkot [3]:
Rendben, hogyan tudom végrehajtani a keresést?
Nem azt mondom, hogy ezt rád bízom, hanem te ” A teljes megértéshez más forrásokat kell igénybe vennem. Azt azonban elmondhatom, hogy ez a kd fával történő tér particionálás segíthet megtalálni a legközelebbi szomszédot a tér egy adott pontjához anélkül, hogy feltárnánk az összes partíciót , amire szükségünk van, hogy a divízió valós idejű jelentéseket tegyük a Social Cop számára.
A kd fák legközelebbi szomszédos algoritmusának megértése érdekében itt van egy jó erőforrás: http://www.stanford.edu/class/cs106l/handouts/assignment-3-kdtree.pdf
Engedje meg, hogy gyorsan áttekintsem a kd fák néhány egyéb alkalmazását, mivel a kd fák hátterének nagy részét az első alkalmazás tárgyalása már lefedte.
2. Többdimenziós keresőkulcsot tartalmazó adatbázis-lekérdezések
A (40, 50) és a (15 000, 20000) éves korosztályba tartozó összes munkavállalót megkérdező és havonta (15000, 20000) fizetést kérő lekérdezés geometriai problémává alakítható, ahol az életkor az x tengely mentén kerül ábrázolásra. és a fizetés az y tengely mentén kerül ábrázolásra [4]
[4] Az x tengely az életkorát jelöli az alkalmazott években , az y tengely pedig a havi fizetést ezer rúpia -ban jelöli.
Kétdimenziós kd fa a (életkor, fizetés) összetett indexen segíthet hatékonyan keresni az összes alkalmazottat, akik a fent leírt lekérdezés által meghatározott téglalap alakú térrészbe tartoznak.
3. n-test probléma [5]
Hogyan tudjuk hatékonyan szimulálni a kölcsönös gravitációs vonzerő alatt mozgó tárgyak gyűjteményének mozgását?
A naiv módszer magában foglalná egy objektum közötti gravitációs erő kiszámítását minden más objektum miatt annak érdekében, hogy szimulálja a mozgását gravitációs vonzás alatt. Ezenkívül minden olyan objektum esetében meg kellene tennünk, amely O (n ^ 2) időt vesz igénybe.
A k-d fák használatával azonban fel tudjuk osztani a teret, és a tér minden egyes felosztásához megtudhatjuk annak teljes hatását a tér többi részére. Az alábbiakban látható az algoritmus álkódja [6].
Helyezze az objektumokat egy fába. Kezdje a fa alsó szintjén, Minden régióban, a fa mélységében d : Ha bármelyik gyerek leveles, akkor számítsa ki az interakciót. Számítsa ki a ” Többpólusú bővítés “Konvertálja ezt a szülőcsomópont helyi kiterjesztésévé, és adja át. Lépjen tovább a d-1 szintre. Amikor eljutunk a fa tetejére, térjünk vissza a fán, összegezve a helyi kiterjedéseket.
4. Színcsökkentés [7]
Mi az intelligens módszer 256 szín kiválasztására a színes kép megjelenítéséhez?
A naiv módszer a leggyakrabban használt színek felvétele lehet.
Egy hatékonyabb módszer azonban a színeket képviselheti RGB értékeket állítson össze és hozzon létre egy háromdimenziós kd fát a kép összes színét tartalmazó tér felosztása érdekében. A k-d fa felépítése leáll, ha a levélcsomópontok száma 256-ra válik. Ezután a 256 partíció mindegyikének RGB-értékének átlagát felhasználhatjuk egy 256 színpaletta megszerzésére a színes képhez.
Hivatkozások: [1], [2], [3]: http://en.wikipedia.org/wiki/Kd-tree [4]: Besorolás a legközelebbi szomszédok használatával [5], [6], [7] : kD fák