Finden Sie die kleinsten summierten Abstände, indem Sie Elemente eines Satzes eindeutig mit Elementen eines anderen Satzes koppeln

Als Eingabe habe ich zwei Punktmengen in R ^N , typischerweise für großes N, zum Beispiel N = 40. Angenommen, beide Mengen haben m Elemente:

S = s ₁ ... s _m

T = t ₁ ... t _m

Semantisch sind beide Mengen gleich, aber aufgrund von Rauschen (welcher Art auch immer) an den R ^ N-Punkten haben Elemente, die semantisch gleich sein sollten, immer noch einen Abstand größer als 0.

Was ich finden möchte, sind m Tupel (s _i , t _j ), so dass die Summe der Abstände (s _i , t _j ) minimiert wird und so dass s _k und t _k genau einmal in der Menge der Tupel für k = 1 auftreten ... m. Grundsätzlich müssen (i, j) als Türme auf einem Schachbrett gewählt werden, die sich nicht gegenseitig treffen können, während die summierten Entfernungen minimiert werden.

Mit anderen Worten, ich möchte eine Eins-zu-Eins-Karte zwischen S und T finden, die "eine Art Identitätskarte ist, aber robust gegen Rauschen". Wir gehen davon aus, dass das Abstandsmaß ein guter Hinweis darauf ist, wie ähnlich Elemente sind.

Grundsätzlich muss ich eine Permutation von 1 ... N finden, und daher denke ich, dass dieses Problem entweder NP-hart oder NP-vollständig ist, da es sich dem TSP ziemlich ähnlich anfühlt. Ich konnte das TSP-Problem hier jedoch nicht in eine Teilmenge meines Problems umschreiben.

Ist dieses Problem für großes N realistisch lösbar? Gibt es einen Namen für dieses Problem? Was wäre eine praktikable Lösung? Gibt es andere Kriterien, die besser sein könnten als die summierten Entfernungen?

Ich dachte an einen gierigen Ansatz, sei D eine Matrix der Entfernungen, d _ij = Entfernung (s _i , t _j ).

T = {}
while D is not empty:
    (i,j) = argmin-(i,j) dij
    append (i,j) to T
    set row i and column j to infinity.

Dies führt nicht zur optimalen Lösung, sondern findet eine Lösung. Wäre das meine beste Wahl? Sollte ich simuliertes Tempern verwenden oder ist es übertrieben?

PS: Aus meiner Sicht ist dies nur ein kleines Problem bei einem größeren ML-Problem, aber ich interessiere mich sehr für den CS-Hintergrund.

Dies ist das Problem, die maximale Übereinstimmung in einem gewichteten zweigliedrigen Graphen zu finden. Es gibt effiziente Algorithmen , die dieses Problem in Polynomzeit lösen.

$2m$$S$$T$$i,j$$s_i$$t_j$$-d(s_i,t_j)$$s_i$$t_j$

$(s_i,t_j)$

Hier ist eine schnelle probabilistische Methode, die für Sie funktionieren könnte.

1. Projizieren Sie Ihre Punkte auf eine zufällige Linie und lösen Sie das 1D-Übereinstimmungsproblem in dieser Linie.

2. Wiederholen Sie den Vorgang für eine Handvoll verschiedener zufälliger Zeilen, um eine Sammlung von Kandidatenübereinstimmungen zu erhalten.

3. Lassen Sie Ihre Kandidaten-Matchings Punkt für Punkt "abstimmen", um das "beste" Matching zu finden.