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

소개글

ClosestPair(근접쌍) 알고리즘 - 분할정복에 대한 보고서 자료입니다.

목차

[.settings]
[bin]
[src]
.classpath
.project



파일 14, 폴더 3
23.0KB

본문내용

//package com.nts.algorithm_hw4_1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ClosestPair {
　　　　private static double INFINITY = Double.MAX_VALUE;

　　　　// compute closest pair - brute force method
　　　　static double closestPairBruteForce0(Point[] points) {
　　　　　　　　double minDistance = INFINITY;
　　　　　　　　double distance;

　　　　　　　　int numberOfPoints = points.length;
　　　　　　　　for (int i = 0; i < numberOfPoints - 1; i++) { // outer loop
　　　　　　　　　　　　for (int j = i + 1; j < numberOfPoints; j++) { // inner loop
　　　　　　　　　　　　　　　　distance = points[i].distance(points[j]);
　　　　　　　　　　　　　　　　if (distance < minDistance) { // remember the shortest distance
　　　　　　　　　　　　　　　　　　　　minDistance = distance;
　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　}
　　　　　　　　}
　　　　　　　　return minDistance;
　　　　}




　≪ … 중 략 … ≫




　　　　public static void main(String[] args) {
　　　　　　　　for (int i = 3; i < 6; i++) {
　　　　　　　　　　　　int numberOfPoints = (int) Math.pow(10, i);
　　　　　　　　　　　　System.out.print(\\"For \\" + numberOfPoints + \\" points, \\");

　　　　　　　　　　　　Point[] points = PointGenerator.generate(numberOfPoints);

　　　　　　　　　　　　double minDistance1 = closestPairBruteForce(points);
　　　　　　　　　　　　System.out.printf(
　　　　　　　　　　　　　　　　　　　　\\"distance from closestPairBruteForce = %.2f \n\n\\",
　　　　　　　　　　　　　　　　　　　　minDistance1);

키워드

근접쌍,   closest,   분할정복,   최근접점쌍,   closest pair,   divide and conquer,   최단거리,   가까운 점,   알고리즘,   자료구조