Zuordnen eine Reihe von 3D-Punkten auf einem anderen Satz mit minimaler Summe der Entfernungen

Question

sind zwei Sätze von dreidimensionalen Punkten gegeben, einer Quelle und einem Zielsatz. Die Anzahl der Punkte auf jedem Satz beliebig ist (kann Null sein). Die Aufgabe ist, eine oder keine Quelle Punkt zu jedem Zielpunkt zuweisen, so dass die Summe aller Abstände minimal ist. Wenn es mehr Quelle als Zielpunkte sind, sind die zusätzlichen Punkte ignoriert werden.

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

Ich habe Interesse an beiden Annäherungen und exakten Lösungen.

Edit: Haha, ja, ich nehme an, es Hausaufgaben klingt wie. Eigentlich ist es nicht. Ich schreibe ein Programm, das Positionen einer großen Anzahl von Autos empfängt und ich versuche, sie zu ihren jeweiligen Park Zellen abzubilden. :)

Answer 1

Aus der Spitze von meinem Kopf, räumliche Art, gefolgt von simulierten Glühen.

Raster der Raum & sortieren Sie die Sätze in die Raumzellen.

Lösen Sie das O (NM) Problem in jeder Zelle, dann innerhalb der Zelle zur Umgebung und so weiter, eine Probeanpassung zu erhalten.

Schließlich viele Zyklen des simulierten Glühen ausgeführt, in dem Sie zufällig Matches ändern, um die in der Nähe Raum zu erkunden.

Dies ist Heuristik, Ihnen eine gute Antwort bekommen, wenn auch nicht unbedingt die besten, und es sollte ziemlich effizient sein aufgrund der anfänglichen Gitter sortieren.

Answer 2

Eine Möglichkeit, dieses Problem nähern könnte, ist zu behandeln ist wie die klassische Zuordnungsproblem: 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 ist, können Sie Gewichte neu definieren beispiel sein.

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

wo bigNumber ist größer als Ihre längste Strecke.

Natürlich am Ende mit einem zweiteiligen Graphen auf. Dann nutzen Sie eine der Standard-Algorithmen für maximale gewichtete bipartiter Anpassung (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 ) diese Weise werden Sie Ende- up mit einem O (NM max (N, M)) Algorithmen, wobei N und M Größen Ihrer Punktmengen sind.

Answer 3

Obwohl ich nicht wirklich eine Antwort auf Ihre Frage habe, kann ich in folgenden Themen vorschlägt, Blick. (Ich weiß sehr wenig darüber, aber begegnet er zuvor auf Stack-Überlauf).

• Nearest Neighbor Suche
• k d-Baum

Hope, das hilft ein wenig.