Kürzeste Pfad- und Sortierpunkte in einem 2-dimensionalen Raum

Question

Angenommen, ich habe ein Objekt in einem 2-dimensionalen Raum und eine Menge von Punkten, die ich für das Objekt benötige. Punkte können jederzeit hinzugefügt, aber nicht entfernt werden.

Was mag ich in der Lage sein, den nächsten am nächsten Punkt zu bestimmen, wo mein Objekt ist in O (lg (n)) Zeit, dann gehen Sie zu ihm, dann bestimmen die nächste Nähe, etc ..

Eine einfache Prioritätswarteschlange funktioniert dafür nicht, da das Objekt seine Position ändert, sodass die Warteschlange bei jeder Bewegung neu angeordnet werden muss. Ich stellte mir vor, die Punkte irgendwie in eine BST zu sortieren, aber ich bin mir unsicher, wie ich nach (x, y) sortieren soll oder ob es überhaupt möglich ist.

Das fühlt sich an, als ob ich versuchen könnte zu lösen traveling salesman, ohne es zu merken, wenn ja, ich entschuldige mich haha.

Answer 1

Eine Option wäre, einen Raum-Partitionierungsbaum wie einen Quadtree oder K-D-Baum zu verwenden, um alle Punkte im Raum zu speichern. Diese Datenstrukturen unterstützen effizient (üblicherweise in der sublinearen Zeit) Abfragen der Form "Was sind die nächsten Punkte zum Punkt p?" Sie könnten dann Folgendes tun:

1. Erstellen Sie einen Raum Partitionierungsbaum für die Punkte im Raum.
2. Verwenden Sie den Baum, um den Punkt p zu finden, der Ihrem Startpunkt am nächsten ist.
3. Wiederholen Sie die folgenden Schritte:
   1. Gehen Sie zu Punkt p.
   2. Entfernen Sie p aus dem Baum.
   3. Stellen Sie p als den Punkt ein, der Ihrem aktuellen Standort am nächsten ist.

hoffe, das hilft!