suma más pequeña de pares

Question

Dadas 2n-puntos en una 2D plano, usted tiene que agruparlos en N pares tal que la suma total de las distancias entre los puntos de todos los pares es el mínimo posible valor. El resultado deseado es solo la suma.

En otras palabras, si a1, a2, .. un son las distancias entre los puntos de primer, segundo y enésimo par ... respectivamente, entonces (a1 + a2 + ... a) deberá ser como mínimo .

Consideremos esta prueba de los casos, si los 2 * 5 puntos son: {20,20}, { 40, 20}, {10, 10}, { 2, 2 }, {240, 6}, {12, 12}, {100, 120}, {6, 48}, {12, 18}, {0, 0}

deseado la salida es .

Esta no es mi tarea, soy curioso acerca de diferentes enfoques en lugar de la fuerza bruta.

Answer 1

Parece que está buscando Minimum weight perfect matching.

Existen algoritmos para explotar el hecho de que estos son puntos en un plano. Este documento: Mincost Perfect Matching in the Plane tiene un algoritmo y también menciona algunos trabajos previos sobre él.

---

a lo solicitado, aquí es una breve descripción de un algoritmo de "simple" para la coincidencia perfecta de peso mínima en un gráfico. Este es un breve resumen de partes del capítulo sobre emparejamiento ponderado en el libro Optimización combinatoria, algoritmos y complejidad de Papadimitriou & Steiglitz.

Supongamos que se le asigna un gráfico ponderado no dirigido G (con un número par de nodos). El gráfico puede considerarse un gráfico ponderado completo, al agregar los bordes faltantes y asignarles pesos muy grandes.

Supongamos que los vértices están etiquetados de 1 a ny el peso del borde entre los vértices i y j es c (i, j).

Tenemos n (n-1)/2 variables x (i, j) que denotan una coincidencia de G. x (i, j) = 1 si el borde entre i y j está en la coincidencia y x (i, j) = 0 si no lo es.

Ahora el problema de adaptación se puede escribir como el problema de programación lineal:

minimizar Sum c (i, j) * x (i, j)

sujeto a la condición de que

Suma x (1, j) = 1, donde j varía de 1 a n.

Sum x (2, j) = 1, donde j varía de 1 a n. . . .

Sum x (n, j) = 1, donde j varía de 1 a n.

(Sum x (1, j) = 1 significa básicamente que estamos seleccionando exactamente una arista incidente el vértice marcado con 1.)

Y la condición final de que

x (i, j)> = 0

(que podría haber dicho x (i, j) = 0 o 1, pero eso no sería hacer de este un problema de programación lineal a medida que las restricciones son o ecuaciones lineales o desigualdades)

hay un método llamado el método Simplex, que puede resolver este problema de programación lineal para dar una solución óptima en el tiempo polinomio en el número de variables.

Ahora, si G eran bipartito, se puede demostrar que podemos obtener una solución óptima tal que x (i, j) = 0 o 1. Así, mediante la resolución de este problema de programación lineal para un gráfico bipartito, obtenemos una conjunto de asignaciones para cada x (i, j), cada una de las cuales es 0 o 1. Ahora podemos obtener una coincidencia seleccionando los bordes (i, j) para los cuales x (i, j) = 1. Las restricciones garantizan que lo hará ser un emparejamiento con el peso más pequeño.

Desafortunadamente, esto no es cierto para los gráficos generales (es decir, x (i, j) siendo 0 o 1). Edmonds descubrió que esto se debía a la presencia de ciclos impares en el gráfico.

Así, además de los contraints anteriores, Edmonds añadió la restricción adicional de que en cualquier subconjunto de vértices de tamaño 2k + 1 (es decir, de tamaño impar), el número de bordes coincidentes no es más que k

Enumerate cada subconjunto impar de vértices para obtener una lista de conjuntos S (1), S (2), ..., S (2^n - n). Deje tamaño de S (r) sea de 2 * s (r) + 1.

Entonces las limitaciones anteriores son, para cada conjunto S (r)

Sum x (i, j) + y (r) = s (r), para i, j en S (r).

Edmonds entonces demostró que esto era suficiente para garantizar que cada uno de x (i, j) es 0 o 1, lo que nos da una correspondencia perfecta de peso mínimo.

Por desgracia, ahora el número de variables se ha convertido exponencial de tamaño. Entonces, el algoritmo simplex, si solo se ejecuta en este estado, conducirá a un algoritmo de tiempo exponencial.

Para superar esto, Edmonds considera el doble de este problema de programación lineal (no entraré en detalles aquí), y muestra que el algoritmo primal-dual cuando se ejecuta en el dual solo toma O (n^4) pasos para llegar a una solución, ¡dándonos un algoritmo de tiempo polinomial! Lo muestra mostrando que, como máximo, O (n) de y (r) no son cero en ningún paso del algoritmo (que él llama flores).

Aquí hay un enlace que debe explicar en detalle un poco más: http://www.cs.ucl.ac.uk/staff/V.Kolmogorov/papers/blossom5.pdf, Sección 2.

Merece la pena leer el libro que mencioné antes (aunque puede ser un poco seco) para obtener una comprensión más profunda.

Phew. ¡Espero que ayude!

---

Answer 2

Su suma final estará dominada principalmente por el mayor sumando. El algoritmo más simple para explotar esto podría ir como esto (no puedo demostrar esto):

1. puntos en orden descendente por su distancia del vecino más próximo
2. forma par de la primera entrada y su vecino más cercano
3. retire el par de lista
4. si la lista no vacía Goto 1.

Esto debería funcionar muy a menudo.

Dado que usted está buscando esencialmente un algoritmo de agrupamiento para clusters de 2 this link o una búsqueda de clustering algorithms for jet reconstruction podría ser interesante. La gente de la comunidad experimental de física de partículas está trabajando en algoritmos heurísticos para problemas como este.

Answer 3

Después de buscar en Google por un tiempo, encontré algunas otras referencias a peso mínimo que coinciden perfectamente con los algoritmos que pueden ser más fáciles de entender (al menos, más fáciles hasta cierto punto).

EDITAR

Here I found a python implementation de uno de esos algoritmos. Tiene 837 líneas de código (+ algunas pruebas de unidades adicionales), y yo no lo probé solo. Pero tal vez puedas usarlo para tu caso.

Here is a link a un algoritmo de aproximación para el problema. Por supuesto, el estilo del papel también es matemático, pero en mi humilde opinión es mucho más fácil de entender que el papel de Cook y Rohe. Y afirma en su prefacio que apunta exactamente para que el propósito sea más fácil de implementar que el algoritmo original de Edmond, ya que no necesita un solucionador de programación lineal.

Edit2:

Después de pensar un rato sobre el problema, en mi humilde opinión, debe ser posible para establecer una búsqueda A* para resolver este problema. El espacio de búsqueda aquí es el conjunto de 'emparejamientos parciales' (o conjuntos de puntos parcialmente emparejados). Como Moron ya escribió en sus comentarios, uno puede restringir la búsqueda a la situación donde no existen pares con líneas de conexión cruzadas. La función de costo de ruta (para usar los términos de Wikipedia) es la suma de las distancias de los puntos ya emparejados. La función heurística h(x) puede ser cualquier subestimación para las distancias restantes, por ejemplo, cuando tiene 2M puntos no emparejados hasta el momento, tome la suma de M distancias mínimas entre todos los puntos restantes.

Probablemente ese no sea tan eficiente como el algoritmo al que se refirió Moron, pero sospecho que será mucho mejor que 'fuerza bruta', y mucho más fácil de implementar.