Beste Antwort
Unterschied zwischen Diagramm- und Baumdatenstruktur:
Graph
- Im Diagramm kann es mehr als einen Pfad geben, dh das Diagramm kann unidirektionale oder bidirektionale Pfade zwischen Knoten haben.
- Im Diagramm gibt es kein solches Konzept von root -Knoten.
- Graph kann Schleifen, Schaltkreise sowie Selbstschleifen haben.
- In Graph gibt es keine solchen Eltern-Kind-Beziehung.
- Diagramme sind im Vergleich zu Bäumen komplexer, da sie Zyklen, Schleifen usw. enthalten können.
- Das Diagramm wird von DFS : Tiefensuche und in BFS : Algorithmus für die Breitensuche.
- Der Graph kann zyklisch oder azyklisch sein.
- Es gibt hauptsächlich zwei Arten von Diagrammen: gerichtete und ungerichtete Diagramme.
- Diagramm-App likationen: Färben von Karten, Algorithmen, Grafikfärbung, Auftragsplanung usw.
- In Grafik, Nr. Die Anzahl der Kanten hängt vom Diagramm ab.
- Das Diagramm ist ein Netzwerkmodell.
Bäume
- Baum ist eine spezielle Form eines Graphen, dh ein minimal verbundener Graph mit nur einem Pfad zwischen zwei beliebigen Eckpunkten.
- Baum ist ein Sonderfall eines Graphen ohne Schleifen, ohne Schaltkreise und ohne Selbstschleifen.
- Im Baum gibt es genau eine root Knoten und jedes Kind haben nur ein Elternteil.
- In Bäumen gibt es eine Eltern-Kind-Beziehung, sodass der Fluss mit der Richtung erfolgen kann von oben nach unten oder umgekehrt.
- Bäume sind weniger komplex als Diagramme, da sie keine Zyklen, keine Selbstschleifen und immer noch verbunden sind.
- Baumdurchquerung ist eine Art Sonderfall der Durchquerung des Graphen. Der Baum wird in Vorbestellung , In-Order und Nachbestellung (alle drei in DFS oder in BFS Algorithmus)
- Bäume fallen in die Kategorie DAG: Directed Acyclic Graphs ist eine Art gerichteter Graph ohne Zyklen.
- Verschiedene Baumarten sind: Binärbaum , Binärer Suchbaum, AVL-Baum, Heaps.
- Baumanwendungen : Sortieren und Suchen wie Tree Traversal & Binary Search.
- Tree hat immer n-1 Kanten.
- Tree ist ein hierarchisches Modell.
Antwort
Auf den ersten Blick scheinen kd-Bäume eher theoretischer als praktischer Natur zu sein. Dies ist jedoch wirklich nicht der Fall.
kd-Bäume enthalten eine Vielzahl wichtiger Anwendungen, von denen einige Folgendes umfassen:
1 Suche in der Nähe des Nachbarn
Nehmen wir an, Sie beabsichtigen, eine Social Cop in Ihrem Smartphone. Social Cop hilft Menschen, Verbrechen in Echtzeit der nächsten Polizeistation zu melden.
Was scheint hier also ein Problem zu sein?
Ja, Sie haben es richtig erraten. Wir müssen nach der Polizeistation suchen, die dem Tatort am nächsten liegt, bevor wir versuchen, etwas zu melden.
Wie können wir das tun? schnell ?
K-d-Bäume können Ihnen dabei helfen, den nächsten Nachbarn zu einem Punkt auf einer zweidimensionalen Karte Ihrer Stadt zu finden. Alles, was Sie tun müssen, ist, aus den Standorten aller Polizeistationen in Ihrer Stadt einen zweidimensionalen kd-Baum zu erstellen und dann den kd-Baum abzufragen, um die nächstgelegene Polizeistation zu einem bestimmten Ort in der Stadt zu finden.
Okay, ich verstehe, was sie tun können. Aber wie machen sie das?
Wenn Sie bereits wissen, wie binäre Suchbäume funktionieren, verstehen Sie, wie kd-Bäume funktionieren würden sei nichts Neues. k-d-Bäume helfen bei der Partitionierung des Speicherplatzes ebenso wie binäre Suchbäume bei der Partitionierung der -Oberlinie . k-d-Bäume partitionieren rekursiv einen Raumbereich und erstellen auf jeder Ebene des Baums eine binäre Raumpartition.
So sieht ein dreidimensionaler Raumbereich aus, der durch einen dreidimensionalen kd-Baum unterteilt ist [1]:
Ein dreidimensionaler kd-Baum. Die erste Aufteilung (rot) schneidet die Wurzelzelle (weiß) in zwei Unterzellen, von denen jede dann in zwei Unterzellen aufgeteilt wird (grün). Schließlich wird jede dieser vier in zwei Unterzellen aufgeteilt (blau). Da keine Aufteilung mehr erfolgt, werden die letzten acht als Blattzellen bezeichnet.
Und wie ist der Baum aufgebaut?
Zunächst haben Sie eine Reihe von Punkten in einem k-dimensionalen Raum.Geben wir uns ein Beispiel für einen zweidimensionalen kd-Baum:
Eingabe: (2,3), (5,4), (9,6), (4,7), (8, 1), (7,2)
Ausgabe: Ein zweidimensionaler kd-Baum [2]:
Bei binären Suchbäumen wird die binäre Partition der realen Linie an jedem internen Knoten durch einen Punkt
Also für den Fall Bei binären Suchbäumen dient der durch den internen Knoten dargestellte Punkt als Punkt, der zum Partitionieren der realen Linie verwendet wird. Wie wählen wir eine Partitionierungslinie bei zweidimensionalen kd-Bäumen aus?
Im Wesentlichen Sie können eine beliebige Linie auswählen, die durch den vom internen Knoten dargestellten Punkt verläuft die zweidimensionale kartesische Ebene zu unterteilen.
Die obige kd-Baumausgabe wurde mit einer einfachen Methode zum Auswählen der Partitionierungslinie an jedem internen Knoten des Baums erstellt: –
Ebene 0 : – Wählen Sie die Trennlinie senkrecht zur erste Dimension ( X in diesem Fall) und Durchlaufen des durch den betreffenden Knoten dargestellten Punkts.
Ebene 1 : – Wählen Sie die Trennlinie aus senkrecht zur zweiten Dimension (in diesem Fall Y ) und durch den durch dargestellten Punkt der betreffende Knoten.
: : :
Ebene k-1 : – Wählen Sie die Trennlinie senkrecht zum k-te Dimension und Durchlaufen des dargestellten Punktes durch den betreffenden Knoten. Ebene k : – Wählen Sie die Trennlinie senkrecht zur erste Dimension ( X in diesem Fall) und Durchlaufen des durch den betreffenden Knoten dargestellten Punkts.
Grundsätzlich wechseln wir auf jeder Ebene zwischen den X- und Y-Dimensionen um an jedem internen Knoten des kd-Baums eine Partitionierungslinie auszuwählen.
Die Beschriftungen, die Sie neben jedem der Knoten des kd-Baums [2] sehen, stellen die Wahl der Dimension für die Trennlinie an den Knoten auf dieser Ebene dar.
Lassen Sie “ Sehen Sie nun, wie unser zweidimensionaler kd-Baum die zweidimensionale Ebene [3] partitioniert:
Gut, wie führe ich die Suche durch?
Ich werde nicht sagen, dass ich das Ihnen überlassen werde, sondern Ihnen. Ich muss einige andere Ressourcen in Anspruch nehmen, um sie vollständig zu verstehen. Ich kann Ihnen jedoch sagen, dass diese Raumaufteilung durch einen kd-Baum Ihnen helfen kann, den nächsten Nachbarn zu einem bestimmten Punkt im Raum zu finden. ohne alle Partitionen untersuchen zu müssen , was wir brauchten, um Echtzeitberichte für Social Cop zu erstellen.
Um den Algorithmus für den nächsten Nachbarn auf kd-Bäumen zu verstehen, ist hier eine gute Ressource: http://www.stanford.edu/class/cs106l/handouts/assignment-3-kdtree.pdf
Lassen Sie mich kurz auf einige andere Anwendungen von kd-Bäumen eingehen, da der größte Teil des Hintergrunds von kd-Bäumen bereits in der Diskussion der ersten Anwendung behandelt wurde.
2. Datenbankabfragen mit einem mehrdimensionalen Suchschlüssel
Eine Abfrage, bei der alle Mitarbeiter in der Altersgruppe (40, 50) gefragt werden und ein Gehalt im Bereich von (15000, 20000) pro Monat verdient wird, kann in ein geometrisches Problem umgewandelt werden, bei dem das Alter entlang der x-Achse aufgetragen wird und das Gehalt ist entlang der y-Achse aufgetragen [4]
[4] Die x-Achse bezeichnet das Alter von Der Mitarbeiter in Jahren und die y-Achse geben das monatliche Gehalt in Tausend Rupien an.
Ein zweidimensionaler kd-Baum im zusammengesetzten Index von (Alter, Gehalt) Mit können Sie effizient nach allen Mitarbeitern suchen, die in den durch die oben beschriebene Abfrage definierten rechteckigen Raumbereich fallen.
3. n-Körper-Problem [5]
Wie können wir die Bewegungen einer Sammlung von Objekten, die sich unter gegenseitiger Anziehungskraft bewegen, effizient simulieren?
Die naive Methode würde die Berechnung der Gravitationskraft zwischen einem Objekt aufgrund jedes anderen Objekts beinhalten, um seine Bewegung unter Gravitationsanziehung zu simulieren. Außerdem müssten wir dies für jedes Objekt tun, das O (n ^ 2) Zeit benötigt.
Mit k-d-Bäumen können wir jedoch den Raum unterteilen und für jede Unterteilung des Raums die Gesamtwirkung auf den Rest des Raums ermitteln. Unten finden Sie den Pseudocode [6] des Algorithmus.
Fügen Sie die Objekte in einen Baum ein. Beginnen Sie auf der untersten Ebene des Baums. Für jede Region in einer Tiefe d im Baum: Wenn Kinder Blätter sind, berechnen Sie die Interaktion direkt. Multipol-Erweiterung „Konvertieren Sie diese in eine lokale Erweiterung für den übergeordneten Knoten und übergeben Sie sie. Fahren Sie mit Stufe d-1 fort. Wenn wir die Spitze des Baumes erreichen, kehren Sie den Baum zurück und summieren die lokalen Erweiterungen.
4. Farbreduzierung [7]
Was ist eine intelligente Möglichkeit, 256 Farben auszuwählen, um ein Vollfarbbild darzustellen?
Die naive Methode könnte darin bestehen, die am häufigsten verwendeten Farben aufzunehmen.
Eine effizientere Methode könnte jedoch Farben in Bezug auf ihre RGB -Werte und konstruieren Sie einen dreidimensionalen kd-Baum, um den Raum zu teilen, der alle Farben des Bildes enthält. Die Konstruktion des k-d-Baums würde aufhören, wenn die Anzahl der Blattknoten gleich 256 wird. Der Durchschnitt des RGB-Werts jeder der 256 Partitionen könnte dann verwendet werden, um eine 256-Farben-Palette für das Vollfarbbild zu erhalten.
Referenzen: [1], [2], [3]: http://en.wikipedia.org/wiki/Kd-tree [4]: Klassifizierung unter Verwendung der nächsten Nachbarn [5], [6], [7] : kD-Bäume