Asignación de un conjunto de puntos 3D a otro conjunto con suma mínima de distancias

Question

Se dan dos conjuntos de puntos tridimensionales, una fuente y un conjunto de destinos. El número de puntos en cada conjunto es arbitrario (puede ser cero). La tarea es asignar uno o ningún punto de origen a cada punto de destino, de modo que la suma de todas las distancias sea mínima. Si hay más puntos de origen que de destino, los puntos adicionales deben ignorarse.

Existe una solución de fuerza bruta para este problema, pero como el número de puntos puede ser grande, no es factible. Escuché que este problema es fácil en 2D con el mismo tamaño de conjunto, pero lamentablemente estas condiciones previas no se dan aquí.

Me interesan tanto las aproximaciones como las soluciones exactas.

Edit: Jaja, sí, supongo que suena como tarea. En realidad, no lo es. Estoy escribiendo un programa que recibe posiciones de una gran cantidad de automóviles y estoy tratando de asignarlos a sus respectivas celdas de estacionamiento. :)

Answer 1

Off the top of my head, spatial sort seguido por recocido simulado.

Cuadricula el espacio & clasifica los conjuntos en celdas espaciales.

Resuelva el problema O (NM) dentro de cada celda, luego dentro de los vecindarios de la celda, y así sucesivamente, para obtener una coincidencia de prueba.

Finalmente, ejecute muchos ciclos de recocido simulado, en el que altera al azar las coincidencias, a fin de explorar el espacio cercano.

Esto es heurístico, consiguiendo una buena respuesta aunque no necesariamente la mejor, y debería ser bastante eficiente debido a la ordenación inicial de la cuadrícula.

Answer 2

Aunque realmente no tengo una respuesta a su pregunta, puedo sugerir que investigue los siguientes temas. (Sé muy poco acerca de esto, pero se encontró con que previamente desbordamiento de pila.)

• Nearest Neighbour Search
• kd-tree

espero que esto ayude un poco.

Answer 3

Una forma de poder abordar este problema es de tratar es como el clásico problema de asignación: http://en.wikipedia.org/wiki/Assignment_problem

Se trata a los puntos ya que los vértices del grafo, y los pesos de los bordes son la distancia entre los puntos. Debido a que los algoritmos más rápidos suponen que está buscando un emparejamiento máximo (y no menos importante como en su caso), y que los pesos no son negativos, puede volver a definir los pesos sean por ejemplo:

weight(A, B) = bigNumber- distance(A,B) 

donde bigNumber es más grande que tu distancia más larga.

Obviamente terminas con un gráfico bipartito. Luego, utiliza uno de los algoritmos estándar para la coincidencia bipartita ponderada máxima (muchos recursos en la web, p. Ej. http://valis.cs.uiuc.edu/~sariel/teach/courses/473/notes/27_matchings_notes.pdf o Wikipedia para información general: http://en.wikipedia.org/wiki/Perfect_matching#Maximum_bipartite_matchings) De esta forma terminará con un algoritmo O (NM max (N, M)) , donde N y M son tamaños de tus conjuntos de puntos.