3D 포인트 세트를 최소한의 거리로 다른 세트에 매핑

Question

3 차원 포인트의 두 세트, 소스 및 대상 세트가 제공됩니다. 각 세트의 점수는 임의적입니다 (0). 작업은 모든 거리의 합이 최소화되도록 모든 대상 지점에 하나 또는 전혀 소스 지점을 할당하는 것입니다. 대상 지점보다 더 많은 소스가있는 경우 추가 점이 무시됩니다.

이 문제에 대한 무자비한 솔루션이 있지만 포인트 수는 클 수 있기 때문에 가능하지 않습니다. 나는이 문제가 동일한 세트 크기로 2D로 쉽다고 들었지만 슬프게도 이러한 전제 조건은 여기에 제공되지 않습니다.

나는 근사치와 정확한 솔루션 모두에 관심이 있습니다.

편집 : 하하, 예, 숙제처럼 들린다 고 생각합니다. 사실, 그렇지 않습니다. 나는 많은 자동차의 위치를받는 프로그램을 작성하고 있으며 각 주차장에 매핑하려고합니다. :)

Answer 1

내 머리 꼭대기에서 공간 정렬 다음 시뮬레이션 어닐링이 이어집니다.

공간을 그리드하고 세트를 공간 세포로 분류하십시오.

각 세포 내에서 O (NM) 문제를 해결 한 다음 세포 이웃 내에서 등을 해결하여 시험 일치를 얻습니다.

마지막으로, 근처의 공간을 탐색하기 위해 무작위로 일치를 변경하는 시뮬레이션 된 어닐링 사이클을 많이 실행하십시오.

이것은 휴리스틱이며, 반드시 최고는 아니지만 좋은 답변을 얻는 것이 좋으며 초기 그리드 정렬로 인해 상당히 효율적이어야합니다.

Answer 2

이 문제에 접근 할 수있는 한 가지 방법은 고전적인 과제 문제입니다. http://en.wikipedia.org/wiki/assignment_problem

점을 그래프의 정점으로 취급하고 가장자리의 무게는 점 사이의 거리입니다. 가장 빠른 알고리즘은 최대 일치를 찾고 있다고 가정하고 (사례에서와 같이 최소값이 아님) 가중치는 음성이 없다고 가정하기 때문에 예를 들어 가중치를 재정의 할 수 있습니다.

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

어디 bigNumber 가장 긴 거리보다 큽니다.

분명히 당신은 양파자 그래프로 끝납니다. 그런 다음 최대 가중 2 분파 일치에 대한 표준 알고리즘 중 하나를 사용합니다 (웹의 많은 리소스, 예 : http://valis.cs.uiuc.edu/~sariel/teach/courses/473/notes/27_matchings_notes.pdf 또는 개요를위한 Wikipedia : http://en.wikipedia.org/wiki/perfect_matching#maximum_bipartite_matchings)이 방법으로 당신은 o (nm max (n, m)) 알고리즘으로 끝납니다. 여기서 n과 m은 포인트 세트의 크기입니다.

Answer 3

나는 당신의 질문에 대한 답이 실제로 없지만 다음 주제를 살펴 보는 것이 좋습니다. (나는 이것에 대해 거의 알지 못하지만 이전에 Stack Overflow에서 만났다.)

• 가장 가까운 이웃 검색
• 케이D- 트리

이것이 조금 도움이되기를 바랍니다.