Mappage d'un ensemble de points 3D sur un autre ensemble avec une somme minimale de distances

Question

On donne deux ensembles de points tridimensionnels, un ensemble source et un ensemble de destinations. Le nombre de points sur chaque ensemble est arbitraire (peut être zéro). La tâche consiste à affecter un ou plusieurs points sources à chaque point de destination, de sorte que la somme de toutes les distances soit minimale. S'il y a plus de points source que de destination, les points supplémentaires doivent être ignorés.

Il existe une solution brute-force à ce problème, mais puisque le nombre de points peut être grand, ce n’est pas faisable. J'ai entendu dire que ce problème était facile en 2D avec des tailles de jeu égales, mais malheureusement, ces conditions préalables ne sont pas données ici.

Je m'intéresse à la fois aux approximations et aux solutions exactes.

Edit: Haha, oui, je suppose que ça sonne comme un devoir. En fait, ce n'est pas. J'écris un programme qui reçoit les positions d'un grand nombre de voitures et j'essaie de les mapper vers leurs cellules de stationnement respectives. :)

Answer 1

De mémoire, un tri spatial suivi d'un recuit simulé.

Grille l'espace & amp; trier les ensembles en cellules spatiales.

Résolvez le problème O (NM) au sein de chaque cellule, puis au sein des quartiers de cellules, etc., pour obtenir une correspondance d'essai.

Enfin, exécutez de nombreux cycles de recuit simulé au cours desquels vous modifiez de manière aléatoire les correspondances afin d'explorer l'espace proche.

C’est une heuristique, qui vous donne une bonne réponse, même si ce n’est pas nécessairement la meilleure, et qui devrait être assez efficace en raison du tri initial de la grille.

Answer 2

Une des façons d’aborder ce problème est de traiter le problème classique des tâches: http: // en.wikipedia.org/wiki/Problem_Assignment

Vous traitez les points comme les sommets du graphique et les poids des arêtes représentent la distance entre les points. Comme les algorithmes les plus rapides supposent que vous recherchez une correspondance maximale (et non minimale comme dans votre cas) et que les pondérations ne sont pas négatives, vous pouvez redéfinir les pondérations pour qu'elles soient, par exemple, les suivantes:

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

où bigNumber est plus grand que votre plus longue distance.

Évidemment, vous vous retrouvez avec un graphique bipartite. Vous utilisez ensuite l’un des algorithmes standard pour une correspondance bipartite pondérée maximale (beaucoup de ressources sur le Web, par exemple, http://valis.cs.uiuc.edu/~sariel/teach/courses/473/notes/27_matchings_notes.pdf ou Wikipedia pour un aperçu: http://en.wikipedia.org/wiki/Perfect_matching#Maximum_bipartite_matchings ) De cette façon, vous allez finir avec un algorithme O (NM max (N, M)), où N et M sont les tailles de vos ensembles de points.

Answer 3

Bien que je n’aie pas vraiment de réponse à votre question, je peux suggérer d’examiner les sujets suivants. (Je sais très peu de choses à ce sujet, mais je l’ai déjà rencontré lors d’un débordement de pile.)

• Recherche de voisin le plus proche
• k d-arbre

J'espère que cela aide un peu.