算法设计与分析——最近点对问题

目录 后记

前言

实际项目中，计算平面中多个点中最近的两点的距离是很常见的事，再上升一下，三维空间中计算最近两点间的距离(或者哪两个点最近）也是经常的事，故而，最近点对问题诞生。

问题背景：在平面直角坐标系中，存在许多点，计算众多点中最近两个点的距离。

一、算法思想分析

最近点对的暴力解法，一个一个的对比，形成一个n*n的二位距离数组，从而知道哪两个距离最近，其算法复杂度是n的平方级别，显然，在数据量较大时，这个方法不可取。

那么？怎么得出简单方法？这里有一个核心的分析，我有时候也不是很看得懂。

简易方法分析：

1. 首先，算法的核心策略是采用分治法，将平面分为左右两个平面。

2. 分别去计算左边平面和右边平面中最近两个点的距离（如果有需要，你可以记录点的位置，但本问题中暂无需求），然后进行比较，从而获取一个最近两点的距离D（这个时候的距离并不是最短的，只是左右两个平面内部比较的最短距离）。

3. 但是，只是获取了左右两边两个区域的最近点对距离就够了么？显然不够，我们原理上是将平面划分为左右两个平面，那么左右两个平面中的点到对方平面点的距离呢？例如：存在左边平面某个点到右边平面某个点的距离小于我们刚才划分平面后获取的两个平面内部的最近点对距离，那么这个时候，这个距离D就要易主了。

4. 这个时候，我们的问题仿佛就复杂了。想象一下，我们把左边的最近两个点距离算得为DL，右边的最近两个点距离算得为DR，那么两个区域各取一点之后获得的最短距离呢？因为只有这个距离获取了，我们才能获取到一个真正的最近点对。

5. 显然，左右两个区域内的最近点对很容易获取到，利用递归即可，那么这里我们记左右两个区域内最近点对距离为Dis（Dis=min(DR,DL)）。而跨边界（划分两个区域的边界）的最近点，通过数学计算，我们可以知道，我们需要计算的跨边界的点，是距边界的距离小于Dis。而算距离过于麻烦，我们则用x轴方向的间距小于Dis即可获取到一个计算区域。这个时候，我们获取到了一个我们需要计算的中间区域，是不是只要把这个区域全部的点之间的距离算一下并且比较获取最小值就行了呢？

可以，但没必要。在跨边界的地方，我们利用数学做了一个分析。分析之前，我们需要将中间区域的一个点与该区域其他所有的点计算距离并求最小，分析之后，只需要与六个点比较即可，比较完再让下一个点与其他六个点比较。具体的分析请见视频（数学处理具体分析视频）。

【北大公开课】 算法设计与分析 屈婉玲教授 （76p）

6. 从上述分析得知，每次我们取左边所有的点去与右边比较，其实我们只需要比较六个点，说得再明白一点，就是，虽然我们要遍历中间区域所有的点，但我们正在做了距离计算且进行比较获取最小距离的，其实只有六个点。为什么做这个分析呢？一是为了设计一个不比较的条件，二则是算法效率分析，我们显然降低了算法成本。每轮比较其实只有n的复杂级别了。

二、算法效率分析

三、算法代码 3.1 C语言

这其中我注释掉了我以前的一个错误思想的做法，大家可以看看，以免进入误区。

/**
基本思想：
以x轴坐标进行升序排序 取中轴划分为两块， 分别计算左右两边最近两点的距离
这里最近两点的距离是用递归操作获取的  
在处理了两边的点，获取了两边的最近点对距离后 以中线打开两边各一个最小距离 
在这个范围里面 获取到中间区域的最近点对 
题设：
输入一个n（0 
#include
#include
#include
#include
#include 
#define MAXN 1001
#define MAXX 100001
#define MAXY 100001
using namespace std;
/*全部的点*/
struct Node{double x,y;
}node[MAXN];
/*中间区域的点*/
Node middleLeft[MAXN];
Node middleRight[MAXN];
/*利用sort方法 需要的参数*/
bool cmpX(Node a,Node b){return a.x<b.x;};
bool cmpY(Node a,Node b){return a.y<b.y;};
/*获取两个点的最小距离*/
double getDis(Node a,Node b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))*1.0;
}
/*随机生成n的点*/
void getRandomNode(int n){for(int i=1;i<=n;i++)