基于递归法的最接近点对问题

基于递归法的最接近点对问题

ID:15101247

大小:97.00 KB

页数:11页

时间:2018-08-01

基于递归法的最接近点对问题_第1页
基于递归法的最接近点对问题_第2页
基于递归法的最接近点对问题_第3页
基于递归法的最接近点对问题_第4页
基于递归法的最接近点对问题_第5页
资源描述:

《基于递归法的最接近点对问题》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、基于递归法的最接近点对问题姓名:杨意学号:309040102009学院:数学信息学院专业:计算机辅助教育目录1、问题综述22、用递归法解决22.1一维情形下的分析22.2二维情形下的分析32.3算法优化62.4算法实现63、结论9基于递归法的最接近点对问题摘要:在计算机应用中,常用诸如点、圆等简单的几何对象表现现实世界中的实体。在涉及几何对象的问题中,常需要了解其邻域中其他几何对象的信息。例如,在空中交通控制问题中,若将飞机作为空间中移动的一个点来处理,则具有最大碰撞危险的两架飞机就是这个空间中最近的

2、一点。这类问题是计算机几何学中研究的基本问题之一。本文就运用递归法对一维和二维的情况加以讨论。关键词:最接近点对递归法1、问题综述最接近点对问题的提法是:给定平面上n个点,找其中的一对点,使得在n个点组成的所有点对中,该点对间的距离最小。实际情况下,最接近点对可能多于一对,为简单起见,我们只找其中的一对作为问题的解。有一个最直观的方法就是将每一点与其他n-1个点的距离算出,找出达到最小距离的两点即可。然而,这样做效率太低,我们想到用递归法来解决这个问题。2、用递归法解决将所给的平面上n个点的集合S分成

3、两个子集S1和S2,每个子集中约有n/2个点。然后在每个子集中递归地求其最接近的点对。在这里,一个关键的问题是如何实现递归法中的合并步骤,即由S1和S2的最接近点对,如何求得原集合S中的最接近点对。如果组成S的最接近点对的两个点都在S1中或都在S2中,则问题很明显就可以找到答案。可是还存在另外一种可能,就是这两给点分别在S1和S2中的时候。下面主要讨论这种情况。2.1一维情形下的分析为使问题易于理解和分析,我们先来考虑一维的情形。此时,S中的n各点退化为x轴上的n个实数x1,x2,x3…xn。最接近点

4、对即为这n个实数中相差最小的两个实数。我们尝试用递归法来求解,并希望推广到二维的情形。假设我们用x轴上的某个点m将S划分为两个集合S1和S2,使得S1={x∈S

5、x≤m};S2={x∈S

6、x>m}。这样一来,对于所有p∈和q∈S2有p<q。递归地在S1和S2上找出其最接近点对{p1,p2}和{q1,q2},并设d=min{

7、p1-p2

8、,

9、q1-q2

10、}由此易知,S中的最接近进点对或者是{p1,p2},或者是{q1,q2},或者是某个{p3,q3},其中,p3∈S1且q3∈S2。如图2-1-1所示。图

11、2-1-1一维情形的递归法我们注意到,如果S的最接近点对是{p3,q3},即

12、p3-q3

13、<d,则p3和q3两者与m的距离不超过d,即

14、p3-m

15、<d,

16、q3-m

17、<d。也就是说,p3∈(m-d,m],q3∈(m,m+d]。由于每个长度为d的半闭区间至多包含S1中的一个点,并且m是S1和S2的分割点,由图2-1-1可以看出,如果(m-d,m]中有S中点,则此点就是S1中最大点。同理,如果(m,m+d]中有S中点,则此点就是S2中最小点。因此,我们用线性时间就能找到区间(m-d,m]和(m,m+d]中所

18、有点,即p3和q3。从而我们用线性时间就可以将S1的解和S2的解合并成为S的解。但是,还有一个问题需要认真考虑,即分割点m的选取,即S1和S2的划分。选取分割点m的一个基本要求是由此将S进行分割,使得S=S1∪S2,S1≠Φ,S2≠Φ,且S1∈{x

19、x≤m},S2∈{x

20、x>m}。容易看出,如果选取m={max(S)+min(S)}/2,可以满足分割要求。然而,这样选取分割点,有可能造成划分出的子集S1和S2的不平衡。例如在最坏情况下,

21、S1

22、=1,

23、S2

24、=n-1,这样的计算效率与分割前相比提高幅度

25、不明显。这种现象可以通过递归法中“平衡子问题”的方法加以解决。我们可以适当选择分割点m,使S1和S2中有个数大致相等的点。我们会想到用S中各点坐标的中位数来作为分割点。由此,我们设计出一个求一维点集S的最接近点对的算法Cpair1如下:---------------------------------------------------------------BoolCpair1(S,d){N=

26、S

27、;if(n<2){d=∞;returnfalse;}m=S中各点坐标的中位数;//构造S1和S2;S1

28、={x∈S

29、x≤m};S2={x∈S

30、x>m};Cpair1(S1,d1);Cpair1(S2,d2);p=max(S1);q=min(S2);d=min(d1,d2,q-p);returntrue}------------------------------------------------------------------2.2二维情形下的分析以上一维算法可以推广到二维的情形。设S中的点为平面上的点,它们都有两个坐标值x和y。为了将平面上点集S线

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。