算法设计与分析实验2 分治法求最近点对

一、实验目的

掌握分治法思想。
学会最近点对问题求解方法。

二、实验概述

分治法也称为分解法、分治策略等。分治法算法思想如下：

(1) 将一个问题划分为同一类型的若干子问题，子问题最好规模相同。

(2) 对这些子问题求解（一般使用递归方法，但在问题规模足够小时，有时也会利用另一个算法）。

(3) 有必要的话，合并这些子问题的解，以得到原始问题的答案。

当子问题足够大时，需要递归求解时，我们称之为递归情况（Recursive Case）。当子问题变得足够小，不再需要递归时，表示递归已经“触底”，进入了基本情况（Base Case）。

三、实验内容

1. 对于平面上给定的N个点，给出所有点对的最短距离，即，输入是平面上的N个点，输出是N点中具有最短距离的两点。

2. 要求随机生成N个点的平面坐标，应用蛮力法编程计算出所有点对的最短距离。

3. 要求随机生成N个点的平面坐标，应用分治法编程计算出所有点对的最短距离。

4. 分别对N=100000—1000000，统计算法运行时间，比较理论效率与实测效率的差异，同时对蛮力法和分治法的算法效率进行分析和比较。

5. 如果能将算法执行过程利用图形界面输出，可获加分。

四、问题描述

1.实验基本要求

随机生成n个点的随机坐标，且必须保证n个点均没有出现重复
使用蛮力法求解点的最短距离
使用分治法求解点的最短距离
分别对n=100000—1000000，统计算法运行时间，比较理论效率与实测效率的差异
对蛮力法和分治法的算法效率进行分析和比较
将算法执行过程利用图形界面输出

2.实验亮点

通过暴力法以及分治法详细介绍“最近点对”问题的实现方法
完成两种算法的图形界面可视化，使算法执行过程更清晰
完成数据运行效率的对比
对于算法实现的过程，绘制了算法示意图和算法流程图

3.实验说明

本实验从大规模数据验证了两种算法的正确性
本实验是基于蛮力法进行比较的
各算法消耗时间以秒为单位，只包含搜索的过程

五、算法原理和实现

1. 算法原理和实现

实验流程

首先通过随机数生成器生成特定范围内的double型数据，然后对点集分别使用蛮力法和分治法进行运算，计算出所有点对中的最短距离以及运行的时间消耗，并通过对比实际消耗与理论消耗、蛮力法与分治法消耗对比进行算法效率分析，得出实验结论

数据生成

在本题中，我选择使用随机设备做种子，并设置生成器，生成随机数为0-100以内的双精度浮点数，并用point结构体储存位置

数据去重

由于随机值生成的过程中有可能生成重复点的情况，因此需要对重复的点进行剔除

在生成随机数时，通过依次对比避免重复

同时重载哈希比较函数，在进行分治法时发挥作用

2. 蛮力法

算法原理

不断遍历求出每个点之间的距离，并选择距离最小的两个点进行输出

流程示意

实验伪代码

时间复杂度分析

共内外两次循环，时间复杂度为O(n^2)，可将其看作一个求n边无向完全图问题，即对于n个顶点每个顶点都连着n-1条边，共有边数为n(n-1)/2，也可得出时间复杂度为O(n^2)

3. 分治法

算法描述

根据问题描述，我们只需要在所有点对中求得一个两点之间的最短距离，而所有点对中，存在着一些明显就很远的点对，而对于这些点对的距离求解及比较完全是一种无用功，将造成时间和空间的双重浪费

为了简化蛮力法，降低无用比较次数，我们可以选择将所有点对组成的一个大整体拆分成几个小部分，进行分而治之，再合并求得其中的一个最小值，其即为我们需要求得的最短距离

算法内容

结合上述分析，我们可以使用分治法，利用分而治之的思想将问题实现简化，其算法关键内容包括：

a预处理: 将所有点对按照其横坐标进行排序，便于后续将点对均分为两部分，分别对其两个子问题进行求解

b基本情况base(递归返回条件):

若 n=1 return 无穷大

若 n=2 return 两点间距离

若 n=3 return 三间较小的距离

else n>3 则以该组坐标的下标中值进行再一次分块，mid=(l+ r)/2、midnum=arr[mid].x，将规模为n的问题再次分为两个规模为n/2的子问题，分别求其最短距离，复杂度为O(1)

c 取两个子问题返回最短距离较小的那个，d=min(dl, dr)

d 合并子问题的点，找到所有横坐标范围再[mid-d, mid +d]中的点,并根据纵坐标的值对其点进行排序

e 对于[mid-d, mid]中的每一点，检查[mid, mid +d]中的点与它的距离，更新所获得的最近距离

实验流程

算法实现

将所有点按照x坐标进行排序，并将平面分为两个大致相等的点集

则此时，对于求任意两点p1，p2之间的距离，存在三种情况：

p1，p2 都位于左侧点集

p1，p2 都位于右侧点集

p1，p2 一个位于左侧点集，一个位于右侧点集

对于情况1和情况2，我们只需要不断进行递归并结合返回条件便可得到结果

以下为针对于情况3的求解:

递归得到两边点子集的最近点对距离，取最小值d，其中d=min(dl,dr)，距离d来缩小我们查找的空间，中间点向外扩散，如果点与中间点的x左边之差，大于d，那么这个点及其往后的点，都不可能是最优的答案，缩小了查找空间

然而通过缩小查找空间来提高效率，其实是不稳定的，可能查找空间和原来一样，若继续通过蛮力法枚举查找，时间复杂度仍为O(n^2),达不到线性的复杂度

对于点对在[L-d, L+d]的数据，我们可以做出以下假设，对于对于左边区域的每一点p1要想在右边区域找到一点p2得 p1p2的距离<=d，这样的点p2必定存在于【以p1的y坐标为中心，上下延展d形成的d*2d的子矩形中】

证明：在一般情况及特殊情况下

通过遍历左边区域的所有点，划分出d*2d的矩形区域，然后检查6个点，更新答案即可，而这需要浪费O(n)的复杂度，则我们需要在O(1)的复杂度里找到d*2d的矩形区域，并求出最短距离

将左右的子区域的所有点对按照纵坐标进行排序，在对左侧区域所有点进行升序遍历时，设置指针h在右侧区域的点对向后查找，当左侧的点与查找到的右侧的点高度差小于d时，从h向后找六个点即可

由于左右区域的点均为升序排序，因此下一个左侧的点对应的指针h的下边界一定会变大，因此，h只需要在原来基础上继续进行比较，其比较最多的次数为右侧区域点集的大小，复杂度为O(1)，而进行查找的操作为6次，其时间复杂度仍为O(1),所以，总的时间复杂度仍为O(n)

算法实验伪代码

算法复杂度分析

递推式如下：T(n) = 2T(2/n) + n*log(n)

算法的改进

在未进行递归的情况下，时间复杂度最大为O(n*logn), 而产生这样的复杂度是由于在解决第三种情况时，需要对数据进行排序，此时排序时间复杂度便达到了O(n*logn)，若效仿归并排序，每次二分递归之后，我们对数组归并，因为递归排好了左右子区间，这样归并后，数组就是对y有序的了，不用消耗额外的时间再排序了，可以使合并子问题的代价变为O(n)级别

改进实现

更改返回条件-当有两个点时，需要对其进行比较