크기의 그룹은 거리에 따라 2입니다.

Question

나는 각각에 대해 위도와 경도가있는 수천 개의 길이가 N 인 목록을 가지고 있습니다.

난 (N이 홀수 인 경우, 하나의 3 것) 각각 함유하는 2 점, 그룹 N/2 그룹들로 이러한 점 싶다.

이 그룹의 목적은 2 점 사이의 거리를 최소화하는 것이다. 각 그룹에 대한 오차를 제곱 된 점 사이의 거리로 생각할 수 있습니다. 그리고 모든 그룹에 대한 오류의 합계 오류 합계.

이를 달성하기 위해 최선의 알고리즘이 될 것입니다 무슨 알고리즘은 상대적으로 빠른 (이이 API에 배포하고 사용자 요청에 대한 응답으로 실행됩니다) 있어야 제약 조건을 감안할 때?

그룹화는 반드시 '최고'할 수 있지만, 바람직하게는 결정적 일 필요는 없습니다.

Answer 1

센터를 계산하십시오.

센터에서 거리별로 정렬.

내림차순으로

, 다음 타의 추종을 불허하는 지점을 선택하고 가장 가까운 타의 추종을 불허하는 이웃 페어링. 삼각형 부등식을 사용하여 후보를 작게 유지할 수 있습니다.

색인으로,이 욕심 꾸러기 접근은 O (n log n) 그렇지 않으면 O (n^2)이다. 그것은 아마도 최상의 결과는 아니지만이 실행 시간 동안 상당히 좋을 것입니다. 사전 정렬은 (센터가 너무 불균형하지 않는 한) 정말 나쁜 경우를 피합니다.

Answer 2

첫째, 우리는 사분면 함수를 정의 할 수 있습니다 :

int quadrant(point a){ 
    if(a.latitude > 0) 
     if(a.longitude > 0) return 1; 
     else    return 2; 
    else 
     if(a.longitude < 0) return 3; 
     else    return 4; 
} 

을하고 우리는이 같은 점을 정렬 할 수 있습니다

이

bool comparison(point a, point b){ 
    if (quadrant(a) == quadrant(b)){ 
     if(a.longitude > b.longitude) return true; 
     else return a.longitude > b.longitude; 
    else 
     return quadrant(a) < quadrant(b); 
} 

사분면 기능은 단지 직교 평면으로 작동을하고, 도움이 될 것입니다 당신은 함께 포인트를 넣어.

이와 비슷한 비교를 기반으로 정렬하면 가까운 지점을 그룹화하는 데 도움이되므로 쌍 (a1, a2), (a3, a4), ..., (an-1, an) 및 O (N lg (N)) 시간이 걸립니다. 당신은 인접한 사분면을 더 나은 치료하거나 좀 더 논리를 할 경우

당신은 조금을 최적화 할 수 있습니다, 그러나 이것은 좋은 시작이다.