분할정복(Divide and Conquer) - 최근접 점의 쌍 찾기

최근접 점의 쌍(closest pair) 문제는 2차원 평면상의 n개의 점이 입력으로 주어질 때 거리가 가장 가까운 한 쌍의 점(거리)을 찾는 문제이다.

 

 

최근접 점의 쌍을 찾는 방법으로는

• 모든 점에 대하여 각각의 두 점 사이의 거리를 계산하여 가장 가까운 점의 쌍을 찾는 방법 (BruteForce) - O(n^2)
• n개의 점을 1/2로 분할하여 각각의 부분 문제에서 최근접 점의 쌍을 찾고 부분해 중 짧은 쌍을 찾는 방법 (분할정복)

이 있다.

 

 

부분해를 취합(정복)하는 과정에서 중간 영역 사이의 점에서 더 근접한 점의 쌍이 존재할 수 있다.

중간 영역의 점들은 [왼쪽 그룹의 가장 오른쪽 점의 x 좌표에서 부분해를 뺀 값과 오른쪽 그룹의 가장 왼쪽 점의 x좌표에서 부분해를 더한 값 사이의 x 좌표 값을 가진 점]이다.

ex) 부분해 값이 10이고 왼쪽 그룹의 가장 오른쪽 점의 x좌표가 21, 오른쪽 그룹의 가장 왼쪽 점의 x좌표가 24이면,

  x좌표 값이 11부터 34 사이에 위치한 점들이 중간 영역에 해당하는 점들이다.

 

 

알고리즘을 간단하게 작성해보면,

#n을 점의 갯수라고 할 때
if(n==2):
    return distance #두 점 사이의 거리 return
elif (n==3):
    #점이 a,b,c,가 있으면
    return min(distance) #세 점 사이의 거리 중 최솟값 return
else:
    mid=(left+right)//2
    d1=CP(x<=mid)
    d2=CP(x>mid) ##영역 두개로 나눔
    d=min(d1,d2) # 두 부분해 중 최근접쌍 구함
    d3=mid-d<x<mid+d ##중간 영역 중 최근접쌍 탐색
    return min(d,d3)  #중간 영역과 d 값중 작은 값 변환

 

 

시간복잡도

closestPair 알고리즘의 분할과정은 합병 정렬과 동일하나 합병과정에서의 정렬하는 시간복잡도를 고려해야함.

k층까지 분할된 후, 층별로 취합되는 과정

각 층의 수행 시간 O(nlogn) * 층 수 (logn) 를 곱한 값인

이 된다.

 

 

알고리즘 구현(python)

import random
import math
n=10

def dist(p1,p2):
    return math.sqrt((p1[0]-p2[0])*(p1[0]-p2[0])+(p1[1]-p2[1])*(p1[1]-p2[1]))

def DMZcheck(p,left,right,d):
    p.sort(key=lambda x:x[1])
    for i in range(left,right+1):
        for j in range(i+1,right+1):
            if p[j][1]-p[i][1]>d:
                break
            tmp=dist(p[i],p[j])
            d=min(d,tmp)
    return d

def closestPairIter(p):
    dMin=10**6
    for i in range(1,n-1):
        for j in range(1,n-1):
            d=dist(p[i],p[j])
            if(d<dMin):
                dMIn=d
                iMin=i
                jMin=j
    print(p[iMin][0],p[iMin][1],p[jMin][0],p[jMin][1],dMin)
    

def closestPairRecur(p,left,right):
    size=right-left+1 #점의 갯수

    if(size==2):
        return dist(p[left],p[right]) #두 점 사이의 거리 return
    elif(size==3):
        a=dist(p[left],p[left+1])
        b=dist(p[left+1],p[right])
        c=dist(p[left],p[left+2])
        return min(a,b,c) #세 점 사이의 거리 중 min 값 return
    ##분할
    else:
        mid=(left+right)//2
        a=closestPairRecur(p,left,mid)
        b=closestPairRecur(p,mid+1,right)
        return DMZcheck(p,left,right,min(a,b)) #중간영역 
 
#중간 영역은 정복 전 마지막에 고려 후에 정복 시작(결과 취합)

p=[[0,0] for _ in range(n)] 
for i in range(n):
    p[i][0]=random.randint(0,100)
    p[i][1]=random.randint(0,50)

p.sort() #x좌표 정렬
print(p)
closestPairIter(p)
print("-"*10)
print(closestPairRecur(p,0,n-1))