0007算法笔记——【分治法】最接近点对问题

一、最接近点对问题（一维）一、最接近点对问题（一维）最接近点对问题:给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。

此时S中的n个点退化为x轴上的n个实数x1,x2,..,x n。

最接近点对即为这n个实数中相差最小的2个实数。

2、分析将所给的平面上n个点的集合S分成2个子集S1和S2，每一个子集中约有n/2个点，·然后在每一个子集中递归地求其最接近的点对。

S1和S2的最接近点对未必就是S的最接近点对，若是组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决。

可是，若是这2个点别离在S1和S2中，则对于S1中任一点p，S2中最多只有n/2个点与它组成最接近点对的候选者，仍需做n2/4次计算和比较才能肯定S的最接近点对。

因此，依此思路，归并步骤耗时为O(n2)。

整个算法所需计算时间T(n)应知足:T(n)=2T(n/2)+O(n2)它的解为T(n)=O(n2)3、伪代码随机Randomfloat Random(){float result=rand()%10000;return result*;}返回最大、最小float Max OR Min(float s[],int p,intq)序实现#include<>#include<iostream>#include<cmath>using namespace std;const int M=50;D=i;X[i].x=Random();X[i].y=Random();c out<<"("<<X[i].x<<","<<X[i].y<<") ";}PointX a;PointX b;float d;Cpair2(X,number_used,a,b,d);cout<<endl;cout<<"the closest pair is ("<<<<","<<<<")和("<<<<","<<<<") "<<endl;cout<<"the min distance is "<<d<<endl;return 0;}float Random(){float result=rand()%10000;return result*;}=i;Y[i].x=X[i].x;Y[i].y=X[i].y;}PointY*tmpy=new PointY[n];MergeSort(Y,tmpy,0,n-1);PointY*Z=new PointY[n];closest(X,Y,Z,0,n-1,a,b,d);delete []Y;delete []Z;return true;}void closest(PointX X[],PointY Y[],PointY Z[], int l, int r,PointX& a,PointX& b,float& d){i f(r-l==1){>m) Z[g++]=Y[i];else Z[f++]=Y[i]; closest(X,Z,Y,l,m,a,b,d);float dr;PointX ar,br;closest(X,Z,Y,m+1,r,ar,br,dr);if(dr<d){a=ar;b=br;d=dr;}Merge(Z,Y,l,m,r);-Y[t].x)<d){Z[k++]=Y[t];}-Z[s].y<d;j++){float dp=dis(Z[s],Z[j]);if(dp<d){d=dp;a=X[Z[i].p];b=X[Z[j].p];} } } }template <typename Type>void Merge(Type c[],Type d[], int l, int m, int r){i nt i=l,j=m+1,k=l;w hile((i<=m)&&(j<=r))if(c[i]<=c[j])d[k++]=c[i++];elsed[k++]=c[j++];if(i>m)for(int q=j;q<=r;q++)d[k++]=c[q];elsefor(int q=i;q<=m;q++)d[k++]=c[q];}template <typename Type>void MergeSort(Type a[], Type b[],int left, int right){ // a[]为待排序的数组，left，right为a数组的下标，b[]为临时存放排好序的临时数组i f(left<right){int i=(left+right)/2;//取中点MergeSort(a,b,left,i);MergeSort(a,b,i+1,right);Merge(a,b,left,i,right);//归并到数组bCopy(a,b,left,right);//复制回数组a }}template <typename Type>void Copy(Type a[],Type b[], int right,int left) {for(int i=right;i<=left;i++)a[i]=b[i];}运行情况：。

最近点对问题I.一维问题：一、问题描述和分析最近点对问题的提法是：给定平面上n个点，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。

严格的讲，最接近点对可能多于1对，为简单起见，只找其中的1对作为问题的解。

简单的说，只要将每一点与其它n-1个点的距离算出，找出达到最小距离的2点即可。

但这样效率太低，故想到分治法来解决这个问题。

也就是说，将所给的平面上n个点的集合S 分成2个子集S1和S2，每个子集中约有n/2个点。

然后在每个子集中递归的求其最接近的点对。

这里，关键问题是如何实现分治法中的合并步骤，即由S1和S2的最接近点对，如何求得原集合S中的最接近点对。

如果组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决，但如果这2个点分别在S1和S2中，问题就不那么简单了。

下面的基本算法中，将对其作具体分析。

二、基本算法假设用x轴上某个点m将S划分为2个集合S1和S2，使得S1={x∈S|x<=m}；S2={x ∈S|x>m}。

