원본 및 대상 집합의 두 세트의 3 차원 점이 있습니다. 각 집합의 점 수는 임의입니다 (0 일 수 있음). 작업은 모든 대상 지점에 하나 또는 모든 소스 지점을 지정하여 모든 거리의 합이 최소가되도록하는 것입니다. 목적 지점보다 더 많은 근원이 있다면, 추가 지점은 무시되어야한다.최소 거리 합계를 사용하여 3D 점 집합을 다른 집합에 매핑
이 문제에 대한 무차별 대책이 있지만 점수가 클 수는 없으므로 실현 불가능합니다. 나는이 문제가 동일한 세트 크기를 가진 2D에서 쉽다고 들었지만 슬프게도 이러한 전제 조건은 여기에 주어지지 않았다.
근사치와 정확한 해결책에 모두 관심이 있습니다.
편집 : 하하, 네, 숙제 같은 것 같아요. 사실, 그렇지 않습니다. 저는 많은 수의 차량 위치를 얻는 프로그램을 작성하고 있습니다. 각 주차 셀에 맵핑하려고합니다. :)
내 머리 꼭대기에서 공간적 정렬을 한 다음 시뮬레이트 된 어닐링을 수행합니다.
그리드 공간 & 집합을 공간 셀로 정렬하십시오.
각 셀 내에서, 그리고 셀 인접 내에서 O (NM) 문제를 해결하고 평가판 일치를 얻으십시오.
마지막으로, 시뮬레이트 된 어닐링 사이클을 많이 실행하여 임의로 일치 항목을 변경하여 주변 공간을 탐색하십시오.
이것은 경험적이며 최상의 답변은 아니지만 최상의 그리드 정렬로 인해 매우 효율적이어야합니다.
귀하의 질문에 대한 답변이 없지만 다음 주제를 살펴볼 수 있습니다. (나는 이것에 대해 거의 알고 있지만 스택 오버플로에 이전에 발생했습니다.)
희망이 조금 도움이됩니다. 이 문제에 접근 할 수
한 가지 방법은 고전 할당 문제로되어 치료하는 것입니다 http://en.wikipedia.org/wiki/Assignment_problem
당신은 그래프의 정점으로 포인트를 치료하고, 가장자리의 가중치는 점 사이의 거리입니다. bigNumber가 큰 곳
weight(A, B) = bigNumber- distance(A,B)
을 : 가장 빠른 알고리즘은 최대 일치 (귀하의 경우와 같이되지 최소) 찾고있는, 그리고 가중치가 음수가 아닌 것으로 가정하기 때문에, 당신은 무게 등으로 다시 정의 할 수 있습니다 너의 최장 거리보다.
분명히 두 가지 그래프로 끝납니다. 그런 다음 최대 가중치가있는 두 부분 일치 (예 : 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은 점 집합의 크기입니다.
숙제 같은 냄새가납니다. –
주차 세포에 자동차 매핑?하하가 맞습니다. 어떤 도움이 필요하면 더 풀이/그럴듯한 설명을하거나 깨끗하게 와야합니다. "숙제"태그를 직접 추가하고 지금까지 한 일을 요약하십시오. – MarkusQ
미안하지만 숙제가 아닙니다. 내가 CS 전공을 가졌고 사용 가능한 알고리즘을 알아낼 수 있었다면 나는 그렇게 부탁하지 않을 것이다. – mafu