宁波工程学院电信学院计算机系实验报告课程名称：算法设计与分析实验项目：用分治法算法解最接近点对问题指导教师：崔迪实验位置：软件工程实验室姓名：班级：学号：日期： 2016/10/12一、实验目的通过上机实验，要求掌握分治法算法的问题描述、算法设计思想、程序设计和算法复杂性分析等。
二、实验环境：Eclipse三、实验内容：用分治法解最接近点对问题（1）问题描述给定平面S上n个点，找其中的一对点，使得在n(n-1)/2 个点对中，该点对的距离最小。
（2）算法设计思想1. n较小时直接求 (n=2).2.将S上的n个点分成大致相等的2个子集S1和S23.分别求S1和S2中的最接近点对4.求一点在S1、另一点在S2中的最近点对5.从上述三对点中找距离最近的一对.（3）程序设计（程序清单及说明）package closestpair;import java.util.Arrays;import parator;import java.util.Random;import java.util.Scanner;//定义坐标点class Point {double x;double y;public Point(double x, double y) {this.x = x;this.y = y;}}// 根据x坐标排序class MyComparatorX implements Comparator<Point> { @Overridepublic int compare(Point p1, Point p2) {if (p1.x < p2.x) {return -1;} else if (p1.x > p2.x) {return 1;} else {return 0;}}}// 根据Y坐标排序class MyComparatorY implements Comparator<Point> { @Overridepublic int compare(Point p1, Point p2) {if (p1.y < p2.y) {return -1;} else if (p1.y > p2.y) {return 1;} else {return 0;}}}public class ClosestPair {public static Point[] point = new Point[2];public static double mindis = Double.POSITIVE_INFINITY;public static void main(String[] args) {do {System.out.print("请输入坐标点数:");Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();if (n <= 1) {System.out.println("请输入大于1的点数！");} else {Random random = new Random();Point point[] = new Point[n];for (int i = 0; i < n; i++) {point[i] = new Point(random.nextInt(100), random.nextInt(100));System.out.println("(" + point[i].x + "," + point[i].y + ")");}Comparator<Point> cmp = new MyComparatorX();Arrays.sort(point, cmp);closestUtil(point, point.length);break;}} while (true);System.out.println("最近点对是(" + point[0].x + "," + point[0].y + ")和" + "(" + point[1].x + "," + point[1].y + ")");System.out.println("距离为" + mindis);}// 比教两数最小public static double min(double x, double y) {return (x < y) ? x : y;}// 求两点之间距离public static double dist(Point p1, Point p2) {return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));}// 暴力方法找到最小的点对public static double minpair(Point P[], int n) {double min = Double.POSITIVE_INFINITY;for (int i = 0; i < n; ++i)for (int j = i + 1; j < n; ++j)if (dist(P[i], P[j]) < min) {min = dist(P[i], P[j]);if (min < mindis) {mindis = min;point[0] = P[i];point[1] = P[j];}}return min;}// 找出strip[] 数组中的最小点对public static double stripClosest(Point strip[], int size, double d) { double min = d;Comparator<Point> cmp = new MyComparatorY();Arrays.sort(strip, cmp);for (int i = 0; i < size; ++i)for (int j = i + 1; j < size && (strip[j].y - strip[i].y) < min; ++j)if (dist(strip[i], strip[j]) < min) {min = dist(strip[i], strip[j]);if (min < mindis) {mindis = min;point[0] = strip[i];point[1] = strip[j];}}return min;}// 递归的计算最小点对public static double closestUtil(Point P[], int n) { // 如果点较少，用暴力解决if (n <= 3)return minpair(P, n);// 找到中间点int mid = n / 2;Point midPoint = P[mid];// 分成两个部分，分别计算Point[] P1 = new Point[mid];Point[] P2 = new Point[n - mid];for (int i = 0; i < mid; i++) {P1[i] = P[i];}for (int i = mid, j = 0; i < n; i++) {P2[j] = P[i];j++;}double dl = closestUtil(P1, mid);double dr = closestUtil(P2, n - mid);double d = min(dl, dr);// 所有距离垂直线距离在d以内的点Point[] strip = new Point[n];int j = 0;for (int i = 0; i < n; i++)if (Math.abs(P[i].x - midPoint.x) < d) {strip[j] = P[i];j++;}Point[] strips = new Point[j];for (int i = 0; i < j; i++) {strips[i] = strip[i];}// 找出strip 数组中的最小点对return min(d, stripClosest(strips, j, d));}}（4）数据输入和结果输出（运行结果截屏显示）（5）算法复杂性分析在上面分成两部分后，需要找到 strip[] 数组，需要的时间为O(n)，排序strip[]的时间为 O(nLogn)，在strip[] 在找到最小点对的时间为 O(n) T(n) = O(1)(n<=3)2T(n/2) + O(n) + O(nLogn) + O(n)=2T(n/2) + O(nLogn)=O(n (Logn)^2)（n>3）四、实验心得与小结通过这次试验，对最近点对问题有了深入的了解，在编写算法中知道了分治法和鸽舍原理。
当在面对一个复杂的问题时，我们就可以利用分治法把复杂问题分解成一个个简单问题，再去解决。