因此，对于所有p∈S1和q∈S2有p<q。

递归的在S1和S2上找出其最接近点对{p1，p2}和{q1，q2}，并设d=min{|p1-p2|,|q1-q2|}。

由此易知，S中的最接近点对或者是{p1，p2}，或者是{q1，q2}，或者是某个{p3，q3}，其中p3∈S1且q3∈S2。

如下图所示：S1 S2p1 p2 p3 q1 q2 q3图1 一维情形的分治法注意到，如果S的最接近点对是{p3，q3}，即|p3-q3|<d，则p3和q3两者与m的距离不超过d，即|p3-m|<d，|q3-m|<d。

也就是说，p3∈(m-d，m],q3∈(m，m+d]。

由于每个长度为d的半闭区间至多包含S1中的一个点，并且m是S1和S2的分割点，因此(m-d，m]中至少包含一个S中的点。

同理，(m，m+d]中也至少包含一个S中的点。

平⾯最接近点对问题（分治法）头⽂件部分：（1）数据结构部分：//涉及的数据结构#ifndef DATASET_H#define DATASET_Hstruct point{ //点结构double x, y;};#endif（2）函数声明部分：//函数头⽂件//=======================================#ifndef FUNC_H#define FUNC_H#include "dataset.h"double closest_distance(point s[], int low, int high, point rec[]);double Distance(point a, point b);bool comp_x(point a, point b);bool comp_y(point a, point b);#endif源⽂件部分：（1）函数实现部分：//求解最近距离的函数实现#include "dataset.h"#include <math.h>#include <algorithm>using namespace std;double Distance(point a, point b) //计算两点距离{return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) - (a.y - b.y));}bool comp_x(point a, point b) //按x升序判别函数{return a.x < b.x;}bool comp_y(point a, point b) //按y升序判别函数{return a.y < b.y;}//函数实现：rec[]存储最接近点对；double closest_distance(point s[], int low, int high, point rec[]){double d1, d2, d3, d;int mid, i, j, index;double x1, y1, x2, y2; //记录最近的点对point *P = new point[high - low + 1];point temp_1[2], temp_2[2], temp_3[2];if (high - low == 1) //两个点时的情况{rec[0].x = s[low].x; rec[0].y = s[low].y;rec[1].x = s[high].x; rec[1].y = s[high].y;return Distance(s[low], s[high]);}if (high - low == 2) //三个点时的情况{d1 = Distance(s[low], s[low + 1]);d2 = Distance(s[low + 1], s[high]);d3 = Distance(s[low], s[high]);if ((d1 <= d2) && (d1 <= d3)) //这⾥在判断三种情况时，第⼆种情况没必要使⽤(d2<d3)&&(d2<d1),相较更繁琐了；{rec[0].x = s[low].x; rec[0].y = s[low].y;rec[1].x = s[low + 1].x; rec[1].y = s[low + 1].y;return d1;}else if (d2 < d3){rec[0].x = s[low + 1].x; rec[0].y = s[low + 1].y;rec[1].x = s[high].x; rec[1].y = s[high].y;return d2;}else{rec[0].x = s[low].x; rec[0].y = s[low].y;rec[1].x = s[high].x; rec[1].y = s[high].y;return d3;}}mid = (low + high) / 2;d1 = closest_distance(s, low, mid, rec);temp_1[0] = rec[0];temp_1[1] = rec[1];d2 = closest_distance(s, mid + 1 ,high, rec);temp_2[0] = rec[0];temp_2[1] = rec[1];if (d1 <= d2){d = d1;rec[0] = temp_1[0];rec[1] = temp_1[1];}else{d = d2;rec[0] = temp_2[0];rec[1] = temp_2[1];}index = 0;for (i = mid; (i >= low) && ((s[mid].x - s[i].x) < d); i--){P[index++] = s[i]; //点集合P1}for (i = mid + 1; (i <= high) && ((s[i].x - s[mid].x) < d); i++){P[index++] = s[i]; //点集合P2}sort(P, P + index, comp_y); //升序排列for (i = 0; i < index; i++){for (j = i + 1; j < index; j++){if ((P[j].y - P[i].y) >= d)break;else{d3 = Distance(P[i], P[j]);if (d3 < d){rec[0].x = P[i].x; rec[0].y = P[i].y;rec[1].x = P[j].x; rec[1].y = P[j].y;d = d3;}}}}delete []P; //注意动态内存的删除⽅式，防⽌内存泄漏return d;}（2）主函数部分：//2018_02_24//使⽤分治法求解⼆维平⾯最接近点问题//============================================================= #include <iostream>#include <math.h>#include <algorithm>#include "dataset.h"//数据结构实现放在这个头⽂件中#include "func.h"//函数声明的头⽂件using namespace std;int main(void){point p[10]; //设定点的集合int n;double minDist;cout << "输⼊点的个数：\n";cin >> n;cout << "输⼊点集：(x , y) \n";for (int i = 0; i < n; i++)cin >> p[i].x >> p[i].y;sort(p, p + n, comp_x); //对输⼊的点先进⾏排序point index[2];minDist = closest_distance(p, 0, n - 1, index);cout << "最⼩距离点对为：(" << index[0].x << "," << index[0].y << "),(" << index[1].x << "," << index[1].y << ")"; cout << "最⼩距离为：\n" << minDist;system("pause");return0;}最后，结果如下：。

