- UID
- 388422
- 积分
- 839
- 精华
- 贡献
-
- 威望
-
- 活跃度
-
- D豆
-
- 在线时间
- 小时
- 注册时间
- 2006-1-28
- 最后登录
- 1970-1-1
|
发表于 2007-3-18 00:51:06
|
显示全部楼层
您的查询字词都已标明如下:最近点对 算法 (点击查询词,可以跳到它在文中首次出现的位置)
如果您想保存该页面,可以添加到搜藏
(百度和网页http://cse.seu.edu.cn/people/jmd ... 的即时页面。)
--------------------------------------------------------------------------------
求最近点对的随机算法
分治法求解需O(nlogn)时间,而用随机算法求解可达到O(n)时间.
对于给定的平面上的n个点(xi,yi)( i=1,2,…,n)和一个距离δ,
以δ为尺寸可以构造一个(逻辑上的)网格,
该网格以(min{xi},min{yj})为网格的最左下点,
之后以步长δ不断向右,向上伸展为长方形网格;
使得(max{xi},max{yj})也含在其中.
由于所有的点均在长方形网格中,最近点对也必在其中.
对每个尺寸为δ×δ的方格,分别向左向上,向右向上,向左向下,
向右向下各扩展一格,可得4个2δ×2δ的方格(i=1,2,3,4). i
δ2Γ
定理:设已知平面上的某两点的距离为δ.
若最近点对中的一个点落在某个δ×δ方格δΓ中,
则在上述的4个2δ× 2δ方格(i=1,2,3,4)中, i
δ2Γ
至少有一个同时含有最近点对的两个点.
推论:若已知平面上的某两点的距离为δ,
且算法对长方形网格中每一个2δ×2δ方格中的所有点对,
均一一计算其距离,则该算法一定可以找出最近点对.
算法:
1) 在点集S(|S|=n)中随机地取一个子集T,使得|T|= n .
(按随机取样算法的分析,n个中取m个(m≤n)时间为O(n))
2) 对T中的所有点对逐一计算距离,求出最近点对距离δ(T).
(点对数为 n ( n -1)/2,每个点对计算时间为O(1),
故总的计算时间为O( n 2)= O(n).)
3) 以δ(T)为尺寸构造一个(逻辑上的)长方形网格,
(设长方形的横向共有m格,纵向共有r格.)
4) 如果m*r≤cn(c可取2~10,取何值合适见后面的讨论),
则开设一个m×r的指针矩阵P,和一个m×r的计数矩阵Q,
然后逐一扫描S中的点sk:
如果sk落在方格中(i,j分别表示所在方格横向,纵向位置), ij
δΓ
则把该点放入P[i,j]所指的链表内,Q[i,j]增1,
直至n个点全部检查为止.
(每个点计算时间为O(1),故总的计算时间为O(n).)
然后扫描Q数组,找到含顶点最多的方格.(时间为O(n)) ij
δΓ
如果中点数≤ij
δΓn,则逐一计算中的点距离(时间为O(n)), ij
δΓ
求出其中的最近点对及新的δ'(如果δ'比δ小的话).
如果中点数>ij
δΓn,则把一分为4,成为4个ij
δΓ
2
δ×
2
δ的方格,
找出其中含点最多的方格,一直拆分到方格中的点数≤n,
求出其中的最近点对及新的δ'(时间复杂度期望值是O(n)).
若m*r>cn,则在素数表中找一个略小于cn的素数p,
然后逐一检查S中的点sk,找到其所在方格(时间为O(n)), ij
δΓ
用散列函数H(i,j,p)把sk散列至长为p的桶中:
桶中的每个槽只对应一个方格(若发生冲突,用冲突处理机制), ij
δΓ
每个槽要记录方格中点的个数,各个点用链表连接起来.
S的检查完成以后,找到含点数最多的方格(时间为O(n)), ij
δΓ
用前述方法计算出该方格中的最近点对和新δ'(如果δ'比δ小的话).
5) 以新δ'为尺寸构造一个(逻辑上的)新网格,
设网格中的小方格数为m'×r',则在这个网格中
恰有(m'-1)×(r'-1)个尺寸为2δ'×2δ'的方格.
由定理知,最近点对必定落在某个之中. δ2Γ
逐一检查S中的点,依次把这些点放入(m'-1)×(r'-1)个指针
所指的链表中(或长度为p的散列表中).(时间复杂度是O(n))
6) 逐一检查含有2个点以上的方格, δ2Γ
对方格中的所有点对进行计算,与当前最小的δ*比较,
若小于δ*,则更新δ*,更新当前的最近点对.
当所有含2个点以上的2δ×2δ方格检查完毕时,
点集中的最近点对也就找到了.根据概率分析,
此项工作的时间复杂度期望值是O(n).
关于c的取值(c可取2~10):
c取值大的好处是需要散列的可能性降低,可直接处理二维表,
且每一个格子中的顶点数相对要少,第6步中工作量减少;
坏处是循环次数增多.c取的小的好处,坏处则反之.
一般来说,若顶点较密集,则c要取的稍大. |
|