Mapear un conjunto de puntos 3D a otro conjunto con una suma mínima de distancias

Question

Se proporcionan dos conjuntos de puntos tridimensionales, un conjunto de origen y uno de destino. 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, se deben ignorar los puntos adicionales.

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

Me interesan tanto las aproximaciones como las soluciones exactas.

Editar: 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

En la parte superior de mi cabeza, ordenamiento espacial seguido de recocido simulado.

Cuadrícula el espacio & amp; ordenar los conjuntos en celdas espaciales.

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

Finalmente, ejecute muchos ciclos de recocido simulado, en el que altere las coincidencias al azar, para explorar el espacio cercano.

Esto es heurístico, te da una buena respuesta, aunque no necesariamente la mejor, y debería ser bastante eficiente debido al tipo de cuadrícula inicial.

Answer 2

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

Usted trata los puntos como los vértices del gráfico, y los pesos de los bordes son la distancia entre puntos. Debido a que los algoritmos más rápidos suponen que está buscando una coincidencia máxima (y no mínima como en su caso), y que los pesos no son negativos, puede redefinir los pesos para que sean, por ejemplo:

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

donde bigNumber es más grande que su 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, por ejemplo, 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 manera usted terminará- con algoritmos O (NM max (N, M)), donde N y M son tamaños de sus conjuntos de puntos.

Answer 3

Aunque realmente no tengo una respuesta a su pregunta, puedo sugerir que analice los siguientes temas. (Sé muy poco sobre esto, pero lo encontré anteriormente en Stack Overflow).

• Búsqueda de vecinos más cercanos
• k d-tree

Espero que esto ayude un poco.