Trouvez les plus petites distances additionnées en associant de manière unique des éléments d'un ensemble à des éléments d'un autre ensemble

En entrée, j'ai deux ensembles de points dans R ^N , généralement pour un grand N, par exemple N = 40. Supposons que les deux ensembles ont m éléments:

S = s ₁ ... s _m

T = t ₁ ... t _m

Sémantiquement, les deux ensembles sont égaux, mais en raison du bruit (de quelque nature que ce soit) sur les points R ^ N, les éléments qui devraient être sémantiquement les mêmes ont toujours une distance supérieure à 0.

Ce que je veux trouver, c'est m tuples (s _i , t _j ) tels que la somme des distances (s _i , t _j ) soit minimisée et tels que s _k et t _k se produisent exactement une fois dans l'ensemble de tuples pour k = 1 ... m. Fondamentalement (i, j) doivent être choisis comme des tours sur un échiquier qui ne peuvent pas se heurter tout en minimisant les distances totalisées.

En d'autres termes, je veux trouver une carte un à un entre S et T qui "est en quelque sorte une carte d'identité, mais robuste au bruit". Nous supposons que la mesure de distance est une bonne indication de la similitude des éléments.

Fondamentalement, j'ai besoin de trouver une permutation de 1 ... N, et donc je pense que ce problème est soit NP-dur ou NP-complet, car il "se sent" assez similaire au TSP; cependant, je n'ai pas pu réécrire le problème TSP dans un sous-ensemble de mon problème ici.

Ce problème peut-il être résolu de manière réaliste pour un grand N? Y a-t-il un nom pour ce problème? Quelle serait une solution réalisable? Y a-t-il un autre critère qui pourrait être meilleur que les distances additionnées?

J'ai pensé à une approche gourmande, soit D une matrice des distances, d _ij = distance (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.

Cela n'aboutit pas à la solution optimale, mais trouve une solution. Serait-ce mon meilleur pari? Dois-je utiliser un recuit simulé ou est-ce exagéré?

PS: de mon point de vue, ce n'est qu'un problème mineur dans un problème ML plus important, cependant, je suis très intéressé par l'arrière-plan CS de celui-ci.

C'est le problème de trouver la correspondance maximale dans un graphe biparti pondéré. Il existe des algorithmes efficaces qui résolvent ce problème en temps polynomial.

Fondamentalement, vous avez un graphique bipartite complet avec $2m$ sommets. $S$ forme un ensemble de sommets; $T$forme l'autre ensemble de sommets. Pour chaque$i,j$, créez un bord à partir de $s_i$ à $t_j$ dont le poids est égal à $-d(s_i,t_j)$, la négation de la distance entre $s_i$ et $t_j$.

Maintenant, vous voulez trouver une correspondance dont le poids est aussi grand que possible. Cela correspond à un ensemble de paires$(s_i,t_j)$dont la distance totale est la plus petite possible. À partir de là, vous pouvez utiliser les algorithmes existants sur ce graphique pour trouver la correspondance de poids maximum.

Voici une méthode probabiliste rapide qui pourrait vous convenir.

1. Projetez vos points sur une ligne aléatoire et résolvez le problème de correspondance 1D dans cette ligne.

2. Répétez le processus pour une poignée de lignes aléatoires différentes pour obtenir une collection de correspondances candidates.

3. Demandez à vos candidats candidats de «voter» point par point pour trouver le «meilleur» match.