Beste svaret
Forskjellen mellom graf og tredatastruktur:
Graf
- I grafen kan det være mer enn en bane, dvs. at grafen kan ha en- eller toveis stier mellom noder.
- I grafen er det ikke noe slikt begrep root node.
- Graf kan ha sløyfer, kretser så vel som kan ha selvsløyfer.
- I graf er det ikke noe slikt foreldrebarnsforhold.
- Grafer er mer komplekse i forhold til trær, da det kan ha sykluser, sløyfer osv.
- Grafen krysses av DFS : Dybde første søk og i BFS : Algoritme for bredde første søk.
- Grafen kan være syklisk eller syklisk.
- Det er hovedsakelig to typer grafer: Direkte og ikke-dirigerte grafer.
- Grafapp lisenser: Farging av kart, algoritmer, Graffarging, jobbplanlegging etc.
- I graf, nr. av kantene avhenger av grafen.
- Grafen er en nettverksmodell.
Trær
- Treet er en spesiell form for graf, dvs. minimalt tilkoblet graf og har bare en bane mellom to toppunkt.
- Treet er et spesielt tilfelle av graf uten sløyfer, ingen kretser og ingen selvløkker.
- I treet er det nøyaktig en rot node og alle barn har bare en forelder.
- I trær er det foreldrebarnsforhold slik at flyt kan være der med retning topp til bunn eller omvendt.
- Trær er mindre komplekse enn grafer uten å ha sykluser, ingen selvløkker og fremdeles koblet sammen.
- Traversering av tre er en slags spesiell tilfelle av traversal av grafen. Treet krysses i Forhåndsbestilling , Bestilling og Etterbestilling (alle tre i DFS eller i BFS algoritme)
- Trær kommer i kategorien DAG: Directed Acyclic Graphs er en slags rettet graf som ikke har noen sykluser.
- Ulike typer trær er: Binært tre , Binært søketre, AVL-tre, dynger.
- Treapplikasjoner : sortering og søking som Tree Traversal & Binary Search.
- Treet har alltid n-1 kanter.
- Tree er en hierarkisk modell.
Svar
Så, kd-trær, ved første blikk, kan se ut til å være mer teoretiske enn praktiske. Men det er ikke tilfelle.
kd trær inneholder en rekke viktige applikasjoner, hvorav noen inkluderer:
1 Nærmeste nabo-søk
La oss si at du har tenkt å bygge en Social Cop på smarttelefonen din. Social Cop hjelper folk med å rapportere forbrytelser til nærmeste politistasjon i sanntid.
Så hva ser ut til å være et problem her?
Ja, du gjettet riktig. Vi må søke etter politistasjonen nærmest kriminalitetsstedet før vi prøver å rapportere noe.
Hvordan kunne vi gjøre det raskt ?
Ser ut som k-d-trær kan hjelpe deg med å finne nærmeste nabo til et punkt på et todimensjonalt kart over byen din. Alt du trenger å gjøre er å konstruere et todimensjonalt kd-tre fra plasseringene til alle politistasjonene i byen din, og deretter spørre kd-treet for å finne nærmeste politistasjon til et gitt sted i byen.
Ok, jeg får hva de kan gjøre. Men hvordan gjør de det?
Hvis du allerede vet hvordan binære søketrær fungerer, forstår du hvordan kd-trær fungerer ikke være noe nytt. k-d trær hjelper til med å partisjonere plass, akkurat som binære søketrær hjelper til med å partisjonere ekte linje . k-d trær deler rekursivt en region av rommet, og skaper en binær rompartisjon på hvert nivå av treet.
Slik ser et tredimensjonalt område av rommet delt ut av et tredimensjonalt kd-tre ut [1]:
Et tredimensjonalt kd-tre. Den første delingen (rød) kutter rotcellen (hvit) i to underceller, som hver blir delt (grønn) i to underceller. Til slutt er hver av disse fire delt (blå) i to underceller. Siden det ikke er mer splitting, blir de åtte siste kalt bladceller.
Og hvordan er treet konstruert?
Til å begynne med har du et sett med punkter i et k-dimensjonalt rom.La oss gi oss et eksempel på et todimensjonalt kd-tre:
Inngang: (2,3), (5,4), (9,6), (4,7), (8, 1), (7,2)
Utgang: Et todimensjonalt kd-tre [2]:
I tilfelle binære søketrær er den binære partisjonen til den virkelige linjen ved hver interne node representert med et punkt på den virkelige linjen. På samme måte, i tilfelle av et 2-dimensjonalt kd-tre, blir den binære partisjonen til det 2-dimensjonale kartesiske planet ved hver interne node representert med et linje i flyet.
Så i tilfelle av binære søketrær, tjener punktet representert av den interne noden som punktet som brukes til å dele den virkelige linjen. Hvordan velger vi en partisjoneringslinje i tilfelle 2-dimensjonale kd-trær?
I hovedsak , kan du velge hvilken som helst linje som går gjennom punktet representert av den interne noden å dele det todimensjonale kartesiske planet.
Kd-treutdataene ovenfor er konstruert ved hjelp av en enkel metode for å velge partisjoneringslinjen ved hver interne node i treet: –
Nivå 0 : – Velg partisjonslinjen vinkelrett på første dimensjon ( X i dette tilfellet) og passerer gjennom punktet representert av den aktuelle noden.
Nivå 1 : – Velg partisjoneringslinjen vinkelrett på andre dimensjon ( Y i dette tilfellet) og passerer gjennom punktet representert av den aktuelle noden.
: : :
Nivå k-1 : – Velg partisjoneringslinjen vinkelrett på kth dimensjon og passerer gjennom punktet representert av den aktuelle noden. Nivå k : – Velg partisjonslinjen vinkelrett på første dimensjon ( X i dette tilfellet) og passerer gjennom punktet representert av den aktuelle noden.
Så i utgangspunktet veksler vi på hvert nivå mellom X- og Y-dimensjonene for å velge en partisjoneringslinje ved hver interne node i kd-treet.
Etikettene du ser ved siden av hver av nodene i kd-treet [2] representerer valget av dimensjonen for partisjoneringslinjen på nodene på det nivået.
La » s se nå hvordan vårt 2-dimensjonale kd-tre partisjonerer det 2-dimensjonale planet [3]:
Greit, hvordan utfører jeg søket?
Jeg vil ikke si at jeg la det være opp til deg, men du » Jeg må ta hjelp av noen andre ressurser for å forstå det helt. Jeg kan imidlertid fortelle deg at denne rompartisjoneringen av et kd-tre kan hjelpe deg med å finne nærmeste nabo til et bestemt punkt i rommet uten behov for å utforske alle partisjonene som er det vi trengte, å gjøre sanntidsrapportering for Social Cop.
For å forstå den nærmeste naboalgoritmen på kd-trær, er det en god ressurs: http://www.stanford.edu/class/cs106l/handouts/assignment-3-kdtree.pdf
La meg raskt gå gjennom noen av de andre applikasjonene til kd-trær, da det meste av bakgrunnen til kd-trær allerede har blitt dekket i diskusjonen av den første applikasjonen.
2. Databasespørsmål som involverer en flerdimensjonal søkenøkkel
Et spørsmål som ber om alle ansatte i aldersgruppen (40, 50) og som tjener lønn i størrelsesorden (15000, 20000) per måned, kan forvandles til et geometrisk problem der alderen er tegnet langs x-aksen og lønnen er tegnet langs y-aksen [4]
[4] X-aksen betegner alderen til den ansatte i år , og y-aksen betegner månedslønnen i tusen rupees .
Et todimensjonalt kd-tre på den sammensatte indeksen til (alder, lønn) kan hjelpe deg effektivt å søke etter alle ansatte som faller i det rektangulære området av rommet, definert av spørringen beskrevet ovenfor.
3. n-kroppsproblem [5]
Hvordan kan vi effektivt simulere bevegelsene til en samling objekter som beveger seg under gjensidig gravitasjonsattraksjon?
Den naive metoden vil innebære å beregne gravitasjonskraften mellom et objekt på grunn av alle andre objekter for å simulere bevegelsen under tyngdekraften. Videre må vi gjøre det for hvert objekt som tar O (n ^ 2) tid.
Ved å bruke k-d-trær kan vi imidlertid dele rommet og for hver underavdeling av rommet finne ut den totale effekten på resten av rommet. Nedenfor er algoritmens pseudokode [6].
Sett gjenstandene i et tre. Start på det nederste nivået av treet. For alle regioner på en dybde d i treet: Hvis noen barn er blader, så beregn interaksjonen direkte. Beregn » Multipole-utvidelse «Konverter dette til en lokal utvidelse for foreldrenoden og gi den videre. Gå videre til nivå d-1. Når vi når toppen av treet, kan du gå tilbake nedover treet og oppsummere de lokale utvidelsene.
4. Fargereduksjon [7]
Hva er en intelligent måte å velge 256 farger for å representere et fullfargebilde?
Den naive metoden kan være å plukke opp fargene som brukes ofte.
En mer effektiv metode kan imidlertid representere farger når det gjelder RGB verdier og konstruere et tredimensjonalt kd-tre for å dele opp rommet som inneholder alle fargene på bildet. Konstruksjonen av k-d-treet ville stoppe når tellingen av bladnodene blir lik 256. Gjennomsnittet av RGB-verdien til hver av de 256 partisjonene kan da brukes til å få en 256 fargepalett for fullfargebildet.
Referanser: [1], [2], [3]: http://en.wikipedia.org/wiki/Kd-tree [4]: Klassifisering ved hjelp av nærmeste naboer [5], [6], [7] : kD Trees