J'ai un ensemble de points dans l'espace de coordonnées 2D.
J'aimerais trouver l'ensemble des chemins qui les connectent avec la longueur totale la plus courte. (solution heuristique ok, ne doit pas nécessairement être exacte.)
Cela pourrait sembler comme le problème du vendeur itinérant, mais c'est différent. Je ne cherche pas un cycle qui visitera chaque point une fois et une seule fois. J'ai juste besoin de chaque point relié à au moins un autre point de sorte que tous les points de l'ensemble sont au moins indirectement connectés l'un à l'autre avec la somme des longueurs des connexions choisies à minimiser. Il devrait donc être acyclique de minimiser la somme des longueurs des connexions.
Un simple algorithme voisin le plus proche (c.-à-d. Connectez-vous chaque point à son voisin le plus proche qui n'est pas déjà connecté à celui-ci) ne fonctionne pas car de petites grappes qui sont loin les unes des autres se retrouveront isolé et vous finirez toujours pas Up créant des cycles.
3 Réponses :
Si je comprends votre question correctement, ce que vous recherchez est un arbre au minimum étendu (souvent abrégé comme MST). Un MST n'est qu'un sous-ensemble de chemins
Il existe plusieurs algorithmes bien connus qui peuvent trouver un MST, tel que l'algorithme PRIM et l'algorithme de Kruskal - je vais vous marcher à travers Kruskal, que je trouve personnellement être la plus intuitive. Si vous êtes intéressé, vous devriez être capable de trouver des algorithmes supplémentaires en ligne ou dans des manuels d'algorithmes.
Kruskal commence par trier les chemins individuels par longueur. En utilisant cette liste, nous sommes ensuite en mesure de créer un MST en répétant le processus suivant jusqu'à ce que tous les points / sommets soient inclus dans notre arborescence:
Finalement, vous vous retrouverez avec un arbre qui
Notes:
(1) Lorsque vous traitez avec MST (et d'autres problèmes de graphique), nous appelons souvent des pièces par des noms spécifiques: l'ensemble des points est un "graphique", un point ou un nœud spécifique est un "sommet", des chemins entre les sommets sont "Bords" et les longueurs de bords sont des "poids".
(2) L'algorithme de Kruskal fonctionne dans le temps O (elogv), où E est le nombre de chemins / bords et v est le nombre de points / sommets.
(3) Si votre graphique contient des sommets ou des ensembles de sommets déconnectés du reste de l'ensemble de données, vous vous retrouverez avec plusieurs MST dans une "forêt de MST".
(4) Un graphique peut avoir plus d'un MST; par exemple dans Ce graphique , la longueur minimale du MST est 6 - qui est obtenue Par les deux MST suivants: MST1 , MST2
(5) déterminer si l'ajout d'un chemin créerait un cycle peut réellement être délicate; Une méthode de fonctionnement utilise la structure de données Unionfind, que vous pouvez jouer avec ici .
Le problème que vous décrivez des sons comme l'algorithme de Kruskal:
L'algorithme de Kruskal est un algorithme d'arbres minimum-étendu qui trouve un bord du poids le moins possible qui relie deux arbres dans la forêt.it est un algorithme gourmand dans la théorie des graphes car il trouve un Arbre minimum étendu pour un graphique pondéré connecté ajoutant une augmentation coûter des arcs à chaque étape. Cela signifie qu'il trouve un sous-ensemble des bords qui forme un arbre qui inclut chaque sommet, où le poids total de tous les bords de l'arborescence est minimisé. Si le graphique n'est pas connecté, alors il trouve une forêt étendue minimale (une étendue minimale arbre pour chaque composant connecté).
La complexité du temps kruskal Le pire cas est O (e journal E), cela parce que nous devons trier les bords. La complexité du temps PRIM est le pire des cas (e log V) avec une file d'attente prioritaire ou même mieux, O (E + V Log V) avec tas de fibonacci. Vous devez utiliser Kruskal lorsque le graphique est clairsemé, c'est-à-dire un nombre de bords, comme E = O (V), lorsque les bords sont déjà triés ou si nous pouvons les trier en temps linéaire. Nous devrions utiliser prim lorsque le graphique est dense, c'est un nombre d'arêtes est élevé, comme E = O (V²)
Comme les autres ont souligné, vous devez utiliser un MST. Mais si vous souhaitez choisir parmi toutes les paires de points (arêtes potentielles pour le MST), vous avez terminé avec une énorme quantité d'arêtes à traiter qui souffle d'exécution et de mémoire.
Il serait probablement plus rapide de commencer avec n'importe quel point, connectez-le à son voisin le plus proche qui ne crée pas de cycle et répétez cette étape jusqu'à ce que tout soit connecté.
Ceci est une autre manière plus rare de construire un arbre étendu au minimum qui devrait être plus rapide dans votre application.
Si vous voulez, je peux (essayer de) prouver l'algorithme que je viens de proposer.
Si vous arrivez à différentes solutions pour votre problème, remarquez qu'un MST n'est pas nécessairement unique, il peut y avoir plusieurs solutions optimales.
On dirait que vous décrivez le problème du MST.
Ah oui ça sonne comme ça.
Peut-être aussi connexe: le problème du Steiner Tree
Combien de points?