900字范文 > 最近点对问题（分治法）

最近点对问题（分治法）

时间：2023-01-28 13:11:19

相关推荐

最近点对问题（分治法）

问题描述

给定平面S上n个点，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小

蛮力法求解

点的存储：

class Point{//横坐标int x;//纵坐标int y;/*** 求解两个坐标之间的距离* @return*/public static double distance(Point ri, Point le) {return Math.sqrt((ri.x - le.x)*(ri.x - le.x) + (ri.y - le.y)*(ri.y - le.y));}}

求解过程：

/*** 使用蛮力法求解最短点距* @param list 点列表* @param begin 开始索引* @param end 结束索引* @return 最短点距*/private static Object[] simDistance(Point[] list, int begin, int end) {//存储最近点对及距离Object[] result = new Object[3];result[0] = Double.MAX_VALUE;for(int i = begin; i <= end; i++) {for(int j= i+1; j <= end; j++) {//求解每一对点的距离double distance = Point.distance(list[i],list[j]);if((double)result[0] >= distance) {result[0] = distance;result[1] = list[i];result[2] = list[j];}}}return result;}

此时，时间复杂度为：T(n) = O(n2)

分治法求解

求解步骤

划分子问题

将问题化为相等的两份

先将子问题按照横坐标的大小进行排序，然后求出中间值，将其分为两部分

求解子问题

递归的对两个子问题进行求解

①先求出左半部分的最短距离（第一对点）

②再求出右半部分的最短距离（第二对点）

③求得中间部分的最短距离（第三对点）

合并问题的解

比较三个值中最小的一个，将其返回

重点问题（第三对点的求解）

先求得第一对点和第二对点，得出两者最小值d，这时S1和S2中任意点对之间的距离小于或等于d，但S1、S2交界的垂直带形区（由所有与中轴线的x坐标值相差不超过d的点构成）中的点对之间的距离有可能小于d

若在PL中存在一个点s，则PR 中需要计算距离点的y轴坐标一定位于区间[s.y-d, s.y+d]之间，即这样的点一定落在一个d×2d的矩形区域内

根据鸽舍原理：将该区域分割为d/2 * 2d/3的六块大小相同的区域

设两个点同时存在于一块小区域内，此时最远点距为√（(d/2)2+（2d/3)2) =√ 25d2/36 < d2

这与d的定义（S1和S2中任意点对之间的距离小于或等于d）不符，即点s所需要计算点最多有6个

即该步骤可在线性时间内完成

实现代码

提供给外界的方法：

/*** 使用分治法求解最近点对问题* @param list 所有点数组* @return 最短距离*/public static Object[] seekDistance(Point[] list) {//将数组中点按x进行排序quiSort(list, 0, list.length-1, "x");//递归求解return ClosestDistance(list,0,list.length-1);}

主要计算方法：

/*** 使用二分法进行递归求出最短距离* @param xArray x轴排列* @param yArray y轴排列* @param begin x开始索引* @param end x结束索引* @return 最短距离*/private static Object[] ClosestDistance(Point[] xArray, int begin, int end) {Object[] result = null;//若此时点数少于四个，则使用蛮力法求解if(end - begin + 1 < 4) {return simDistance(xArray, begin, end);}//求出中间值int midIndex = (begin+end)/2;//使用二分法对左半部分求解Object[] minLeft = ClosestDistance(xArray, begin, midIndex);//对右半部分求解Object[] minRight = ClosestDistance(xArray, midIndex+1, end);//求出两边所求出的距离最小值if((double)minLeft[0] < (double)minRight[0]) {result = minLeft;}else {result = minRight;}//取出最短距离double minDistance = (double)result[0];//根据最小值数组中划分出垂直带形区 //建立两个个数组将该区域内的数据进行收纳//而根据鸽舍原理得出每一个点所需要计算的最多有6个ArrayList<Point> lList = new ArrayList<Point>();ArrayList<Point> rList = new ArrayList<Point>();int index = begin;while(xArray[index].x <= xArray[midIndex].x - minDistance) {index++;}while(xArray[index].x <= xArray[midIndex].x) {//处在左半部分的点lList.add(xArray[index]);index++;}while(xArray[index].x <= xArray[midIndex].x + minDistance && index <= end) {//处在右半部分的点rList.add(xArray[index]);index++;}//转化为数组Point[] lArray = new Point[lList.size()];Point[] rArray = new Point[rList.size()];lList.toArray(lArray);rList.toArray(rArray);//按照y进行排序quiSort(lArray, 0, lArray.length-1, "y");quiSort(rArray, 0, rArray.length-1, "y"); //计算第三对点距离double minMid = minDistance ;for(int i=0; i< lArray.length; i++){for(int j=0; j< rArray.length; j++) {//判断,由于此时y是有序的,可根据y的差值判断是否需要计算//当y值太小时，直接进行下一次循环if((lArray[i].y - rArray[j].y) < 0 - minDistance) {continue;}//两个点距离大于最小值时,直接跳出此层循环if((lArray[i].y - rArray[j].y) > minDistance) {break;}//选出最小值minMid = Point.distance(lArray[i], rArray[j]);if(minMid < minDistance) {minDistance = minMid;//存储距离及点对result[0] = minDistance;result[1] = lArray[i];result[2] = rArray[j];}}} return result;}

快排方法：

/*** 快速排序* @param list 需要排序的行列* @param i 数据开始索引* @param j 数据结束索引* @param type 需要排序的坐标类型* @return 排序的结果*/private static Point[] quiSort(Point[] list, int i, int j, String type) {//长度大于一时，使用递归进行排序（相当于一个二叉树）if(i < j) {int mid = onceQuiSort(list, i, j, type);//左边排序,需使得mid-1，不然会死循环quiSort(list, i, mid-1, type);//右边排序quiSort(list, mid+1, j, type);}return list;}/*** 一次快速排序* @param list 需要排序的行列* @param i 头指针* @param j 尾指针* @param type 需要排序的坐标类型* @return 排序结束中间指针*/private static int onceQuiSort(Point[] list, int i, int j, String type) {//取出第一位元素作为界点if(type.equals("x")) {Point point = list[i];while(i != j) { while(i != j && list[j].x >= point.x) {j--;}list[i] = list[j];while(i != j && list[i].x <= point.x) {i++;}list[j] = list[i];}list[i] = point;}else {Point point = list[i];while(i != j) { while(i != j && list[j].y >= point.y) {j--;}list[i] = list[j];while(i != j && list[i].y <= point.y) {i++;}list[j] = list[i];}list[i] = point;} return i;}

测试方法:

Point[] list = new Point[10];list[0] = new Point(4,10);list[1] = new Point(3,7);list[2] = new Point(9,7);list[3] = new Point(3,4);list[4] = new Point(5,6);list[5] = new Point(5,4);list[6] = new Point(6,3);list[7] = new Point(8,1);list[8] = new Point(3,0);list[9] = new Point(1,6);Object[] result = seekDistance(list);System.out.println("最短距离为："+(double)result[0]);System.out.println("所对应的点对为："+(Point)result[1]+"、"+(Point)result[2]);