龙空技术网

《算法导论》:平面上的最近点对(分治算法)

算法哥 1099

前言:

而今大家对“算法导论第八章思考题答案”大约比较关注,同学们都需要知道一些“算法导论第八章思考题答案”的相关知识。那么小编同时在网络上收集了一些对于“算法导论第八章思考题答案””的相关资讯,希望小伙伴们能喜欢,兄弟们快快来学习一下吧!

导读:算法哥今天给大家分享一道《算法导论》里的介绍分治算法的经典题目,大家跟着我来一起学习吧!
题目描述

给定平面上n个点,找出其中的一对点的距离,使得在这n个点的所有点对中,该距离为所有点对中最小的。

输入格式:

第一行:n;2≤n≤200000

接下来n行:每行两个实数:x y,表示一个点的行坐标和列坐标,中间用一个空格隔开。

输出格式:

仅一行,一个实数,表示最短距离,精确到小数点后面4位。

输入输出样例

输入样例#1:

31 11 22 2

输出样例#1:

1.0000

说明

0<=x,y<=10^9

题目分析

题目要求距离最近的两个点的距离,最朴素的做法就是直接两层循环,枚举所有的点对,计算距离,得出距离最小的,显然时间复杂度是O(n^2)的,数据规模n=200000,毫无疑问会超时的。

那怎么解决这个问题,根据《算法导论》里的介绍,我们可以分而治之,把平面上的点先按照横坐标排序,横坐标相同就按照纵坐标排序,然后从中间分开,假设我们已经求出左边的点集里的最近距离d1,右边点集的最近距离d2,令d = min(d1,d2),那么最终要求的最近距离可能是d,也可能是一个点在左边,一个点在右边构成的点对所形成的距离!

见图:平面上有11个点,我们以红色的F点把平面上的点一分为二,假设F点本身属于左半部分,那么d1 = AB = 1,d2 = HI = 1,所以d = min(d1,d2) = 1

现在,我们已经知道左半部分最近距离d1,以及右半部分最近距离d2,那么所有点集的最短距离还有可能是一个点在左半边部分,一个点在右半部分,比如上图里的GL=0.6。那么我们怎么求出一个点在左边,一个点在右边的这种情况的最短的距离呢 ?首先,我们可以枚举左边的点和右边的点组成的点对,但是这样显然复杂度太高了,假设左边有n/2个点,右边有n/2个点,直接枚举所有点对要枚举n^2/4次!

那有什么其他办法可以想吗 ?有!既然我们已经知道左半部分和右半部分的最短距离d,那么是不是有可以利用这个距离d,做点事情?上面的例子d=1,我们是以红色的F点分割点集的,那么我们分别在F点左右两边,距离为d=1的地方,画两条绿色直线,如图:

显然,我们要找的点对,一个点在F点左边,一个点在F点右边,且这两个点必然落在两条绿色直线之间!因为一旦有一个点在两条绿线区间外,那他们的距离必然大于d!所以,我们此时只需要考察落在两条绿色直线范围内的点!上图中,我们只需要考察F,G,L 3个点即可!

我们考察F点,我们看PQKR形成的边长等于2d=2的正方形,显然,能够与F点形成距离小于d的点,必然在这个正方形内, 且落在这个正方形内的点,必然是不会超过16个的,因为我们可以把PQKR这个正方形,分割成16个边长为d/2=0.5小矩形(此时小矩形对角线长必然小于d),假设每个小矩形内有一个点,那么再放一个点进来,必然导致有两个点在同一个小矩形内,这样导致小矩形内的两个点的最远距离(对角线距离)必然小于d,与前面得到的点对同时位于左边,或者同时位于右边的最小的距离d矛盾了!所以PQKR矩形里最多不会超过16个点,也说明对于绿色区域内的点X,与点X形成最近距离有可能小于d的点一定小于16个,且必然落在绿色区域内,且这些点的纵坐标与X的纵坐标差值小于d。实际上,在编码时,我们把绿色区域内的点,按照纵坐标y来排序,从小到大,依次考察每个点X,我们只需要考察点X上方的点的纵坐标减去X点的纵坐标小于d的点。显然这些点不会超过8个。我们把绿色区域内的点扫描一遍,复杂度是O(n*8)=O(n)的,但是对绿色区域内纵坐标排序,直接快速排序是O(nlogn)的,有没有更好的方法呢 ?有!归并排序的思路,哈哈!直接O(n)合并左右区间内已经按照y坐标排好序的点即可!这个地方看起来有点抽象,结合源码可以理解!

上源码:

复杂度分析

最初按照横坐标和纵坐标来排序的复杂度是O(nlogn)的,然后,每次递归划分区间,区间划分的深度不会超过O(logn),每一层归并复杂度是O(n)(归并只涉及合并两个有序的区间),所以总复杂度是O(nlogn)的。

题目总结

平面上最近点对,是《算法导论》里非常经典的一个题目,要理解这个题目有以下几个难点:

1:对递归有深刻的认识,这样才知道怎么把区间划分,怎么合并有序区间;

2:充分利用左右两边已知的最近距离d,来思考一个点在左边部分,一个点在右边部分的情况;

3:得出绿色区域内的点,只需要考察纵坐标差值在d范围内的点后,想到绿色区域里的点按照纵坐标排序,线性时间算出最小的d;

今天的题目你有收获吗 ?书读百遍其义自见,如果有不理解的,请在文章下面留言哦!

标签: #算法导论第八章思考题答案