finden Sie den nächsten Satz von Punkten auf einem anderen Satz

Question

I zwei Sätze haben, A und B mit N und M Punkte in R^n sind. Ich weiß, dass N < M immer.

Der Abstand zwischen zwei Punkten, P und Q , wird durch d ( P, Q ) bezeichnet. Da das Problem generisch ist, könnte dieser Abstand irgendeine Funktion sein (z. B. Euklidischer Abstand).

Ich mag die nächste Teilmenge von B zu A zu finden. Mathematisch würde ich sagen, dass ich die Teilmenge C von B mit Größe N mit dem minimalen globalen Abstand zu A finden möge. Der globale Abstand zwischen A und C wird durch

gegeben

D(A,C) = min([sum(d(P_i,Q_i),i=1,N) with P_i in A and Q_i in C* for C* in Permutations of C]) 

Ich habe über dieses Problem nachgedacht und ich habe einen Algorithmus, der ein lokales Optimum, aber nicht unbedingt die optimal: Finden

Schritt 1), um den nächstgelegenen Punkt jeder Punkt der A in B. Wenn es keine wiederholten Punkte gibt, habe ich die optimale Teilmenge gefunden und beende den Algorithmus. Wenn jedoch Punkte wiederholt werden, fahren Sie mit Schritt 2 fort.

Schritt 2) Vergleichen Sie ihre Abstände (natürlich vergleiche ich den Abstand zwischen Punkten mit dem nächsten Punkt). Der Punkt mit dem minimalen Abstand behält den zuvor gefundenen Punkt und die anderen ändern ihren gewünschten Punkt für den "nächsten" nächsten Punkt, der noch nicht für einen anderen Punkt ausgewählt wurde.

Schritt 3) Überprüfen Sie, ob alle Punkte unterschiedlich sind. Wenn sie sind, beende. Wenn nicht, gehe zurück zu Schritt 2.

Irgendeine Idee? Versuchen alle Kombinationen ist nicht eine gute (ich sollte berechnen M!/(MN)! Globale Abstände)

Answer 1

Wenn M = N, könnte dieses Problem als minimales Gewicht perfekte Übereinstimmung in einem zweiteiligen Graph oder formuliert werden, in Mit anderen Worten, ein Zuweisungsproblem. Eine bekannte Methode zur Lösung eines Zuordnungsproblems ist die Hungarian algorithm.

Um Ungarische Methode anwendbar im Fall N < M zu machen, könnte man Satz A mit (M-N) zusätzlichen Elementen (von denen jeden Null-Abstand zu allen Elementen der B) erstrecken.