On m'a donné une tâche où je dois connecter tous les points de l'avion 2D. Il y a quatre conditions à remplir:
image pour visualiser le problème:
La mauvaise image connectée des points correctement, bien que la longueur totale soit plus grande que celle à gauche.
Au début, j'ai pensé à trier les points et à le faire avec une ligne de balayage et à construire un arbre de toutes les possibilités, bien que cela semble être un moyen d'une solution compliquée avec une complexité énorme. Par conséquent, je cherche de meilleures approches. J'apprécierais quelques conseils quoi faire, ou comment puis-je m'approcher du problème.
4 Réponses :
wow, c'est un problème délicat. C'est beaucoup de conditions à rencontrer.
Je pense à un point de vue de la programmation, la solution "la plus simple" pourrait réellement être de la boucle, de trouver toutes les possibilités qui répondent aux 3 dernières conditions et enregistrent la longueur totale lorsque vous en boucle, et choisissez simplement celui avec La longueur la plus courte à la fin - force brute, devine-et-vérification. Je pense que c'est ce que vous faisiez référence à votre op lorsque vous avez mentionné une "ligne de balayage et construisant un arbre de toutes les possibilités". Cette approche est très chère de calcul, mais si le code est écrit correctement, il devrait toujours fonctionner à la fin.
Si vous voulez la solution "meilleure" solution, où vous voulez simplement résoudre la réponse finale unique, j'ai bien peur que mes compétences en mathématiques ne soient pas assez fortes pour cela - je ne suis même pas sûr s'il y a toute solution analytique unique à ce problème pour toute collection arbitraire de points. Peut-être essayez peut-être de vérifier avec les gens sur Mathoverflow . Si une personne là-bas peut vous expliquer avec les mathématiques derrière ce calcul, vous avez toujours besoin d'aide pour convertir ce mathématique en code dans un certain langage de programmation, mettez-vous à jour votre question (peut-être avec un lien vers la réponse qu'ils vous fournissent) et Je suis sûr que quelqu'un sera capable de vous aider à partir de ce point.
L'une des solutions possibles consiste à utiliser la théorie des graphes.
construire un graphique bipartite g, de sorte que chaque point ait sa copie dans les deux parties. Maintenant, mettez les bords entre les points Notez que, étant donné que cela se trouve sur un plan 2D euclidien, les "bords" résultants de la correspondance ne se croisent pas. Disons que les bords i et j avec le poids = i == j? Infinity: distance [i] [j] . La correspondance maximale maximale du poids dans le graphique sera la configuration souhaitée.
AB et xy intersect pour les points a, b, x, y . Ensuite, la correspondance n'est pas du poids minimum, car AX, par ou ay, bx produira un poids total plus petit sans intersection (ceci provient de l'inégalité de triangle A + B> c)
Je commencerais avec une triangulation de Delaunay de la partie Set. Cela devrait déjà vous donner les connexions voisines les plus proches de chaque point sans intersections. Si je ne me trompe pas, ce problème est lié lié au problème du sac à dos qui est NP-Hard, donc je ne suis donc pas sûr que cette solution vous donne vraiment le meilleur possible. à l'étape suivante, je regarderais les triangles qui résultent de la triangulation - la propriété commode ici est celle basée sur votre Manchet, vous pouvez choisir exactement un côté de chaque triangle et retirer les deux autres de la sélection.
Le problème qui reste maintenant est de choisir ces bords qui vous donnent la plus petite somme totale qui, bien sûr, ne sera pas toujours le plus petit que celui-ci aurait déjà pu être bloqué par un triangle voisin. Je commencerais par une approche gourmande, choisissant toujours le plus petit bord restant qui n'a pas encore été bloqué par les triangles voisins.
Je dirais que ceci est une extension du problème du vendeur itinérant Une bonne technique (si un peu à l'ancienne) consiste à utiliser une technique d'optimisation de recuit simulé .
Vous devrez effectuer des ajustements au coût (A.K.A. Objectif ) fonctionner pour rater des sections du chemin. Mais étant donné un chemin de candidat continu, il est raisonnablement trivial de décider quelles sections manqueraient de minimiser sa longueur. (Vous enlevez d'abord plus de toutes les lignes intersectives).
Je ne sais pas trop à ce sujet, mais si vous avez commencé avec une analyse K-Windows ( En.wikipedia.org/wiki/k-Means_Clustering ) Où
k = n / 2 ?n étant le nombre de points. Running K-signifie sur votre exemple semblait produire le résultat correct à chaque fois que je l'ai essayé. Avez-vous des exemples plus résolus avec des collections plus importantes de points?