ClosestPair(근접쌍) 알고리즘 - 분할정복

ClosestPair(근접쌍) 알고리즘 - 분할정복

ClosestPair.zip

본문 Point xSorted = new Point numberOfPoints ; Point ySorted = new Point numberOfPoints ; System.arraycopy(points, 0, xSorted, 0, numberOfPoints); System.arraycopy(points, 0, ySorted, 0, numberOfPoints); Arrays.sort(xSorted); Arrays.sort(ySorted, new PointComparatorByY()); double minDistance2 = closestPairDNC(xSorted, ySorted); System.out.printf( distance from closestPairDNC = %.2f \n\n , minDistance2); assert (minDistance1 minDistance2); 하고 싶은 말 근접쌍(Closest Pair) 알고리즘 - 분할정복 기법 을 사용하여 점들의 최단 거리 및 소요시간을 출력해 주는 프로그램 입니다. 출력결과에 대한 대략적인 설명은 // BruteForce(이중 for 문) : 1000개의 임의의 점에서 최단거리를 찾았을 때 14밀리세컨드 소요, 최단 거리 : 1.41 For 1000 points, time diff(milli) = 14 diff(sec) = 0 distance from closestPairBruteForce = 1.41 // DNC(Divide And Conquer분할정복) // 1000개의 임의의 점에서 최단거리를 찾았을 때 3밀리세컨드 소요, 최단 거리 : 1.41 time diff(milli) = 3 diff(sec) = 0 distance from closestPairDNC = 1.41 위와 같이 이중 for loop와 분할정복 알고리즘의 속도차를 비교해서 알려 줍니다. 최단거리 측정이 필요한 다양한 프로그램에 응용가능합니다. 키워드 근접쌍, closest, 분할 정복, 최단거리, 최근접점쌍