Zuordnung eines Satzes von 3D-Punkten zu einem anderen Satz mit einer minimalen Summe von Abständen

Question

Gegeben sind zwei Sätze von dreidimensionalen Punkten, eine Quelle und ein Zielsatz. Die Anzahl der Punkte in jedem Satz ist beliebig (kann Null sein). Die Aufgabe besteht darin, jedem Zielpunkt einen oder keinen Quellpunkt zuzuweisen, so dass die Summe aller Entfernungen minimal ist. Wenn es mehr Quell- als Zielpunkte gibt, sind die zusätzlichen Punkte zu ignorieren.

Es gibt eine Brute-Force-Lösung für dieses Problem, aber da die Anzahl der Punkte groß sein kann, ist es nicht machbar. Ich habe gehört, dass dieses Problem in 2D mit gleichen Größenordnungen einfach ist, aber leider sind diese Voraussetzungen hier nicht gegeben.

Ich interessiere mich für beide Annäherungen und genaue Lösungen.

Edit: Haha, ja, ich nehme an, es klingt wie Hausaufgaben. Eigentlich ist es nicht. Ich schreibe ein Programm, das Positionen von einer großen Anzahl von Autos erhält, und ich versuche, sie ihren jeweiligen Parkzellen zuzuordnen. :)

Answer 1

Aus der Spitze meines Kopfes, räumliche Sortierung gefolgt von simulierten Glühen.

Gitter den Raum & sortieren Sie die Sätze in räumliche Zellen.

Lösen Sie das O (NM) -Problem innerhalb jeder Zelle, dann innerhalb von Zellennachbarschaften und so weiter, um eine Testübereinstimmung zu erhalten.

Schließlich, viele Zyklen von simulierten Annealing, in denen Sie zufällig Übereinstimmungen ändern, um den nahe gelegenen Raum zu erkunden.

Dies ist Heuristik, erhalten Sie eine gute Antwort, obwohl nicht unbedingt die beste, und es sollte ziemlich effizient sein, aufgrund der ersten Raster sortieren.

Answer 2

Obwohl ich nicht wirklich eine Antwort auf Ihre Frage habe, kann ich vorschlagen, die folgenden Themen zu untersuchen. (Ich weiß sehr wenig darüber, aber begegnet er zuvor auf Stack-Überlauf.)

• Nearest Neighbour Search
• kd-tree

Hope this hilft ein wenig.

Answer 3

Eine Möglichkeit, dieses Problem nähern könnte, ist als die klassische Zuordnungsproblem zu behandeln ist: http://en.wikipedia.org/wiki/Assignment_problem

Sie behandeln die Punkte als die Knoten des Graphen, und die Gewichte der Kanten der Abstand zwischen den Punkten. Da die schnellsten Algorithmen gehen davon aus, dass Sie für maximale Übereinstimmung suchen (und nicht mindestens wie in Ihrem Fall), und dass die Gewichte nicht negativ sind, können Sie Gewichte neu zu definieren sein, zB:

weight(A, B) = bigNumber- distance(A,B) 

wo bigNumber größer ist als deine längste Entfernung.

Offensichtlich enden Sie mit einem bipartite Graphen. Dann verwenden Sie einen der Standardalgorithmen für den maximalen gewichteten zweiteiligen Abgleich (viele Ressourcen im Internet, zB http://valis.cs.uiuc.edu/~sariel/teach/courses/473/notes/27_matchings_notes.pdf oder Wikipedia für Überblick: http://en.wikipedia.org/wiki/Perfect_matching#Maximum_bipartite_matchings) Auf diese Weise werden Sie mit einem O (NM max (N, M)) - Algorithmus enden , wobei N und M die Größe Ihrer Punkte sind.