Tengo un conjunto de puntos y una función de distancia aplicable a cada par de puntos. Me gustaría conectar TODOS los puntos juntos, con la distancia total mínima. ¿Conoces un algoritmo existente que podría usar para eso?Algoritmo para conectar todos los puntos con la distancia total mínima
Cada punto puede vincularse a varios puntos, por lo que este no es el habitual "itinerario vendedor" problema :)
Gracias!
Lo que quiere es un .
Los dos algoritmos más comunes para generar uno son:
El algoritmo que está buscando se llama árbol de expansión mínima. Es útil encontrar el costo mínimo para una red de agua, teléfono o electricidad. Existe el algoritmo de Prim o el algoritmo de Kruskal. El algoritmo de IMO Prim es un poco más fácil de entender.
aquí http://en.wikipedia.org/wiki/Minimum_spanning_tree usted puede encontrar más información sobre el árbol de expansión mínimo, para que puedas adaptarlo a resuelve tu problema
Echa un vistazo al algoritmo de Dijkstra:
algoritmo de Dijkstra, concebido Holandés científico de la computación Edsger Dijkstra en 1956 y publicado en 1959, es un algoritmo de búsqueda gráfica que resuelve el origen único problema del camino más corto para un gráfico con costos de ruta de borde no negativos, produciendo un árbol de ruta más corto. Este algoritmo se usa a menudo en el enrutamiento y como una subrutina en otros algoritmos de gráficos.
http://en.wikipedia.org/wiki/Dijkstra 's_algorithm
Como otros han dicho, el minimum spanning tree (MST) le permitirá formar una sub-gráfico distancia mínima que conecta todos sus puntos.
Sin embargo, primero tendrá que formar un gráfico para su conjunto de datos. Para formar de manera eficiente un gráfico no dirigido, puede calcular el Delaunay triangulation de su conjunto de puntos. La conversión de la triangulación al gráfico es bastante literal: cualquier borde en la triangulación es también un borde en el gráfico, ponderado por la longitud del borde de triangulación.
Existen algoritmos eficientes para las fases MST (Prim's/Kruskal's O(E*log(V))) y Triangulación Delaunay (Divide y Conquista O(V*log(V))), por lo que son posibles enfoques globales eficientes.
Espero que esto ayude.
Esto podría interpretarse como un problema de árbol de expansión de peso mínimo. No estoy seguro de que sea la mejor forma de abordarlo, pero es de una manera. – biziclop
Si la métrica de distancia sigue a D (x, z) <= D (x, y) + D (y, z) por cada tres puntos x, y y z, básicamente conectar cada par de puntos daría una distancia mínima total. Creo que necesitas refinar tu pregunta un poco. – ElKamina
La métrica de distancia podría ser la suma de todas las longitudes de las conexiones. –