分治算法知识点总结一、基本概念分治算法是一种递归的算法，其基本思想就是将原问题分解成多个相互独立的子问题，然后分别解决这些子问题，最后将子问题的解合并得到原问题的解。

分治算法的核心思想可以用一句话概括：分而治之，分即是将原问题分解成若干个规模较小的子问题，治即是解决这些子问题，然后将子问题的解合并起来得到原问题的解。

分治算法通常包括三个步骤：（1）分解：将原问题分解成若干个规模较小的子问题；（2）解决：递归地解决这些子问题；（3）合并：将子问题的解合并起来得到原问题的解。

分治算法的典型特征包括递归和合并。

递归指的是将原问题分解成若干个规模较小的子问题，然后递归地解决这些子问题；合并指的是将子问题的解合并得到原问题的解。

通常来说，分治算法的递归实现方式很容易编写，但有时可能会面临大量的重复计算，因此需要合并操作来避免这种情况。

二、原理分治算法的原理可以通过一个简单的例子来说明。

我们以计算数组中的最大值为例，具体的步骤如下：（1）分解：将数组分解成两个规模相等的子数组；（2）解决：递归地在这两个子数组中分别找到最大值；（3）合并：比较这两个子数组的最大值，得到原数组的最大值。

从这个例子可以看出，分治算法将原问题分解成两个子问题：分别在左边子数组和右边子数组中找到最大值，然后将这两个子问题的解合并起来得到原数组的最大值。

这种将问题分解成若干个规模较小的子问题，然后合并子问题的解得到原问题的解的方法正是分治算法的核心原理。

分治算法的优势在于它可以将原问题分解成多个规模较小的子问题，然后并行地解决这些子问题，最后合并子问题的解得到原问题的解。

这种并行的设计思路使得分治算法非常适合于并行计算，能够有效地提高计算效率。

三、应用分治算法在计算机科学领域有着广泛的应用，包括排序、搜索、图论、动态规划等多个方面。

下面我们将以排序算法和搜索算法为例，来介绍分治算法在实际应用中的具体情况。

1. 排序算法排序算法是计算机科学领域中一个重要的问题，分治算法在排序算法中有着广泛的应用。

⽤分治法解决最近点对问题：python实现 最近点对问题:给定平⾯上n个点，找其中的⼀对点，使得在n个点的所有点对中，该点对的距离最⼩。

需要说明的是理论上最近点对并不⽌⼀对，但是⽆论是寻找全部还是仅寻找其中之⼀，其原理没有区别，仅需略作改造即可。

本⽂提供的算法仅寻找其中⼀对。

解决最近点对问题最简单的⽅法就是穷举法，这样时间复杂度是平⽅级，可以说是最坏的策略。

如果使⽤分治法，其时间复杂度就是线性对数级，这样⼤⼤提⾼了效率。

⾸先⽤分治法解决该问题的基本思路可以参考 /lishuhuakai/article/details/9133961 ，说的很详细，但⼤致思路就是先根据x轴把所有点平分，然后分别在每⼀部分寻找最近点对，最后通过⽐较选⼀个最⼩的。

当然其中最核⼼的地⽅是跨域求距离，原⽂写的很清楚，在此就不再赘述了。

