Aquí tengo un problema de algoritmo. Es diferente del normal Fermat Point problem.algoritmo para encontrar un punto entre n puntos en el plano para minimizar la suma de distancias
Dado un conjunto de n puntos en el plano, necesito encontrar cuál puede minimizar la suma de distancias al resto de n-1 puntos.
¿Hay algún algoritmo que conozca ejecute menos que O (n^2)?
Gracias.
Una solución es suponer que la mediana está cerca de la media y para un subconjunto de puntos cercanos a la media, calcular exhaustivamente la suma de distancias. Puede elegir los puntos klog (n) más cercanos a la media, donde k es una constante elegida arbitrariamente (complejidad nlog (n)).
Otra solución posible es Delaunay Triangulation. Esta triangulación es posible en el tiempo O (nlogn). La triangulación da como resultado un gráfico con un vértice para cada punto y los bordes para satisfacer la triangulación de Delauney. Una vez que tenga la triangulación, puede comenzar en cualquier punto y comparar la suma de las distancias de ese punto con sus vecinos y seguir moviéndose de forma iterativa. Puede detenerse cuando el punto actual tiene la suma mínima de distancia en comparación con sus vecinos. Intuitivamente, esto se detendrá en el punto óptimo global.
Gracias por la idea. ¿Qué quiere decir exactamente "para un subconjunto de puntos cercanos a la media"? ¿Cómo se define "cerrar" aquí? También en el pensamiento de "Triangulación de Delaunay", ¿cómo "seguir avanzando de forma iterativa"? ¿Cómo decir el criterio de parada? –
@littleEinstein Vea la solución actualizada. – ElKamina
Creo que la suposición subyacente aquí es que tiene un conjunto de datos de puntos que puede enlazar fácilmente, ya que muchos algoritmos que serían "suficientemente buenos" en la práctica pueden no ser lo suficientemente rigurosos para la teoría y/o pueden no escalarse bien para soluciones arbitrariamente grandes.
Una solución muy simple que probablemente sea "lo suficientemente buena" es ordenar las coordenadas en la ordenada Y, luego hacer una ordenación estable en la ordenada X.
Tome el rectángulo definido por los valores mínimo (X, Y) y máximo (X, Y), complejidad O (1) ya que los valores estarán en ubicaciones conocidas en el conjunto de datos ordenado.
Ahora, trabajando desde el centro de su conjunto de datos ordenado, encuentre valores de coordenadas lo más cercanos posible a {Xctr = Xmin + (Xmax - Xmin)/2, Yctr = Ymin + (Ymax - Ymin)/2} - complejidad O (N) limitada por sus criterios de minimización, siendo la distancia el radio familiar de {Xctr, Yctr}.
La peor de las complicaciones sería comparar su centroide con cualquier otro punto, pero una vez que se aleje de los puntos intermedios, no mejorará el óptimo global y debería finalizar la búsqueda.
Desea el http://en.wikipedia.org/wiki/Geometric_median –
¿Necesita el algoritmo para trabajar con la distancia euclidiana o cualquier tipo de distancia? – Josay
@ScottHunter Creo que quiere el punto más cercano a la mediana geométrica (que no debería ser mucho más difícil de encontrar), pero no estoy seguro. – Josay