Segments de ligne ne se recoupant pas tout en minimisant la longueur cumulée

Question

J'aimerais trouver un meilleur algorithme pour résoudre le problème suivant :

Il y a N points de départ (violet) et N points cibles (en vert) en 2D. Je veux un algorithme qui relie les points de départ aux points cibles par un segment de ligne (marron) sans qu'aucun de ces segments ne se croise (rouge) et en minimisant la longueur cumulée de tous les segments.

Mon premier effort en C++ a consisté à permuter tous les états possibles, à trouver des états sans intersection et, parmi ceux-ci, l'état dont la longueur totale du segment est la plus faible O(n !) . Mais je pense qu'il doit y avoir une meilleure façon de procéder.

Une idée ? Ou de bons mots-clés pour la recherche ?

Answer 1

T M .

Answer 2

Vous pouvez sélectionner une connexion aléatoire, puis à chaque fois supprimer une croix en changeant les connexions de ses points d'extrémité. Cette opération réduit la longueur totale (par inégalité des triangles). Comme le nombre de façons dont les lignes se croisent est fini, nous arrivons à une solution sans croisement en un nombre fini d'étapes. En pratique, cette solution devrait converger rapidement.

Answer 3

On dirait que vous pourriez utiliser un Type BSP algorithme.

Answer 4

Suite à la réponse de qq3 qui dit la contrainte d'intersection est redondante, il ne reste plus qu'une étape à franchir. Assigner des points de départ à des points d'arrivée tout en minimisant la longueur totale. Heureusement, il existe un algorithme en temps polynomial pour cela :

Algorithme hongrois est une optimisation combinatoire qui résout le problème d'affectation en temps polynomial.

Il réduit le temps de commande de O(n !) a O(n 3 ) .