以下是代码：from math import sqrtdef nearest_dot(s):len = s.__len__()left = s[0:len/2]right = s[len/2:]mid_x = (left[-1][0]+right[0][0])/2.0if left.__len__() > 2: lmin = nearest_dot(left) #左侧部分最近点对else: lmin = leftif right.__len__() > 2: rmin = nearest_dot(right) #右侧部分最近点对else: rmin = rightif lmin.__len__() >1: dis_l = get_distance(lmin)else: dis_l = float("inf")if rmin.__len__() >1: dis_2 = get_distance(rmin)else: dis_2 = float("inf")d = min(dis_l, dis_2) #最近点对距离mid_min=[]for i in left:if mid_x-i[0]<=d : #如果左侧部分与中间线的距离<=dfor j in right:if abs(i[0]-j[0])<=d and abs(i[1]-j[1])<=d: #如果右侧部分点在i点的(d,2d)之间if get_distance((i,j))<=d: mid_min.append([i,j]) #ij两点的间距若⼩于d则加⼊队列if mid_min:dic=[]for i in mid_min:dic.append({get_distance(i):i})dic.sort(key=lambda x: x.keys())return (dic[0].values())[0]elif dis_l>dis_2:return rminelse:return lmin# 求点对的距离def get_distance(min):return sqrt((min[0][0]-min[1][0])**2 + (min[0][1]-min[1][1])**2)def divide_conquer(s):s.sort(cmp = lambda x,y : cmp(x[0], y[0])) nearest_dots = nearest_dot(s)print nearest_dots测试⼀下，⽐如说要找这些点中最近的⼀对s=[(0,1),(3,2),(4,3),(5,1),(1,2),(2,1),(6,2),(7,2),(8,3),(4,5),(9,0),(6,4)]运⾏⼀下divide_conquer(s)，最终打印出[(6, 2), (7, 2)]，Bingo。

《算法设计与分析》实验报告学号：姓名：日期：得分：一、实验内容：分治法和蛮力法求最近对问题及其时间复杂度比较。

二、所用算法的基本思想及复杂度分析：1.蛮力法求最近对问题:1）基本思想：分别计算每一对点之间的距离，然后找出距离最小的那一对，为了避免对同一对点计算两次距离，只考虑ji<的那些点对()j i P P,.2)复杂度分析：对于此算法，主要就是算两个点的欧几里得距离。

注意到在求欧几里得距离时，避免了求平方根操作，其原因是:如果被开方的数越小，则它的平方根也越小。

