基于递归法的最接近点对问题.docx
- 文档编号:3874464
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:7
- 大小:23.41KB
基于递归法的最接近点对问题.docx
《基于递归法的最接近点对问题.docx》由会员分享,可在线阅读,更多相关《基于递归法的最接近点对问题.docx(7页珍藏版)》请在冰点文库上搜索。
基于递归法的最接近点对问题
姓名:
杨意
学号:
309040102009
学院:
数学信息学院
专业:
计算机辅助教育
目录
1、问题综述 2
2、用递归法解决 2
2.1一维情形下的分析 2
2.2二维情形下的分析 3
2.3算法优化 6
2.4算法实现 6
3、结论 9
基于递归法的最接近点对问题
摘要:
在计算机应用中,常用诸如点、圆等简单的几何对象表现现实世界中的实体。
在涉及几何对象的问题中,常需要了解其邻域中其他几何对象的信息。
例如,在空中交通控制问题中,若将飞机作为空间中移动的一个点来处理,则具有最大碰撞危险的两架飞机就是这个空间中最近的一点。
这类问题是计算机几何学中研究的基本问题之一。
本文就运用递归法对一维和二维的情况加以讨论。
关键词:
最接近点对递归法
问题综述
最接近点对问题的提法是:
给定平面上n个点,找其中的一对点,使得在n个点组成的所有点对中,该点对间的距离最小。
实际情况下,最接近点对可能多于一对,为简单起见,我们只找其中的一对作为问题的解。
有一个最直观的方法就是将每一点与其他n-1个点的距离算出,找出达到最小距离的两点即可。
然而,这样做效率太低,我们想到用递归法来解决这个问题。
2、用递归法解决
将所给的平面上n个点的集合S分成两个子集S1和S2,每个子集中约有n/2个点。
然后在每个子集中递归地求其最接近的点对。
在这里,一个关键的问题是如何实现递归法中的合并步骤,即由S1和S2的最接近点对,如何求得原集合S中的最接近点对。
如果组成S的最接近点对的两个点都在S1中或都在S2中,则问题很明显就可以找到答案。
可是还存在另外一种可能,就是这两给点分别在S1和S2中的时候。
下面主要讨论这种情况。
2.1一维情形下的分析
为使问题易于理解和分析,我们先来考虑一维的情形。
此时,S中的n各点退化为x轴上的n个实数x1,x2,x3…xn。
最接近点对即为这n个实数中相差最小的两个实数。
我们尝试用递归法来求解,并希望推广到二维的情形。
假设我们用x轴上的某个点m将S划分为两个集合S1和S2,使得S1={x∈S|x≤m};
S2={x∈S|x>m}。
这样一来,对于所有p∈和q∈S2有p<q。
递归地在S1和S2上找出其最接近点对{p1,p2}和{q1,q2},并设
d=min{|p1-p2|,|q1-q2|}
由此易知,S中的最接近进点对或者是{p1,p2},或者是{q1,q2},或者是某个{p3,q3},其中,p3∈S1且q3∈S2。
如图2-1-1所示。
图2-1-1一维情形的递归法
我们注意到,如果S的最接近点对是{p3,q3},即|p3-q3|<d,则p3和q3两者与m的距离不超过d,即|p3-m|<d,|q3-m|<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]中所有点,即p3和q3。
从而我们用线性时间就可以将S1的解和S2的解合并成为S的解。
但是,还有一个问题需要认真考虑,即分割点m的选取,即S1和S2的划分。
选取分割点m的一个基本要求是由此将S进行分割,使得S=S1∪S2,S1≠Φ,S2≠Φ,且S1∈{x|x≤m},S2∈{x|x>m}。
容易看出,如果选取m={max(S)+min(S)}/2,可以满足分割要求。
然而,这样选取分割点,有可能造成划分出的子集S1和S2的不平衡。
例如在最坏情况下,|S1|=1,|S2|=n-1,这样的计算效率与分割前相比提高幅度不明显。
这种现象可以通过递归法中“平衡子问题”的方法加以解决。
我们可以适当选择分割点m,使S1和S2中有个数大致相等的点。
我们会想到用S中各点坐标的中位数来作为分割点。
由此,我们设计出一个求一维点集S的最接近点对的算法Cpair1如下:
---------------------------------------------------------------
BoolCpair1(S,d)
{
N=|S|;
if(n<2){
d=∞;
returnfalse;
}
m=S中各点坐标的中位数;
//构造S1和S2;
S1={x∈S|x≤m};
S2={x∈S|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线性分割为大小大致相等的两个子集S1和S2,我们选取一垂直线L:
x=m来作为分割直线。
其中,m为S中各点x坐标的中位数。
由此将S分割为S1={p∈S|x(p)≤m}和S2={p∈S|x(p)>m}。
从而使S1和S2分别位于直线L的左侧和右侧,且S=S1∪S2。
由于m是S中各x坐标的中位数,因此S1和S2中得点数大致相等。
递归地在S1和S2上解最接近点对问题,我们分别得到S1和S2中的最小距离d1和d2。
现设d=min{d1,d2}。
若S的最接近点对(p,q)之间的距离小于d,则p和q必分属于S1和S2。
不妨设p∈S1,q∈S2。
那么p和q距直线L的距离均小于d。
因此,若我们用P1和P2分别表示直线L的左边和右边的宽为d的两个垂直长条区域,则p∈P1且q∈P2,如图2-2-1所示。
图2-2-1距直线L的距离小于d的所有点
在一维情形下,距分割点距离为d的两个区间(m-d,m]和(m,m+d]中最多各有S中一个点。
因而这两点成为唯一的未检查过的最接近点对候选者。
二维的情形则要复杂些。
此时,P1中所有点和P2中所有点构成的点对均为最接近点对的候选者。
在最坏的情况下有n2/4对这样的候选者。
考虑P1中任意一点p,它若与P2中的点q构成最接近点对的候选者,则必有distance(p,q)<d。
满足这个条件的P2中的点有多少个呢?
容易看出这样的点一定落在一个d*2d的矩形R中,如图2-2-2所示。
图2-2-2包含点q的d*2d矩形R
由d的意义可知,P2中任何两个S中的点的距离都不小于d。
由此可以推出矩形R中最多只有6个S中的点。
下面我们来证明这个结论。
我们可以将矩形R的长为2d的边3等分,将它的长为d的边2等分,由此导出6个(d
/2)*(2d/3)的矩形。
如图2-2-3(a)所示。
如图2-2-3矩形R中点的稀疏性
若矩形R中有多于6个S中的点,则由鸽舍原理易知至少有一个(d/2)*(2d/3)的小矩形中有2个以上S中的点。
设u,v是这样2个点,它们位于同一小矩形中,则
(x(u)-x(v))2+(y(u)-y(v))2≤(d/2)2+(2d/3)2=25/36d2
因此,distance(u,v)≤5d/6<d。
这与d的意义相矛盾。
也就是说矩形R中最多只有6个S中的点。
图2-2-3(b)是矩形中恰有6个S中点的极端情形。
由于这种稀疏性质,对于P1中任意一点p,P2中最多只有6个点与它构成最接近点对的候选者。
因此,在递归法的合并步骤中,我们最多只需要检查6*n/2=3n个候选者,而不是n2/4个候选者。
我们将p和P2中所有S2的点投影到垂直线L上。
由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中,所以它们在直线L上的投影点距p在L上投影点的距离小于d。
由上面的分析可知,这种投影点最多只有6个。
因此,若将P1和P2中所有S中点按其y坐标排好序,则对P1中所有点,对排好序的点列做一次扫描,就可以找出所有最接近点对的候选者。
对P1中每一点最多只要检查P2中排好序的相继6个点。
至此,我们给出用递归法求二维点集最接近点对的算法Cpair2如下:
------------------------------------------------------------------------------------------------
boolCpair2(S,d)
{
N=|S|;
If(n<2)
{d=∞;
Returnfalse;
}
1.m=S中各点x间坐标的中位数;
构造S1和S2;
//S1={p∈S|x(p)<=m},S2={p∈S|x(p)>m}
2.Cpair2(S1,d1);
Cpair2(S2,d2);
3.dm=min(d1,d2);
4.设P1是S1中距垂直分割线L的距离在dm之内的所有点组成的集合;
P2是S2中距分割线L的距离在dm之内所有点组成的集合;
将P1和P2中点依其y坐标值排序;
并设X和Y是相应的已经排好序的点列;
5.通过扫描X以及对于X中每个点检查Y中与其距离在dm内的所有点(最多6个)可以完成合并;
当X中的扫描指针逐次向上移动时,Y中的扫描指针可在宽为2dm的一个区间内移动;
设dl是按这种扫描方式找到的点对间的最小距离;
6.d=min(dm,dl);
returntrue;
}
------------------------------------------------------------------------------------------------------
2.3算法优化
在以上二维情形下的算法中,在每次执行第4步时都要进行排序,这将花费较多的时间,从而增加算法的复杂度。
因此,在这里我们要作一个技术处理。
我们采用设计算法时常用的预排序技术,在使用递归法之前,预先将S中n个点依其y坐标值排好序,设排好序的点列为P*。
在执行递归法的第4步时,只要对P*作一次线性扫描,即可抽取出我们所需要的排好序的点列X和Y。
然后,在第5步时再对X作一次线性扫描,即可求得dl。
2.4算法实现
在具体实现算法Cpair2时,我们分别用类PointX和PointY表示依x坐标和依y坐标排序的点。
-----------------------------------------------------------------------------------------
ClassPointX{
Public:
Intoperator<=(PointXa)const
{return(x<=a.x);}
Private:
IntID;//点编号
Floatx,y;//点坐标
};
ClassPointY{
Public:
intoperator<=(PointYa)const
{return(y<=a.y)}
Private:
Intp;//同一点在数组X中的坐标
Floatx,y;//点坐标
};
--------------------------------------------------------------------------------------------
平面上任意两点u和v之间的距离可计算如下:
---------------------------------------------------------------------------------------------
Template
Inlinefloatdistance(constType&u,constType&v)
{
Floatdx=u.x-v.x;
Floatdy=u.y-v.y;
Returnsqrt(dx*dx+dy*dy);
}
------------------------------------------------------------------------------------------------
在算法Cpair2中,用数组X存储输入的点集。
在算法的预处理阶段,将数组X中的点依x坐标和依y坐标排序,排好序的点集分别存储在数组X和数组Y中。
事实上,我们只要取m=(L+r)/2,则X[L:
m]和X[m+1:
r]就是满足要求的分割。
依y坐标排好序的数组Y用于在算法的合并步中快速检查d矩形条内最接近点对的候选者。
--------------------------------------------------------------------------------------------------
BoolCpair2(PointXX[],intn,PointX&a,PointX&b,float&d)
{
If(n<2)returnfalse;
MergeSort(X,n);
PointY*Y=newPointY[n];
For(inti=0;i //将数组X中的点复制到数组Y中 { Y[i].p=i; Y[i].x=X[i].x; Y[i].y=X[i].y; } MergeSort(Y,n); PointY*Z=newPointY[n]; Closest(X,Y,Z,0,n-1,a,b,d); delete[]Y; delete[]Z; returntrue; } 算法Cpair2中,具体计算最接近点对的工作由函数closest完成。 ------------------------------------------------------------------------------------------------ Viodclosest(PointXX[],PointYY[],PointYZ[],intL,intr,PointX&a,PointX&b,float&d) { If(r–1==1)//2点的情形 { a=X[L]; b=X[r]; d=distance(X[L],X[r]); return; } If(r–1==2)//3点的情形 { Floatd1=distance(X[L],X[L+1]); Folatd2=distance(X[L+1],X[r]); Floatd3=distance(X[L],X[r]); If(dL<=d2&&dL<=d3) { a=X[L]; b=X[L+1]; d=dL; return; } If(d2<=d3) { a=X[L+1]; b=X[r]; d=X[d2]; }else { a=X[L]; b=X[r]; d=d3;} return;} //多于3点的情形,用递归法 Intm=(L+r)/2; Intf=L,g=m+1; For(inti=1;i<=r;i++) If(Y[i].p>m) Z[g++]=Y[i]; Else Z[f++]=Y[i]; Closest(X,Z,Y,L,m,a,b,d); Floatdr; PointXar,br; Closest(X,Y,Z,m+L,r,ar,br,dr); If(dr { a=ar; b=br; d=dr; } Merge(Z,Y,L,m,r);//重构数组Y //d矩形条内的点置于Z中 Intk=L; For(inti=L,i<=r,i++) If(fabs(Y[m].x–Y[i].x) Z[k++]=Y[i];//搜索Z[L: k-1] For(inti=L;i<=k;i++) { For(intj=i+1;j { Floatdp=distance(Z[i],Z[j]); If(dp { d=dp; a=X[Z[i].p]; b=X[Z[j].p]; } } } 3、结论 3.1.对于一类问题,如果该问题规模为n,但是可以分解为k个互相独立且与原问题相同的规模较小的子问题的话,我们就可以运用递归法,递归的解决这些子问题,然后将各子问题的解合并得到原问题的解。 3.2通过对最接近点对问题的解决,熟悉了解决问题的基本步骤和方法: 首先对问题进行分类,然后运用该类问题的处理思路进行算法的设计,最后还要考察所设计算法的复杂性,进一步进行优化处理。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 递归 最接近 问题