算法分析与设计作业

《算法分析与设计作业》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、最接近点对问题问题此问题分为一维，二维，三维的情况1.一维：给定直线上n个点，找其中一对点，使得在n个点组成的所有点对中，该点对间的距离最小，这个问题比较简单，是引出二维解法的一个引子，因为一维的百线上的点,相邻点的距离肯定小于相隔的点的距离，只需要考虑相邻点即可。2.二维：给定平面上n个点，找其屮一对点，使得在n个点组成的所有点对屮，该点对间的距离最小，这是我们这一问题的重点3.三维：给定空间上n个点，找其中一对点，使得在n个点组成的所有点对中，该点对间的距离最小，此问题是二维的解法的复杂化，具体可以在飞机航线等问题上运用，但在此不多做介绍。基本思想由于该问题的基木解法是去考察每个

2、点和其他所有点的距离。因此它的时I'可复杂度是0(n2)f这样做的效率太低，我们就要去寻找一个更高效的办法：分治法。1.因二维的情况太过复杂，先考虑一•维的情况中，可以用分治法对其进行分部计算：把直线分成两部分，以心，分别求出其最接近点的距离/〃2。但分割开的地方的两点距离可能小于这两个值，这三个值进行比较Z后，得到最后结果。2.鉴于此，二维的也町以用此方法进行计算：把待计算的点$分成两部分吐，分别求出其最接近点的距离％厶。但/dp最小的未必是$中的最小距离d,它有可能是耳中的一•个点和®屮的一•个点组成的最接近点对。所以述要考虑®中的所有点到归中的每一个点的距离，一一比较之后得出一

3、个最小值，再和心〃2比较，这就得后结果。3.接下来是具体算法实现的步骤：1.把待计算的点S分成两部分®52：重要的如何去划分，这里采用在二维平而上的中线(用横坐标的最小值加上最大值的平均数)来划分。2.分别求出其最接近点的距离d

4、d2：这可以用一个递归來完成。3.计算中的所有点到$2中的每一个点的距离：这个问题是此问题的关键。首先要考虑的是，儿屮的点，是不是每一个都有可能和$2屮的某个点组成最接近点呢。答案是未必。假设中线的横坐标是X.而山中较小的值为心则必中距离中线人于d的点，它和®中任意点的距离必定人于d。所以，只用考虑符合(X-Xj

5、的是，对于每个中距离中线小于d的点，是不是巧屮的每个点都有可能和其组成最接近点呢？答案也是未必。假设一个耳中距离中线小于d的点为讣,它的纵坐标为y,那么归中距离也小于于d的点，它的纵坐标和y之差的绝对值必然小于do即一定在下图阴影部分之中。在下图中，我们观察到：将阴影部分分成6块，每块顶多有一个点。否则，任意一块中的两个点，他们的距离一定小于等于J(-J)2+(-t/)2,叩小于d,这V23和d的定义矛盾。至此，我们得到结论，不是每个孔中的点都需要计算的。我们只需要计算耳中距离中线X不超过d的点和与此点对应的符合阴影部分的®中的点。XJ11d-2/3dId♦1.在笫三步中的所有距离中

6、得到一个最小距离〃3,和/相比Z后，得岀最终答案。1.现在要考虑的是这个算法和基本算法的0(/?)的时间复杂度相比，它有优越性么？假设问题的规模为n,在这个算法中，它的分割步骤和介并步骤总共耗时0(/1)o因此,算法耗费的计算时间为厂⑺)满足递归方程T(n)=0(1)/?<42T(n/2)+0(n)n>4解此方程得T(n)=0(nlogn)。源代码因课本上的关键代码是用C++编写的。本人不善于用C++,故进行修改并用C实现。#include#include#defineMAX50intpointlzpoint2fx[MAX];floatpoint[M

7、AX][2];floatdistance(inta.intb){//两点间距离floatdx,dy;dx=point⑻[0]-point[b][0];dy=point⑻[1]-point[b][l];return(sqrt(dx*dx+dy*dy));}voidrecord(inta」ntb){//用pointl.point2来记录最接近点的编号。if(pointl==・l){pointl=a;point2=b;}elseif(distance(arb)

8、n){//分治法求最接近距离floatdrdl,d2rmid;intij,k;if((n-m)==l){d=distance(x[m],x[n]);record(刈m]fx[n]);returnd;}if((n-m)==2){d=distance(x[m],刈m+1]);dl=distance(x[m],x[n]);d2=distance(x[m+l]/x[n]);if(d<=dl8t&d<=d2){record(x[m]fx[m+l]);returnd;