所以复杂度就是求平方，求执行次数为: nnT==；即时间复杂度为)-n)1)O(((2n)O。

(2n2.分治法求最近对问题：1）基本思想:用分治法解决最近点对问题，就是将一个问题分解两个子问题，然后递归处理子问题,然后合并。

可能两个点在每个子问题中，也可能两个点分别在两个子问题中,就这两种情况。

则基本过程为:找一条中垂线m(坐位S集合x坐标的中位数）把n个元素分成左右两部分元素,然后分别求得两边的最短距离1d ,2d ，然后取两者中的最小者记为d ，在中线两边分别取d 的距离，记录该距离范围内点的个数，中线左边有L 个元素，右边有R 个元素，分别将两边的点按y 坐标升序排列,在左边集合中每一个点，找右边集合的点，找到与之距离小于d的点，更新最短距离，直到循环结束,即可求出最短距离.2)复杂度分析:应用分治法求解含有n 个点的最近对问题，其时间复杂性可由递推式表示：)()2/(*2)(n f n T n T +=。

由以上分析:合并子问题的解的时间)1()(O n f =。

进而可得分治法求最近对问题的时间复杂度为：)log ()(2n n O n T =.三、源程序及注释：#include<iostream>＃include 〈cstring 〉＃include 〈cmath>＃include 〈algorithm>＃include<time.h>using namespace std ；＃define eps 1e-8#define MAXN 10000000#define N 5000struct Point｛double x,y;｝；Point S[N*2],S1[N］,S2[N］,P1[N］,P2[N]；double Distance（Point a,Point b)｛return sqrt((a。

问题场景：在应用中，常用诸如点、圆等简单的几何对象代表现实世界中的实体。

在涉及这些几何对象的问题中，常需要了解其邻域中其他几何对象的信息。

例如，在空中交通控制问题中，若将飞机作为空间中移动的一个点来看待，则具有最大碰撞危险的2架飞机，就是这个空间中最接近的一对点。

这类问题是计算几何学中研究的基本问题之一。

问题描述：给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。

严格地说，最接近点对可能多于1对。

为了简单起见，这里只限于找其中的一对。

1、一维最接近点对问题算法思路：这个问题很容易理解，似乎也不难解决。

我们只要将每一点与其他n-1个点的距离算出，找出达到最小距离的两个点即可。

然而，这样做效率太低，需要O(n^2)的计算时间。

在问题的计算复杂性中我们可以看到，该问题的计算时间下界为Ω(nlogn)。

这个下界引导我们去找问题的一个θ(nlogn)算法。

采用分治法思想，考虑将所给的n个点的集合S分成2个子集S1和S2，每个子集中约有n/2个点，然后在每个子集中递归地求其最接近的点对。

在这里，一个关键的问题是如何实现分治法中的合并步骤，即由S1和S2的最接近点对，如何求得原集合S中的最接近点对，因为S1和S2的最接近点对未必就是S的最接近点对。

如果组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决。

但是，如果这2个点分别在S1和S2中，则对于S1中任一点p，S2中最多只有n/2个点与它构成最接近点对的候选者，仍需做n^2/4次计算和比较才能确定S的最接近点对。

因此，依此思路，合并步骤耗时为O(n^2)。

整个算法所需计算时间T(n)应满足:T(n)=2T(n/2)+O(n^2)。

它的解为T(n)=O(n^2)，即与合并步骤的耗时同阶，这不比用穷举的方法好。

从解递归方程的套用公式法，我们看到问题出在合并步骤耗时太多。

这启发我们把注意力放在合并步骤上。

设S中的n个点为x轴上的n个实数x1,x2,..,xn。

最接近点对问题的算法分析在⼆维平⾯上的n个点中，如何快速的找出最近的⼀对点，就是最近点对问题。

⼀种简单的想法是暴⼒枚举每两个点，记录最⼩距离，显然，时间复杂度为O(n^2)。

在这⾥介绍⼀种时间复杂度为O(nlognlogn)的算法。

其实，这⾥⽤到了分治的思想。

将所给平⾯上n个点的集合S分成两个⼦集S1和S2，每个⼦集中约有n/2个点。

然后在每个⼦集中递归地求最接近的点对。

在这⾥，⼀个关键的问题是如何实现分治法中的合并步骤，即由S1和S2的最接近点对，如何求得原集合S中的最接近点对。

如果这两个点分别在S1和S2中，问题就变得复杂了。

为了使问题变得简单，⾸先考虑⼀维的情形。

此时，S中的n个点退化为x轴上的n个实数x1，x2，...，xn。

最接近点对即为这n个实数中相差最⼩的两个实数。

显然可以先将点排好序，然后线性扫描就可以了。

但我们为了便于推⼴到⼆维的情形，尝试⽤分治法解决这个问题。

假设我们⽤m点将S分为S1和S2两个集合，这样⼀来，对于所有的p(S1中的点)和q(S2中的点)，有p<q。

递归地在S1和S2上找出其最接近点对{p1,p2}和{q1,q2}，并设d = min{ |p1-p2| , |q1-q2| }由此易知，S中最接近点对或者是{p1,p2}，或者是{q1,q2}，或者是某个{q3,p3}，如下图所⽰。

如果最接近点对是{q3,p3}，即|p3-q3|<d，则p3和q3两者与m的距离都不超过d，且在区间(m-d,d]和(d,m+d]各有且仅有⼀个点。

这样，就可以在线性时间内实现合并。

此时，⼀维情形下的最近点对时间复杂度为O(nlogn)。

在⼆维情形下，类似的，利⽤分治法，但是难点在于如何实现线性的合并？由上图可见，形成的宽为2d的带状区间，最多可能有n个点，合并时间最坏情况下为n^2,。

但是，P1和P2中的点具有以下稀疏的性质，对于P1中的任意⼀点，P2中的点必定落在⼀个d X 2d的矩形中，且最多只需检查六个点（鸽巢原理）。

求两组点之间的最近点对实验总结在计算几何学和算法设计中，求两组点之间的最近点对是一个重要且常见的问题。

在这篇文章中，我将从简到繁地探讨这个主题，深入分析求解最近点对的算法，并进行实验总结，以便读者能更深入地理解这一概念。

一、什么是最近点对问题？最近点对问题是指在一个平面上给定n个点，要求在这些点中找到距离最近的两个点。

这个问题在实际中有着广泛的应用，比如计算机视觉中的物体识别、无人驾驶车辆的障碍物检测等都涉及到最近点对的计算。

设计高效的算法来解决最近点对问题具有重要意义。

二、最近点对的暴力解法最简单的方法是通过遍历所有点对，计算它们之间的距离，并找到最小值。

这种暴力解法的时间复杂度为O(n^2)，空间复杂度为O(1)，虽然简单易懂，但对于大规模的数据集来说效率较低。

三、分治法解决最近点对问题分治法是解决最近点对问题的常见方法，其基本思想是将点集分成两个子集，分别求解最近点对，然后再找出整个点集的最近点对。

在这个过程中需要用到分治、筛选和合并三个步骤。

具体算法流程如下：1. 将点集按照x坐标排序，找到中间线将点集分成左右两个子集。

2. 递归求解左右子集的最近点对。

3. 筛选出距离中线距离小于当前最近距离的点，将它们按照y坐标排序。

4. 在筛选后的点集中，以每个点为中心，向上下各取6个点。

5. 计算这些点之间的距离，更新最近距离。

6. 合并左右子集的结果，得到最终的最近点对。

使用分治法解决最近点对问题的时间复杂度为O(nlogn)，效率较高，适用于大规模数据集。

四、实验总结及个人观点在进行最近点对的实验过程中，我发现分治法在处理大规模数据集时具有明显的优势，其算法设计合理、程序实现简单高效。

对于中等规模的数据集，暴力解法也能够得到较好的结果，但对于大规模数据集来说效率明显低于分治法。

我个人认为在解决最近点对问题时，应优先考虑使用分治法，并且可以根据数据规模选择不同的算法来达到更高的效率。

总结来说，求两组点之间的最近点对是一个重要且常见的问题，在实际应用中具有广泛的意义。

最接近点对问题_分治法⼀、问题描述给定平⾯上的n个点，找其中的⼀对点，使得在n个点组成的所有点对中该点对间的距离最⼩。

⼆、解题思路及所选算法策略的可⾏性分析思路：利⽤分治法来解决问题。

递归⼦结构求最接近点对总体可分为⼏个步骤：1、当问题规模⼩于20，直接求解最⼩点对2、将n个点组成的集合S分成2个⼦集S1和S23、递归求出两个⼦集中的最接近点对并⽐较出最⼩点对，记录距离dmin4、以X坐标为基准找到所有点中线，在中线附近找出相距可能⼩于dmin的点对点，记录于S3和S45、求S3和S4每点对距离，和dmin进⾏⽐较，求解最接近点对策略可⾏性分析：设直线l上有2m个点，以m为中点将l分割成两条线段dl,dr，然后求出dl和dr这两点条线段中的最⼩点距d1,d2，此时d=min{d1,d2}，再通过计算出dl线段的中最⼤点与dr线段中的最⼩点之间的距离D，最⼩距离则为min{d,D}.⼆维情况与此相似，最⼤的区别只是对于中线位置的点，⼆维情况只是针对中线旁好多可能点，再在Y轴⽅向上进⾏点的筛选，以减少平⽅计算次数。

三、伪代码描述及复杂度分析Public static double closestPoint(S){1、⾸先，递归结束条件，当数组长度在⼀定范围内时直接求出最近点，蛮⼒求解2、求所有点在X坐标中的中位数midX3、以midX为界将所有点分成两组分别存放在两个表中4、将两张表转化为数组类型，并分别按X坐标升序排列5、求S1中的最近距离的两个点6、求S2中的最近距离的两个点7、求两最近距离的最⼩值8、在S1、S2中收集距离中线⼩于d1的点，分别存放于两个表中9、分别将表T3、T4转换为数组类型的S3、S4，并将其分别按Y坐标升序排列10、求解S3、S4两者之间可能的更近（相⽐于d1）距离 , 以及构成该距离的点}复杂度分析：设算法耗时T(n)。

算法第1步、第2步、第3步和第8步⽤了O(n)时间。

最接近点对问题算法
最接近点对问题是指在平面上给定N个点，找出其中距离最
近的两个点的距离。

可以使用以下算法来解决最接近点对问题：
1. 将所有点按照水平或垂直坐标排序，以便可以更方便地进行后续操作。

2. 将所有点分为两个大致相等的集合，分别称为左集合和右集合。

3. 递归地在左集合和右集合中找出最小距离的点对。

4. 取两个集合中最小距离的点对中较小的距离minDistance。

5. 在以水平坐标为准的线段中，确认是否存在两个点，它们的横坐标之差小于minDistance，并计算它们的距离。

6. 在以垂直坐标为准的线段中，确认是否存在两个点，它们的纵坐标之差小于minDistance，并计算它们的距离。

7. 取步骤5和步骤6中距离的最小值，记为delta。

8. 在左集合和右集合中，找出间距水平线的范围内的点，并按照纵坐标排序。

9. 使用二重循环，依次计算两个集合中的相邻点对之间的距离，直到纵坐标的差大于等于delta。

10. 比较得到的距离和minDistance，取较小的值作为最终的最小距离。

以上算法的时间复杂度为O(nlogn)，其中n为点的数量。

实验四求最近点对算法1.算法设计思路：设共有n个点，找其中距离最近的两点及其距离。

（1）蛮力法：蛮力法的思路是把所有点之间距离比较找出中间最小的。

先假设最短距离是第一个元素和第二个元素的距离，然后求第一个元素与其后的（n-1）个元素各自的距离，若比之前记录的最短距离小则记录当前值···求第i个元素与其后的（n-i）个元素各自的距离，记录之前所得到的所有距离中的最小值，直到计算到第（n-1）个元素与第n个元素的距离，此时记录的距离即为这n个元素中的最短距离。

（2）分治法：分治法是把一个大的问题划分成相似的小问题，采用递归的思想。

找中线把n个元素分成左右两部分元素分别求得两边的最短距离，然后取两者中的最小者记为l，在中线两边分别取l的距离，记录该距离范围内点的个数，中线左边有L个元素，右边有R个元素，求左边元素到右边元素的距离看其是否小于之前记录的最短距离，小则记录下来，此时的右边元素只取y值和左边元素y值距离小于l的（减少循环次数）。

循环结束即可找到最小的距离。

2.程序代码：#include<iostream>#include<cstdlib>#include<ctime>#include<cmath>using std::cout;using std::endl;#define N 5int x[N],y[N],record[N]; //产生原始点数据，x坐标放在x[]中，y坐标放在y[]中。

double Min;//////////////////////////产生随机数组/////////////////////////////void randnum(){int i;srand(time(0));for (i=0;i<N;i++){x[i]=rand()%N;cout<<x[i]<<' ';}cout<<endl;for (i=0;i<N;i++){y[i]=rand()%N;cout<<y[i]<<' ';}cout<<endl;}//////////////////////////////交换数组元素/////////////////////////// void swap(int & a, int & b){int temp=a;a=b;b=temp;}///////////////////////////////求平方///////////////////////////////////int square(int x){return x*x;}/////////////////////////////////////求两点之间距离////////////////////double lengthf(int x1,int y1,int x2,int y2){return sqrt(square(x1-x2)+square(y1-y2));}//////////////////////////////////求两者中最小者////////////////////// double min(double a,double b){if (a>=b)return b;elsereturn a;}////////////////////////////对平面数组排序//////////////////////////// void sort(int A[]){int i,j;for (i=0;i<N;i++)record[i]=i;for (j=1;j<N;j++){i=j;while (i>=0&&A[i]<A[i-1]){swap(A[i],A[i-1]);swap(record[i-1],record[i]); //得到x排序后对应的原y的坐标i--;}}cout<<"排序后的元素数组："<<endl;for (i=0;i<N;i++)cout<<A[i]<<' ';cout<<endl;for (i=0;i<N;i++)cout<<record[i]<<' ';cout<<endl;}///////////////////////////穷举法找最小点对///////////////////////////////double exhaustion(){int i,j,k1,k2;double num;double length;num=10000;k1=k2=-1;for (j=0;j<N-1;j++){for (i=j+1;i<N;i++){length=lengthf(x[i],y[i],x[j],y[j]);if (length<num){num=length;k1=i;k2=j;}}}cout<<"平面数组最短距离是："<<endl;cout<<"min="<<num<<endl;cout<<"对应数组下标及点坐标为："<<endl;cout<<"i="<<k1<<','<<k2<<endl;cout<<"(x1,y1)="<<'('<<x[k1]<<','<<y[k1]<<')'<<endl<<"(x2,y2)="<<'('<<x[k2]<<','<<y[k2]<<')' <<endl;return num;}////////////////////////////////////分治法////////////////////////////////*************************************************************************/double merge(int left,int right){double mlength;if (right==left)mlength=10e-6;if (right==left+1)mlength=lengthf(x[right],y[record[right]],x[left],y[record[left]]); //两个点时求最小值if (right-left==2)mlength=min(min(lengthf(x[right-1],y[record[right-1]],x[left],y[record[left]]),lengthf(x[right],y[re cord[right]],x[left+1],y[record[left+1]])),lengthf(x[right],y[record[right]],x[left],y[record[left]]));//三个点时求最大值return mlength;}double divide(int left,int right){if (right-left<=2){Min=merge(left,right);}else{double l1,l2,mi; //l1记录划分区域后左半面最小距离，l2记录右半面最小距离，min为两者中较小者，m为全部中的最小者int rem1,rem2,l; //记录获得最短距离对应的两个点//int il,jl,ir,jr;int i,j;int R,L;R=L=0; //记录划分小区域后的左半块和右半块个有多少元素l1=l2=Min=100;l=(right-left+1)/2-1; //中线位置///////////////////////////////////////////////////l1=divide(left,l);l2=divide(l+1,right);if (l1<l2){Min=l1;//cout<<"两半面最短距离是："<<min;else{Min=l2;//cout<<"两半面最短距离是："<<min;}///////////////////得到右半块元素数R//cout<<"min="<<min<<endl;for (i=l+1;i<N;i++){if (x[i]-x[l]<=Min)R++;else break;}//cout<<"R="<<R<<endl;/////////////////////得到左半块元素数Lfor (i=l;i>=0;i--){if (x[l]-x[i]<=Min)L++;else break;}//cout<<"L="<<L<<endl;if (L!=0&&R!=0){for (i=l-L+1;i<=l;i++)for (j=l+1;j<=l+R;j++){if (y[record[j]]-y[record[i]]<Min||-Min<y[record[j]]-y[record[i]]){mi=lengthf(x[i],y[record[i]],x[j],y[record[j]]);if (mi<Min){Min=mi;rem1=i;rem2=j;}}}// cout<<"min="<<min<<endl;//cout<<"rem1="<<rem1<<endl<<"rem2="<<rem2<<endl;}return Min;}/***********************************************************************///////////////////////////////////主函数///////////////////////////////////int main(){//double a;randnum();cout<<"***************************遍历法*************************"<<endl;exhaustion();cout<<"***************************分治法*************************"<<endl;sort(x);divide(0,N-1);cout<<"元素组中最短距离为："<<endl;cout<<"min="<<Min<<endl;return 0;}3.实验数据及实验结果：实验数据：随机产生的五个点坐标分别为：（1，3），（4，2），（3，0），（2，0），（0，3）实验结果：用蛮力法得到平面数组最短距离为：min=1用分治法得到平面数组最短距离为：min=14.实验总结：从本次试验中得到的领悟是：分治法事把问题分解成两个相似小问题，子问题和原来的大问题解决方法一样所以可以用递归，分治法重要是找到递归出口，什么时候递归结束，一般都有元素个数的限制。

分治最近点对证明过程分治算法是一种将问题分解为更小的子问题，并通过递归解决子问题，最后将子问题的解合并起来得到原问题解的方法。

最近点对问题是指在一个给定的点集中，找到距离最近的两个点的问题。

在本文中，我们将使用分治算法来解决最近点对问题，并对其正确性进行证明。

我们需要明确最近点对问题的定义。

给定一个点集P，我们需要找到其中两个点p和q，使得它们的距离d(p,q)最小。

距离可以使用欧氏距离或其他度量方式来定义。

我们的目标是设计一个高效的算法来解决这个问题。

分治算法的基本思想是将问题分解为更小的子问题，并通过递归解决子问题。

在最近点对问题中，我们可以将点集P划分为两个较小的子集P1和P2，分别包含点集P的前一半和后一半的点。

然后，我们分别在P1和P2中递归地找到最近点对。

假设在P1和P2中分别找到的最近点对是(p1,q1)和(p2,q2)。

接下来，我们需要考虑P1和P2之间的最近点对。

我们可以观察到，P1和P2中的点到分割线的距离不能超过d1和d2，其中d1和d2分别是P1和P2中找到的最近点对的距离。

因此，我们只需要考虑距离分割线小于d的点。

我们可以将P1和P2按照x轴坐标排序，并找到中间点mid。

然后，我们可以构建一个矩形区域，将其划分为两个部分，分别包含P1和P2的点。

我们只需要在这个矩形区域中找到距离分割线小于d 的点对。

在这个矩形区域中，我们可以按照y轴坐标排序点，并使用滑动窗口的方法来找到距离最近的点对。

具体来说，我们可以从矩形区域的顶部开始，依次考虑每个点，并计算它与后面d/d2个点的距离。

如果找到了距离更小的点对，则更新最近点对的距离。

我们将在P1、P2和跨越分割线的点中找到最近的点对，并返回其距离。

通过以上步骤，我们可以使用分治算法来解决最近点对问题。

接下来，我们将证明该算法的正确性。

我们可以观察到，如果两个点p和q是最近点对，并且它们在分割线的同一侧，那么它们必定在P1或P2中。