Mapeamento de um conjunto de pontos 3D para outro conjunto com a soma mínima de distâncias

Question

Dado dois conjuntos de pontos tridimensionais, uma origem e um destino definido. O número de pontos em cada conjunto é arbitrária (pode ser zero). A tarefa é uma Atribuir ou nenhum ponto de origem para cada ponto de destino, de modo que a soma de todas as distâncias é mínima. Se houver mais fonte de pontos de destino, os pontos adicionais devem ser ignorados.

Há uma solução de força bruta para este problema, mas desde que o número de pontos pode ser grande, não é viável. Eu ouvi este problema é fácil em 2D com tamanhos iguais set, mas infelizmente estas condições não são dadas aqui.

Estou interessado em ambas as aproximações e soluções exatas.

Edit: Haha, sim, acho que soa como lição de casa. Na verdade, não é. Eu estou escrevendo um programa que recebe as posições de um grande número de carros e eu estou tentando mapeá-los para suas respectivas células de estacionamento. :)

Answer 1

Em cima da minha cabeça, tipo espacial seguido de recozimento simulado.

Grade do espaço e classificar os conjuntos em células espaciais.

Resolver o (NM) problema ó dentro de cada célula, em seguida, dentro de bairros celulares, e assim por diante, para obter uma correspondência de julgamento.

Finalmente, os lotes são executados de ciclos de recozimento simulado, em que você aleatoriamente partidas alterar, de forma a explorar o espaço nas proximidades.

Esta é heurística, ficando-lhe uma boa resposta embora não necessariamente o melhor, e que deve ser bastante eficiente, devido à grade inicial espécie.

Answer 2

Uma maneira que você poderia abordar este problema é tratar é como o problema de atribuição clássica: http: // en.wikipedia.org/wiki/Assignment_problem

tratar os pontos como os vértices do gráfico, e os pesos das bordas são a distância entre os pontos. Porque os algoritmos mais rápidos supor que você está procurando correspondência máxima (e não mínimo como no seu caso), e que os pesos são não-negativo, você pode redefinir pesos ser por exemplo:.

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

onde bigNumber é maior do que a sua maior distância.

Obviamente você acabar com um grafo bipartido. Então você usar um dos algoritmos padrão para correspondência máxima bipartida ponderada (lotes de recursos na web, por exemplo, http://valis.cs.uiuc.edu/~sariel/teach/courses/473/notes/27_matchings_notes.pdf ou Wikipedia para visão geral: http://en.wikipedia.org/wiki/Perfect_matching#Maximum_bipartite_matchings ) Desta forma, você vai finais -se com um O (NM max (N, M)) algoritmos, onde N e M são tamanhos de seus conjuntos de pontos.

Answer 3

Embora eu realmente não tenho uma resposta para sua pergunta, eu posso sugerir olhando para os seguintes tópicos. (Eu sei muito pouco sobre isso, mas encontrou anteriormente em Stack Overflow.)

• Nearest Neighbor Pesquisa
• k d-árvore

Espero que isso ajude um pouco.