Beste antwoord
Verschil tussen grafiek en boomgegevensstructuur:
Grafiek
- In graph kan er meer dan één pad zijn, dwz de grafiek kan unidirectionele of bidirectionele paden tussen knooppunten hebben.
- In graph is er niet zon concept van root node.
- Graph kan zowel loops, circuits als self-loops hebben.
- In Graph is er geen ouder-kindrelatie.
- Grafieken zijn complexer in vergelijking met bomen omdat het cycli, lussen enz. kan hebben.
- Grafiek wordt doorlopen door DFS : Depth First Search en in BFS : algoritme voor Breadth First Search.
- De grafiek kan cyclisch of acyclisch zijn.
- Er zijn hoofdzakelijk twee soorten grafieken: gestuurde en niet-gerichte grafieken.
- Grafiek-app licenties: Inkleuren van kaarten, algoritmen, Grafiekkleuren, taakplanning enz.
- In Graph, nr. van randen is afhankelijk van de grafiek.
- Grafiek is een netwerkmodel.
Bomen
- Tree is een speciale vorm van een graaf, dat wil zeggen een minimaal verbonden graaf en met slechts één pad tussen twee hoekpunten.
- Tree is een speciaal geval van een graaf zonder lussen, geen circuits en geen self-loops.
- In de boom is er precies één root knooppunt en elk kind hebben maar één ouder.
- In bomen is er een ouder-kindrelatie, dus er kan stroom zijn met richting van boven naar beneden of vice versa.
- Bomen zijn minder complex dan grafieken omdat ze geen cycli hebben, geen self-loops en toch verbonden zijn.
- Tree traversal is een soort speciaal geval van traversal van de grafiek. Boom wordt doorkruist in Pre-order , In-order en Post-order (alle drie in DFS of in BFS algoritme)
- Bomen vallen in de categorie DAG: Directed Acyclic Graphs is een soort gerichte graaf die geen cycli heeft.
- Verschillende soorten bomen zijn: Binaire boom , Binaire zoekboom, AVL-boom, Heaps.
- Boom-applicaties : sorteren en zoeken zoals Tree Traversal & Binary Search.
- Tree heeft altijd n-1 randen.
- Tree is een hiërarchisch model.
Antwoord
Dus kd-bomen lijken op het eerste gezicht misschien meer theoretisch dan praktisch van aard. Maar dat is echt niet het geval.
kd-trees bevatten een verscheidenheid aan belangrijke applicaties, waaronder enkele:
1 . Naaste buur zoeken
Stel dat u van plan bent een Social Cop op uw smartphone. Social Cop helpt mensen misdaden in realtime bij het dichtstbijzijnde politiebureau te melden.
Dus wat lijkt hier een probleem te zijn?
Ja, je raadt het goed. We moeten zoeken naar het politiebureau dat het dichtst bij de plaats van de misdaad ligt voordat we proberen iets te melden.
Hoe konden we het doen snel ?
Het lijkt erop dat k-d trees u kunnen helpen bij het vinden van de dichtstbijzijnde buur tot een punt op een tweedimensionale kaart van uw stad. Het enige wat je hoeft te doen is een tweedimensionale kd-boom te bouwen op basis van de locaties van alle politiebureaus in je stad, en vervolgens de kd-boom te doorzoeken om het dichtstbijzijnde politiebureau te vinden voor een bepaalde locatie in de stad.
Oké, ik begrijp wat ze kunnen doen. Maar hoe doen ze het?
Als u al weet hoe binaire zoekbomen werken, zou u begrijpen hoe kd-bomen werken niets nieuws zijn. k-d trees helpen bij het partitioneren van ruimte net zoals binaire zoekbomen helpen bij het partitioneren van de echte regel . k-d-bomen verdelen recursief een gebied van ruimte, waardoor een binaire ruimteverdeling ontstaat op elk niveau van de boom.
Zo ziet een driedimensionaal gebied van ruimte verdeeld door een driedimensionale kd-boom eruit [1]:
Een driedimensionale kd-boom. De eerste splitsing (rood) snijdt de wortelcel (wit) in twee subcellen, die vervolgens elk worden gesplitst (groen) in twee subcellen. Ten slotte wordt elk van die vier opgesplitst (blauw) in twee subcellen. Aangezien er geen splitsing meer is, worden de laatste acht bladcellen genoemd.
En hoe wordt de boom geconstrueerd?
Om te beginnen heb je een reeks punten in een k-dimensionale ruimte.Laten we onszelf een voorbeeld geven van een tweedimensionale kd-boom:
Invoer: (2,3), (5,4), (9,6), (4,7), (8, 1), (7,2)
Uitvoer: een tweedimensionale kd-boom [2]:
In het geval van binaire zoekbomen, wordt de binaire partitie van de echte lijn op elk intern knooppunt weergegeven door een punt op de reële lijn. Evenzo wordt in het geval van een tweedimensionale kd-boom de binaire partitie van het tweedimensionale cartesische vlak op elk intern knooppunt weergegeven door een lijn in het vlak.
Dus, voor het geval dat van binaire zoekbomen, dient het punt dat wordt vertegenwoordigd door het interne knooppunt als het punt dat wordt gebruikt om de echte lijn te partitioneren. Hoe kiezen we een scheidingslijn in het geval van tweedimensionale kd-bomen?
In wezen , kunt u een willekeurige lijn kiezen die door het punt loopt dat wordt vertegenwoordigd door het interne knooppunt om het 2 dimensionale cartesische vlak te verdelen.
De uitvoer van de kd-boom hierboven is geconstrueerd met behulp van een eenvoudige methode voor het kiezen van de partitieregel op elk intern knooppunt van de boom: –
Niveau 0 : – Kies de partitielijn loodrecht op de eerste dimensie ( X in dit geval) en door het punt gaan dat wordt vertegenwoordigd door het betreffende knooppunt.
Niveau 1 : – Kies de partitieregel loodrecht op de tweede dimensie ( Y in dit geval) en door het punt dat wordt weergegeven door het betreffende knooppunt.
: : :
Niveau k-1 : – Kies de partitielijn loodrecht op de kde dimensie en gaat door het weergegeven punt door het betreffende knooppunt. Niveau k : – Kies de partitielijn loodrecht op de eerste dimensie ( X in dit geval) en door het punt gaan dat wordt vertegenwoordigd door het betreffende knooppunt.
Dus in feite wisselen we op elk niveau af tussen de X- en Y-dimensies om een partitielijn te kiezen op elk intern knooppunt van de kd-boom.
De labels die je ziet naast elk van de knooppunten van de kd-boom [2] vertegenwoordigen de keuze van de dimensie voor de partitielijn op de knooppunten op dat niveau.
Let ” s nu zien hoe onze tweedimensionale kd-boom het tweedimensionale vlak [3] verdeelt:
Prima, hoe voer ik de zoekopdracht uit?
Ik “zal niet zeggen dat ik” dat aan jou overlaat, maar aan jou ” Ik zal hulp nodig hebben van een aantal andere bronnen om het volledig te begrijpen. Ik kan je echter vertellen dat deze ruimte-indeling door een kd-structuur je kan helpen de dichtstbijzijnde buur te vinden naar een specifiek punt in de ruimte zonder de noodzaak om alle partities te verkennen, wat we nodig hadden, om realtime rapportage voor Social Cop te doen.
Om het algoritme van de dichtstbijzijnde buur op kd-bomen te begrijpen, is hier een goede bron: http://www.stanford.edu/class/cs106l/handouts/assignment-3-kdtree.pdf
Laat me je snel door enkele van de andere toepassingen van kd-bomen leiden, aangezien de meeste achtergrond van kd-bomen al is behandeld in de bespreking van de eerste toepassing.
2. Databasequerys met een multidimensionale zoeksleutel
Een vraag die alle werknemers in de leeftijdsgroep van (40, 50) vraagt en een salaris verdient in het bereik van (15.000, 20.000) per maand, kan worden omgezet in een geometrisch probleem waarbij de leeftijd wordt uitgezet langs de x-as en het salaris is uitgezet langs de y-as [4]
[4] De x-as geeft de leeftijd van de werknemer in jaar , en de y-as staat voor het maandsalaris in duizend roepies .
Een tweedimensionale kd-boom op de samengestelde index van (leeftijd, salaris) kan u helpen efficiënt te zoeken naar alle werknemers die in het rechthoekige gebied van de ruimte vallen dat wordt gedefinieerd door de hierboven beschreven zoekopdracht.
3. n-body Probleem [5]
Hoe kunnen we efficiënt de bewegingen simuleren van een verzameling objecten die bewegen onder wederzijdse zwaartekracht?
De naïeve methode zou het berekenen van de zwaartekracht tussen een object als gevolg van elk ander object inhouden om zijn beweging onder zwaartekracht te simuleren. Bovendien zouden we het voor elk object moeten doen, wat O (n ^ 2) tijd zou kosten.
Door k-d trees te gebruiken, kunnen we de ruimte echter verdelen en voor elke onderverdeling van de ruimte het totale effect op de rest van de ruimte bepalen. Hieronder staat de pseudocode [6] van het algoritme.
Zet de objecten in een boomstructuur. Begin op het onderste niveau van de boom, voor elke regio op een diepte d in de boom: als er bladeren zijn, berekent u de interactie rechtstreeks Bereken de ” Uitbreiding met meerdere polen “Zet dit om in een lokale uitbreiding voor het bovenliggende knooppunt en geef het door. Ga verder naar niveau d-1. Wanneer we de top van de boom bereiken, duik je terug in de boom en tel je de lokale uitbreidingen op.
4. Kleurreductie [7]
Wat is een intelligente manier om 256 kleuren te kiezen om een afbeelding in kleur weer te geven?
De naïeve methode zou kunnen zijn om de kleuren op te pikken die het meest worden gebruikt.
Een efficiëntere methode zou echter kleuren kunnen weergeven in termen van hun RGB -waarden en construeer een driedimensionale kd-boom om de ruimte met alle kleuren van de afbeelding te verdelen. De constructie van de k-d-boom zou stoppen wanneer het aantal bladknooppunten gelijk wordt aan 256. Het gemiddelde van de RGB-waarde van elk van de 256 partities zou dan kunnen worden gebruikt om een 256 kleurenpalet te krijgen voor het volledige kleurenbeeld.
Referenties: [1], [2], [3]: http://en.wikipedia.org/wiki/Kd-tree [4]: Classificatie met behulp van naaste buren [5], [6], [7] : kD Trees