"일꾼이 일을 잘하려면 먼저 도구를 갈고 닦아야 한다." - 공자, 『논어』.
첫 장 > 프로그램 작성 > 분할 정복을 사용하여 가장 가까운 점 쌍 찾기

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

2024-07-30에 게시됨
검색:243

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

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 직사각형 영역에서 점을 어떻게 찾습니까? stripLstripR의 포인트가 y 좌표의 오름차순으로 정렬되면 이 작업을 효율적으로 수행할 수 있습니다. pointsOrderedOnY를 y 좌표의 오름차순으로 정렬된 포인트 목록으로 둡니다. pointsOrderedOnY는 알고리즘에서 미리 얻을 수 있습니다. stripLstripR는 아래 코드와 같이 3단계의 pointsOrderedOnY에서 얻을 수 있습니다.

Image description

pointOrderedOnY의 각 포인트 p에 대해
if (p는 S1에 있고 mid.x – p.x p를 StripL에 추가;
else if (p는 S2에 있고 p.x - mid.x p를 p를 추가하여 StripR;

다음과 같이 stripLstripR의 점을 {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 



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

따라서 가장 가까운 점 쌍은 O(n log n) 시간에 찾을 수 있습니다.

릴리스 선언문 이 기사는 https://dev.to/paulike/finding-the-closest-pair-of-points-using-divide-and-conquer-2deb?1에서 복제됩니다. 침해가 있는 경우, Study_golang@163으로 문의해 주세요. .com에서 삭제하세요
최신 튜토리얼 더>

부인 성명: 제공된 모든 리소스는 부분적으로 인터넷에서 가져온 것입니다. 귀하의 저작권이나 기타 권리 및 이익이 침해된 경우 자세한 이유를 설명하고 저작권 또는 권리 및 이익에 대한 증거를 제공한 후 이메일([email protected])로 보내주십시오. 최대한 빨리 처리해 드리겠습니다.

Copyright© 2022 湘ICP备2022001581号-3