求最近点对随机算法.doc

《求最近点对随机算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、求最近点对的随机算法分治法求解需O(nlogn)时间，而用随机算法求解可达到O(n)时间。对于给定的平面上的n个点(xi,yi)(i=1,2,…,n)和一个距离d，以d为尺寸可以构造一个（逻辑上的）网格，该网格以（min{xi},min{yj}）为网格的最左下点，之后以步长d不断向右、向上伸展为长方形网格；使得（max{xi},max{yj}）也含在其中。由于所有的点均在长方形网格中，最近点对也必在其中。对每个尺寸为d×d的方格，分别向左向上、向右向上、向左向下、向右向下各扩展一格，可得4个2d×2d的方格(i=1,2,3,4)。定理：设已知平面上

2、的某两点的距离为d。若最近点对中的一个点落在某个d×d方格中，则在上述的4个2d×2d方格(i=1,2,3,4)中，至少有一个同时含有最近点对的两个点。推论：若已知平面上的某两点的距离为d，且算法对长方形网格中每一个2d×2d方格中的所有点对，均一一计算其距离，则该算法一定可以找出最近点对。算法：1）在点集S(

3、S

4、=n)中随机地取一个子集T，使得

5、T

6、=ëû。（按随机取样算法的分析，n个中取m个（m≤n）时间为O(n)）2）对T中的所有点对逐一计算距离，求出最近点对距离d(T)。（点对数为ëû(ëû-1)/2，每个点对计算时间为O(1)，故总的计

7、算时间为O(ëû2)=O(n)。）3）以d(T)为尺寸构造一个（逻辑上的）长方形网格，（设长方形的横向共有m格，纵向共有r格。）1）如果m*r≤cn(c可取2～10，取何值合适见后面的讨论)，则开设一个m×r的指针矩阵P、和一个m×r的计数矩阵Q，然后逐一扫描S中的点sk：如果sk落在方格中(i,j分别表示所在方格横向、纵向位置)，则把该点放入P[i,j]所指的链表内，Q[i,j]增1，直至n个点全部检查为止。（每个点计算时间为O(1)，故总的计算时间为O(n)。）然后扫描Q数组，找到含顶点最多的方格。（时间为O(n)）如果中点数≤，则逐一计算中的

8、点距离（时间为O(n)），求出其中的最近点对及新的d’（如果d’比d小的话）。如果中点数＞，则把一分为4，成为4个×的方格，找出其中含点最多的方格，一直拆分到方格中的点数≤，求出其中的最近点对及新的d’（时间复杂度期望值是O(n)）。若m*r＞cn，则在素数表中找一个略小于cn的素数p，然后逐一检查S中的点sk，找到其所在方格（时间为O(n)），用散列函数H(i,j,p)把sk散列至长为p的桶中：桶中的每个槽只对应一个方格（若发生冲突，用冲突处理机制），每个槽要记录方格中点的个数，各个点用链表连接起来。S的检查完成以后，找到含点数最多的方格（时间为

9、O(n)），用前述方法计算出该方格中的最近点对和新d’（如果d’比d小的话）。2）以新d’为尺寸构造一个（逻辑上的）新网格，设网格中的小方格数为m’×r’，则在这个网格中恰有(m’-1)×(r’-1)个尺寸为2d’×2d’的方格。由定理知，最近点对必定落在某个之中。逐一检查S中的点，依次把这些点放入(m’-1)×(r’-1)个指针所指的链表中（或长度为p的散列表中）。（时间复杂度是O(n)）6)逐一检查含有2个点以上的方格，对方格中的所有点对进行计算，与当前最小的d*比较，若小于d*，则更新d*、更新当前的最近点对。当所有含2个点以上的2d×2d方

10、格检查完毕时，点集中的最近点对也就找到了。根据概率分析，此项工作的时间复杂度期望值是O(n)。关于c的取值（c可取2～10）：c取值大的好处是需要散列的可能性降低，可直接处理二维表，且每一个格子中的顶点数相对要少，第6步中工作量减少；坏处是循环次数增多。c取的小的好处、坏处则反之。一般来说，若顶点较密集，则c要取的稍大。