查找二维平面上距离最小点对的O(n)算法原理与Python实现

==============

版权声明：由于公众号后台规则问题，本文暂时无法设置原创标记，但仍属原创内容。

============

问题描述：

给定二维平面上的若干个点，从中查找距离最小的两个。

问题分析：

要解决这个问题，最直接的想法是把给定的点进行两两组合，计算每个组合中两个点的距离，从中找出距离最小的一对。这个算法的计算量非常大，没有任何优化的痕迹，时间复杂度妥妥的O(n^2)，即使充分发挥Python语言函数式编程技巧和标准库对象的优势也无法弥补算法本身效率低下的问题。

上面的代码之所以效率低，主要是做了很多不必要的计算。认识到这一点，可以采用一点技巧来减少计算量，例如根据三角形两边长之和大于第三边可知，如果某两个点之间的水平距离或垂直距离已经大于目前已知的最小距离，那么这两个点的距离不可能更小。引入一点减法运算从而避免一些幂运算还是合算的，可以适当提高速度。但这样的改进不属于算法级的优化，虽然有些效果，但效率不会有特别的提升。细心的读者会发现，下面代码中的开方运算并不是必须的，删除可以进一步加快速度把时间再缩短几秒钟，但与我们的目标还有很大距离。

最初的穷举法是仔细检查每个组合是否满足要求，上面的改进是先稍微看一眼每个组合，如果有希望符合要求就再仔细看看，如果第一眼发现不可能符合要求就看完第一眼不再管它了。如果能够减少一些不必要的组合，缩小搜索的范围，把“稍微看一眼”的时间也省下来，应该可以大幅度提高效率。

接下来我们考虑采用分治法，时间复杂度可以达到O(nlogn)，核心思路为：1）对所有点按x坐标升序排列，x坐标相同的按y坐标升序排列；2）按x坐标把原始点集左右等分为两个子集，分别寻找两个子集内部距离最小的点对，取二者中最小的一个；3）检查左右两个点集之间的点是否有距离更小的，也就是一个点属于左侧点集另一个点属于右侧点集，但二者之间距离更小；4）对左右两个子集重复上面的操作。

下面的代码在实现算法时又进行了一些优化，例如计算左右点集之间的最小距离时，只考虑了有可能构成更短距离的点，也就是左右两个子集边界附近的点。

虽然代码看上去复杂了很多，但执行速度快了几百倍，点越多效率提高越明显。那么，算法还有改进空间吗？

让我们再回过头来深入分析一下这个问题的枚举法求解过程，如果有一个点B与当前点A的距离最小，那么B点一定在A点的邻域内，如果我们只计算A点与很小邻域内的其他点的距离，而不用计算A点与整个点集中所有点的距离，无疑可以减少大量计算。这样的话问题还有两个关键需要解决，一是邻域半径如何确定，二是如何实现只搜索邻域内的点。对于第一个问题，可以使用目前已知的最小距离作为邻域半径，并且随着计算的推进不断地缩小邻域。对于第二个问题，可以借助于字典来实现。通过这样的改进，甚至可以使得时间复杂度接近于O(n)，也会深刻理解一个问题，数据结构是算法的基础，脱离了数据结构的支撑，算法就是空中楼阁。

最后，填写几行代码来测试和比较一下几种方法的效率。

运行结果如下，

注释掉几个函数中检测到距离为0提前结束的代码，重新运行程序，结果如下，

可以看到，只搜索邻域的枚举法具有最好的执行速度，这也符合预期。可能会有读者疑惑，为了确定合适的初始最小距离，代码中先对所有点进行了排序，这是否会引入额外的工作量呢，又是否可以消除呢？需要明确的是，确实会引入一点额外的计算量，但是Python内置函数sorted()已经把排序算法优化到了极致，开销很小。如果不这样做的话，也可以随机选择几个点并计算最小距离作为初始值，这样的话会导致算法不稳定，有时快有时慢，如果随机选择的点距离比较远的话，整个算法的收敛速度会很慢。即使是随机选择的点合适的时候，效率的提升也不明显，几乎可以忽略。