Paras vastaus
Ero kuvaajan ja puun tietorakenteen välillä:
Kaavio
- Kaaviossa voi olla useampi kuin yksi polku, ts. käyrällä voi olla yksisuuntaisia tai kaksisuuntaisia polkuja solmujen välillä.
- Kaaviossa ei ole sellaista käsitystä juuri -solmu.
- Kaaviossa voi olla sekä silmukoita, piirejä että itsesilmukoita.
- Kaaviossa ei ole sellaisia vanhemman ja lapsen välinen suhde.
- Kuvaajat ovat monimutkaisempia verrattuna puihin, koska siinä voi olla jaksoja, silmukoita jne.
- Kaaviota kulkee DFS : Ensimmäisen syvyyden haku ja BFS : Leveys ensimmäisen haun algoritmi.
- Kuvaaja voi olla syklinen tai asyklinen.
- Kuvaajia on pääasiassa kahta tyyppiä: Suunnatut ja Ohjaamattomat kaaviot.
- Kaavio-sovellus lations: Karttojen, algoritmien, graafien väritys, työn aikataulutus jne. väritys.
- Graph, no. reunojen määrä riippuu kaaviosta.
- Kuvaaja on verkkomalli.
Puut
- Puu on erityinen kaavion muoto eli minimaalisesti yhdistetty kaavio, jolla on vain yksi polku kahden pikselin välissä.
- Puu on erikoistapaus graafista, jossa ei ole silmukoita, ei piirejä eikä itsesilmukoita.
- Puussa on täsmälleen yksi juuri solmu ja jokaisella lapsella on vain yksi vanhempi.
- Puissa on vanhemman ja lapsen suhde, joten virta voi olla siellä suunnan kanssa ylhäältä alas tai päinvastoin.
- Puut eivät ole yhtä monimutkaisia kuin kaavioissa, sillä niissä ei ole syklejä, ei itsesilmukoita ja jotka ovat edelleen yhteydessä toisiinsa.
- Puun kulkeminen on eräänlainen erityinen tapa kulkea. kaaviosta. Puu kulkee ennakkotilauksessa , järjestyksessä ja Tilauksen jälkeinen (kaikki kolme DFS: ssä tai BFS: ssä algoritmi)
- Puut kuuluvat DAG-luokkaan: Directed Acyclic Graphs on eräänlainen suunnattu graafi, jolla ei ole syklejä.
- Erilaisia puita ovat: Binaarinen puu , Binaarinen hakupuu, AVL-puu, kasat.
- Puusovellukset : lajittelu ja haku kuten Puun läpikulku ja binaarihaku.
- Puussa on aina n-1 reunat.
- Puu on hierarkkinen malli.
Vastaus
Joten kd-puut saattavat ensi silmäyksellä näyttää olevan luonteeltaan enemmän teoreettisia kuin käytännöllisiä. Mutta näin ei todellakaan ole.
Kd-puissa on useita tärkeitä sovelluksia, joista joitain ovat:
1 . Lähin naapurihaku
Sanotaan, että aiot rakentaa Sosiaalinen poliisi älypuhelimessasi. Social Cop auttaa ihmisiä ilmoittamaan rikoksista reaaliajassa lähimmälle poliisiasemalle.
Joten mikä tässä näyttää olevan ongelma?
Kyllä, arvasit oikein. Meidän on etsittävä rikoksen sijaintia lähinnä oleva poliisiasema ennen kuin yritämme ilmoittaa mistä tahansa.
Kuinka voimme tehdä sen nopeasti ?
Näyttää siltä, että k-d-puut voivat auttaa sinua löytämään lähimmän naapurin pisteeseen kaupunkisi kaksiulotteisella kartalla. Sinun tarvitsee vain rakentaa 2-ulotteinen kd-puu kaupunkisi kaikkien poliisiasemien sijainneista ja kysyä sitten kd-puuta löytääksesi lähimmän poliisiaseman mihin tahansa kaupungin sijaintiin.
Okei, saan mitä he voivat tehdä. Mutta miten he tekevät sen?
Jos tiedät jo, miten binaarihakupuut toimivat, ymmärrät kuinka kd-puut toimivat ole mitään uutta. k-d-puut auttavat jakamaan tilaa samalla tavalla kuin binaariset hakupuut auttavat jakamaan todellisen viivan . k-d-puut jakavat rekursiivisesti tilan alueen luomalla binäärisen avaruusosion puun jokaiselle tasolle.
Tältä näyttää kolmiulotteisen kd-puun osioima avaruuden kolmiulotteinen alue [1]:
Kolmiulotteinen kd-puu. Ensimmäinen jako (punainen) leikkaa juurisolun (valkoinen) kahteen alisoluun, joista jokainen jaetaan sitten (vihreäksi) kahteen alisoluun. Lopuksi kukin näistä neljästä on jaettu (sininen) kahteen alisoluun. Koska halkaisua ei ole enää, kahdeksan viimeistä kutsutaan lehtisoluiksi.
Ja miten puu rakennetaan?
Aluksi sinulla on joukko pisteitä k-ulotteisessa tilassa.Annetaan itsellemme esimerkki 2-ulotteisesta kd-puusta:
Syöttö: (2,3), (5,4), (9,6), (4,7), (8, 1), (7,2)
Tulos: 2-ulotteinen kd-puu [2]:
Binaarihakupuiden tapauksessa jokaisen sisäisen solmun todellisen linjan binaariosio on -kohta . div> viiva tasossa.
Joten, jos binaaristen hakupuiden kohdalla sisäisen solmun edustama piste toimii todellisen viivan osiointipisteenä. Kuinka valitsemme osituslinjan 2-ulotteisten kd-puiden tapauksessa?
Pohjimmiltaan , voit valita minkä tahansa viivan, joka kulkee sisäisen solmun edustaman pisteen läpi 2-ulotteisen suorakulmaisen tason jakamiseksi.
Yllä oleva kd-puun ulostulo on rakennettu yksinkertaisella menetelmällä osiojohdon valitsemiseksi puun jokaisessa sisäisessä solmussa: –
Taso 0 : – Valitse osioviiva, joka on kohtisuorassa ensimmäiseen ulottuvuuteen ( X (tässä tapauksessa) ja kulkemalla kyseisen solmun edustaman pisteen läpi.
Taso 1 : – Valitse ositusrivi kohtisuorassa toiseen ulottuvuuteen (tässä tapauksessa Y ) ja kulkee pisteen, jota edustaa kyseinen solmu.
: : :
Taso k-1 : – Valitse osiointiviiva kohtisuorassa div id = ”870698b623”> k. ulottuvuus ja kulkee esitetyn pisteen läpi kyseisen solmun avulla. Taso k : – Valitse jakolinja, joka on kohtisuorassa ensimmäiseen ulottuvuuteen ( X tässä tapauksessa) ja kulkee kyseisen solmun edustaman pisteen läpi.
Joten periaatteessa kullakin tasolla vaihdetaan X- ja Y-ulottuvuuksien välillä jotta voit valita osituslinjan kd-puun jokaiselle sisäiselle solmulle.
Tunnisteet, jotka näet kd-puun [2] jokaisen solmun vieressä, edustavat osituslinjan ulottuvuuden valintaa kyseisen tason solmuissa.
Let ” Näemme nyt, kuinka 2-ulotteinen kd-puu osaa 2-ulotteisen tason [3]:
Hieno, miten suoritan haun?
En sano, että ”jätän sen sinulle, mutta sinä” Minun on käytettävä joitain muita resursseja ymmärtääksesi ne kokonaan. Voin kuitenkin kertoa teille, että tämä kd-puun jakama välilyönti voi auttaa sinua löytämään lähimmän naapurin tiettyyn pisteeseen avaruudessa ilman tarvetta tutkia kaikkia osioita , mitä tarvitsemme, jotta voimme tehdä reaaliaikaisen raportoinnin Social Copille.
Kd-puiden lähimmän naapurialgoritmin ymmärtämiseksi tässä on hyvä resurssi: http://www.stanford.edu/class/cs106l/handouts/assignment-3-kdtree.pdf
Haluan nopeasti tutustua muihin kd-puiden muihin sovelluksiin, koska suurin osa kd-puiden taustasta on jo käsitelty ensimmäisen sovelluksen keskustelussa.
2. Tietokantakyselyt, jotka sisältävät moniulotteisen hakunäppäimen
Kysely, joka pyytää kaikkia ikäryhmän (40, 50) työntekijöitä ja ansaitsee palkan välillä (15000, 20000) kuukaudessa, voidaan muuttaa geometriseksi ongelmaksi, jossa ikä piirretään x-akselilla ja palkka piirretään y-akselille [4]
[4] x-akseli tarkoittaa ikää työntekijä vuosina , ja y-akseli tarkoittaa kuukausipalkkaa tuhannessa rupiassa .
2-ulotteinen kd-puu yhdistetyssä hakemistossa (ikä, palkka) voi auttaa sinua etsimään tehokkaasti kaikkia työntekijöitä, jotka kuuluvat edellä kuvatulla kyselyllä määritettyyn suorakulmaiseen avaruusalueeseen.
3. n-body-ongelma [5]
Kuinka voimme tehokkaasti simuloida keskinäisen painovoiman alla liikkuvien esineiden kokoelman liikkeitä?
Naiivi menetelmä edellyttäisi kohteen välisen gravitaatiovoiman laskemista kaikista muista kohteista sen liikkeen simuloimiseksi gravitaatiovoiman alla. Lisäksi meidän olisi tehtävä se jokaiselle esineelle, joka vie O (n ^ 2) aikaa.
K-d-puiden avulla voimme kuitenkin jakaa tilan ja selvittää jokaiselle tilan osalle sen kokonaisvaikutus muuhun tilaan. Alla on algoritmin näennäinen koodi [6].
Laita objektit puuhun. Aloita puun alimmasta tasosta. Jokaiselle alueelle, joka on puun syvyydessä d : Jos lapsilla on lehtiä, laske vuorovaikutus suoraan Laske ” Moninapainen laajennus ”Muunna tämä vanhemman solmun paikalliseksi laajennukseksi ja välitä se. Siirry tasolle d-1. Kun saavutamme puun huipun, palaa takaisin alas puuhun, yhteenvetona paikalliset laajennukset.
4. Värien vähennys [7]
Mikä on älykäs tapa valita 256 väriä edustamaan värillistä kuvaa?
Naiivi menetelmä voisi olla useimmin käytettyjen värien poimiminen.
Tehokkaampi menetelmä voisi kuitenkin edustaa värejä niiden RGB -arvot ja muodostetaan kolmiulotteinen kd-puu jakamaan kuvan kaikki värit sisältävä tila. K-d-puun rakentaminen loppuisi, kun lehtisolmujen lukumäärä olisi yhtä suuri kuin 256. Kunkin 256 osion RGB-arvon keskiarvoa voitaisiin sitten käyttää 256 väripaletin saamiseksi täysvärikuvalle.
Viitteet: [1], [2], [3]: http://en.wikipedia.org/wiki/Kd-tree [4]: Luokittelu lähimpien naapureiden avulla [5], [6], [7] : kD-puut