분할 정복을 사용하여 가장 가까운 점 쌍 찾기-java지도 시간-php.cn

분할 정복을 사용하여 가장 가까운 점 쌍 찾기

WBOY

풀어 주다： 2024-07-18 00:58:51

원래의

1071명이 탐색했습니다.

이 섹션에서는 분할 정복을 사용하여 가장 가까운 점 쌍을 찾는 효율적인 알고리즘을 제시합니다. 일련의 점들이 주어졌을 때 가장 가까운 쌍 문제는 서로 가장 가까운 두 점을 찾는 것입니다. 아래 그림과 같이 가장 가까운 쌍 애니메이션에서는 가장 가까운 두 지점을 연결하는 선이 그려집니다.

Image description

사례 연구: 가장 가까운 쌍 찾기에서는 가장 가까운 점 쌍을 찾기 위한 무차별 대입 알고리즘을 제시했습니다. 알고리즘은 모든 점 쌍 사이의 거리를 계산하고 거리가 최소인 점을 찾습니다. 분명히 알고리즘은 O(n^2) 시간이 걸립니다. 좀 더 효율적인 알고리즘을 설계할 수 있을까요?

우리는 이 문제를 해결하기 위해 분할 정복이라는 접근 방식을 사용할 것입니다. 이 접근 방식은 문제를 하위 문제로 나누고 하위 문제를 해결한 다음 하위 문제의 솔루션을 결합하여 전체 문제에 대한 솔루션을 얻습니다. 동적 프로그래밍 접근 방식과 달리 분할 정복 접근 방식의 하위 문제는 겹치지 않습니다. 하위 문제는 크기가 더 작은 원래 문제와 같으므로 재귀를 적용하여 문제를 해결할 수 있습니다. 실제로 재귀 문제에 대한 모든 솔루션은 분할 정복 접근 방식을 따릅니다.

아래 단계에서는 분할 정복 접근법을 사용하여 가장 가까운 쌍 문제를 해결하는 방법을 설명합니다.

1단계: x 좌표의 오름차순으로 점을 정렬합니다. 동일한 x 좌표를 가진 점의 경우 y 좌표를 기준으로 정렬합니다. 그러면 정렬된 S점 목록이 생성됩니다.
2단계: 정렬된 목록의 중간점을 사용하여 S를 동일한 크기의 두 하위 집합 S1과 S2로 나눕니다. 중간점을 S1에 두십시오. S1과 S2에서 가장 가까운 쌍을 재귀적으로 찾습니다. d1과 d2는 각각 두 하위 집합에서 가장 가까운 쌍의 거리를 나타냅니다.
3단계: S1의 한 점과 S2의 한 점 사이에서 가장 가까운 쌍을 찾고 그 거리를 d3으로 표시합니다. 가장 가까운 쌍은 거리가 min(d1, d2, d3)인 쌍입니다.

선택 정렬에는 O(n^2) 시간이 걸립니다. 1단계는 O(n log n) 시간 안에 완료될 수 있습니다. 3단계는 O(n) 시간 안에 완료할 수 있습니다. d = 최소(d1, d2)라고 가정합니다. 우리는 가장 가까운 쌍 거리가 d보다 클 수 없다는 것을 이미 알고 있습니다. S1의 점과 S2의 점이 S에서 가장 가까운 쌍을 형성하려면 아래 그림과 같이 왼쪽 점은 stripL에 있고 오른쪽 점은 stripR에 있어야 합니다( 가).

stripL의 점 p에 대해서는 아래 (b)와 같이 d X 2d 직사각형 내의 올바른 점만 고려하면 됩니다. 직사각형 외부의 오른쪽 점은 p와 가장 가까운 쌍을 형성할 수 없습니다. S2의 가장 가까운 쌍 거리는 d보다 크거나 같으므로 최대 6개가 있을 수 있습니다
직사각형의 점. 따라서 stripL의 각 지점에 대해 stripR의 최대 6개 지점을 고려해야 합니다.

stripL의 각 점 p에 대해 stripR의 해당 d X 2d 직사각형 영역에서 점을 어떻게 찾나요? stripL 및 stripR의 포인트를 y좌표의 오름차순으로 정렬하면 이 작업을 효율적으로 수행할 수 있습니다. pointsOrderedOnY를 y 좌표의 오름차순으로 정렬된 포인트 목록으로 둡니다. pointsOrderedOnY는 알고리즘에서 미리 얻을 수 있습니다. stripL 및 stripR은 아래 코드와 같이 3단계의 pointsOrderedOnY에서 얻을 수 있습니다.

Image description

pointOrderedOnY의 각 포인트 p에 대해
if (p가 S1에 있고 mid.x – p.x <= d)
p를 StripL에 추가합니다.
else if (p는 S2에 있고 p.x - mid.x <= d)
p를 StripR에 추가합니다.

stripL 및 stripR의 포인트를 다음과 같이 {p0, p1, ... , pk} 및 {q0, q1, ... , qt}로 둡니다. 위의 그림 (c). stripL의 점과 stripR의 점 사이의 가장 가까운 쌍은 아래 코드에 설명된 알고리즘을 사용하여 찾을 수 있습니다.

d = min(d1, d2);
 r = 0; // r is the index of a point in stripR
 for (each point p in stripL) {
 // Skip the points in stripR below p.y - d
  while (r < stripR.length && q[r].y <= p.y - d)
  r++;

  let r1 = r;
  while (r1 < stripR.length && |q[r1].y – p.y| <= d) {
 // Check if (p, q[r1]) is a possible closest pair
 if (distance(p, q[r1]) < d) {
 d = distance(p, q[r1]);
 (p, q[r1]) is now the current closest pair;
 }

 r1 = r1 + 1;
 }
}

로그인 후 복사

stripL의 포인트는 p0, p1, ... , pk 순으로 고려됩니다. stripL의 p 지점에 대해 p.y – d 아래에 있는 stripR의 지점을 건너뜁니다(5~6행). 건너뛴 지점은 더 이상 고려되지 않습니다. while 루프(9~17행)는 (p, q[r1])이 가능한 가장 가까운 쌍인지 확인합니다. 이러한 q[r1] 쌍은 최대 6개입니다. stripR의 두 점 사이의 거리는 d보다 작을 수 없기 때문입니다. 따라서 3단계에서 가장 가까운 쌍을 찾는 복잡성은 O(n)입니다.

위 단계의 1단계는 포인트를 사전 정렬하기 위해 한 번만 수행됩니다. 모든 점이 미리 정렬되어 있다고 가정합니다. T(n)은 이 알고리즘의 시간 복잡도를 나타냅니다. 그리하여

Image description