Bedste svar
Forskel mellem graf og treddatastruktur:
Graf
- I grafen kan der være mere end en sti, dvs. grafen kan have envejs- eller tovejsstier mellem noder.
- I grafen er der ikke et sådant begreb rod -knude.
- Graf kan have sløjfer, kredsløb såvel som kan have selvsløjfer.
- I graf er der ikke sådan forældrebarnsforhold.
- Grafer er mere komplekse sammenlignet med træer, da det kan have cyklusser, sløjfer osv.
- Grafen krydses af DFS : Dybde første søgning og i BFS : Algoritme til første søgning i bredde.
- Grafen kan være cyklisk eller cyklisk.
- Der er hovedsageligt to typer grafer: Direkte og ikke-dirigerede grafer.
- Grafik-app licenser: Farvning af kort, algoritmer, Graffarvning, jobplanlægning osv.
- I graf, nr. af kanter afhænger af grafen.
- Grafen er en netværksmodel.
Træer
- Træ er en speciel form for graf, dvs. minimalt forbundet graf og har kun en sti mellem to to hjørner.
- Træ er et specielt tilfælde af graf, der ikke har nogen sløjfer, ingen kredsløb og ingen selvsløjfer.
- I træet er der nøjagtigt en rod node og hver barn har kun en forælder.
- I træer er der forældre-barn-forhold, så flow kan være der med retning top til bund eller omvendt.
- Træer er mindre komplekse end grafer som ingen cyklusser, ingen selvløkker og stadig forbundet.
- Traversering af træ er en slags specielt tilfælde af traversal af grafen. Træ krydses i Forudbestilling , Forudbestilling og Efterbestilling (alle tre i DFS eller i BFS algoritme)
- Træer kommer i kategorien DAG: Directed Acyclic Graphs er en slags rettet graf, der ikke har nogen cyklusser.
- Forskellige typer træer er: Binært træ , Binært søgetræ, AVL-træ, dynger.
- Træapplikationer : sortering og søgning som Tree Traversal & Binary Search.
- Tree har altid n-1 kanter.
- Tree er en hierarkisk model.
Svar
Så ved det første blik kan kd-træer synes at være mere teoretiske end praktiske. Men det er virkelig ikke tilfældet.
kd træer indeholder en række vigtige applikationer, hvoraf nogle inkluderer:
1 Nærmeste nabo-søgning
Lad os sige, at du har til hensigt at opbygge en Social politi på din smartphone. Social Cop hjælper folk med at rapportere forbrydelser til nærmeste politistation i realtid.
Så hvad synes der at være et problem her?
Ja, du gættede det rigtigt. Vi er nødt til at søge efter politistationen nærmest forbrydelsesstedet, inden vi prøver at rapportere noget.
Hvordan kunne vi gøre det hurtigt ?
Synes k-d træer kan hjælpe dig med at finde den nærmeste nabo til et punkt på et todimensionelt kort over din by. Alt hvad du skal gøre er at konstruere et 2-dimensionelt kd-træ fra placeringen af alle politistationer i din by og derefter forespørge på kd-træet for at finde den nærmeste politistation til en given placering i byen.
Okay, jeg får hvad de kan gøre. Men hvordan gør de det?
Hvis du allerede ved, hvordan binære søgetræer fungerer, forstå hvordan kd træer fungerer ikke være noget nyt. k-d træer hjælper med at opdele plads, ligesom binære søgetræer hjælper med at opdele reelle linje . k-d træer rekursivt partitionerer en region af rummet og skaber en binær rumpartition på hvert niveau af træet.
Sådan ser et tredimensionelt område af rummet opdelt ud af et 3-dimensionelt kd-træ ud [1]:
Et tredimensionelt kd-træ. Den første opdeling (rød) skærer rodcellen (hvid) i to underceller, hvoraf hver derefter opdeles (grøn) i to underceller. Endelig er hver af disse fire opdelt (blå) i to underceller. Da der ikke er mere opdeling, kaldes de sidste otte bladceller.
Og hvordan konstrueres træet?
Til at begynde med har du et sæt punkter i et k-dimensionelt rum.Lad os give os et eksempel på et 2-dimensionelt kd-træ:
Input: (2,3), (5,4), (9,6), (4,7), (8, 1), (7,2)
Output: Et 2-dimensionelt kd-træ [2]:
I tilfælde af binære søgetræer er den binære partition af den reelle linje ved hver intern node repræsenteret af et punkt på den rigtige linje. Tilsvarende, i tilfælde af et 2-dimensionelt kd-træ, er den binære partition af det 2-dimensionelle kartesiske plan ved hver intern node repræsenteret af et linje i flyet.
Så i tilfælde af binære søgetræer fungerer det punkt, der er repræsenteret af den interne knude, som det punkt, der bruges til at opdele den reelle linje. Hvordan vælger vi en partitioneringslinie i tilfælde af 2-dimensionelle kd-træer?
I det væsentlige , kunne du vælge en hvilken som helst linje, der passerer gennem det punkt, der er repræsenteret af den interne node at opdele det 2-dimensionelle kartesiske plan.
Kd-træudgangen ovenfor er konstrueret ved hjælp af en enkel metode til at vælge partitioneringslinjen ved hver interne node i træet: –
Niveau 0 : – Vælg partitioneringslinjen vinkelret på første dimension ( X i dette tilfælde) og passerer gennem det punkt, der er repræsenteret af den pågældende node.
Niveau 1 : – Vælg partitioneringslinjen vinkelret på anden dimension ( Y i dette tilfælde) og passerer gennem det punkt, der er repræsenteret af den pågældende knude.
: : :
Niveau k-1 : – Vælg partitioneringslinjen vinkelret på kth dimension og passerer gennem det repræsenterede punkt af den pågældende knude. Niveau k : – Vælg partitioneringslinjen vinkelret på første dimension ( X i dette tilfælde) og passerer gennem det punkt, der er repræsenteret af den pågældende node.
Så dybest set skifter vi på hvert niveau mellem X- og Y-dimensionerne for at vælge en partitioneringslinie ved hver interne node i kd-træet.
De etiketter, du ser ved siden af hver af knudepunkterne i kd-træet [2], repræsenterer valget af dimensionen for partitioneringslinjen på noderne på det niveau.
Lad ” s se nu, hvordan vores 2-dimensionelle kd-træ skiller det 2-dimensionelle plan [3]:
Fint, hvordan udfører jeg søgningen?
Jeg vil ikke sige, at jeg “overlader det til dig, men du” Jeg bliver nødt til at tage hjælp af nogle andre ressourcer for at forstå det fuldstændigt. Jeg kan dog fortælle dig, at denne rumpartitionering med et kd-træ kan hjælpe dig med at finde den nærmeste nabo til et bestemt punkt i rummet uden behov for at udforske alle partitioner , som vi havde brug for, at foretage realtids rapportering til Social Cop.
For at forstå den nærmeste naboalgoritme på kd-træer er her en god ressource: http://www.stanford.edu/class/cs106l/handouts/assignment-3-kdtree.pdf
Lad mig hurtigt gå igennem nogle af de andre applikationer af kd træer, da det meste af baggrunden for kd træer allerede er blevet dækket i diskussionen af den første applikation.
2. Databaseforespørgsler, der involverer en flerdimensionel søgetast
En forespørgsel, der beder om alle medarbejdere i aldersgruppen (40, 50) og tjener en løn i intervallet (15000, 20000) pr. Måned, kan omdannes til et geometrisk problem, hvor alderen er tegnet langs x-aksen og lønnen er tegnet langs y-aksen [4]
[4] X-aksen angiver alderen på medarbejderen i år , og y-aksen angiver den månedlige løn i tusind rupees .
Et 2-dimensionelt kd-træ på det sammensatte indeks af (alder, løn) kan hjælpe dig med effektivt at søge efter alle medarbejdere, der falder i det rektangulære område af rummet defineret af forespørgslen beskrevet ovenfor.
3. n-kropsproblem [5]
Hvordan kan vi effektivt simulere bevægelserne for en samling objekter, der bevæger sig under gensidig gravationsattraktion?
Den naive metode ville involvere beregning af tyngdekraften mellem et objekt på grund af ethvert andet objekt for at simulere dets bevægelse under tyngdekraften. Desuden skulle vi gøre det for hvert objekt, der ville tage O (n ^ 2) tid.
Ved hjælp af k-d træer kan vi dog opdele rummet og for hver underinddeling af rummet finde ud af dets samlede effekt på resten af rummet. Nedenfor er algoritmens pseudokode [6].
Sæt objekterne i et træ. Start på det nederste niveau af træet. For hver region i dybden d i træet: Hvis nogen børn er blade, så beregn interaktionen direkte Beregn ” Multipole-udvidelse “Konverter dette til en lokal udvidelse til den overordnede node og videresend den. Gå videre til niveau d-1. Når vi når toppen af træet, skal du vende tilbage ned ad træet og opsummere de lokale udvidelser.
4. Farvereduktion [7]
Hvad er en intelligent måde at vælge 256 farver til at repræsentere et fuldfarvet billede?
Den naive metode kan være at samle de farver, der bruges oftest.
En mere effektiv metode kan dog repræsentere farver med hensyn til deres RGB værdier og konstruere et tredimensionelt kd-træ for at opdele rummet med alle billedets farver. Konstruktionen af k-d-træet ville stoppe, når antallet af bladknudepunkter bliver lig med 256. Gennemsnittet af RGB-værdien for hver af de 256 partitioner kunne derefter bruges til at få en 256 farvepalet til billedet i fuld farve.
Referencer: [1], [2], [3]: http://en.wikipedia.org/wiki/Kd-tree [4]: Klassificering ved hjælp af nærmeste naboer [5], [6], [7] : kD-træer