最新求谱列表
跳转到第页
5000 朝鲜舞蹈音乐简谱
7-3 请天恩老师记谱最近更新小说列表
[武侠修真]寒香寂寞 02:41:56
[都市言情]烟斗老哥 02:33:46
[历史军事]六月浩雪 02:31:36
[历史军事]颓废的烟121 02:28:42
[玄幻魔法]天蓝色月 02:26:13
[都市言情]茯苓半夏 02:16:05
[玄幻魔法]X战匪 02:12:02
[历史军事]绿豆皮 02:08:04
[历史军事]御宅烟魔 01:59:50
[科幻小说]路人飞 01:54:10
[都市言情]黑眼圈不要啊 01:46:09
[玄幻魔法]雪煮馒头 01:42:57
[都市言情]东流无歇 01:34:45
[都市言情]三十二变 01:28:44
[历史军事]白菜汤 01:26:39
[历史军事]殊彦 01:12:16
[其他类型]老螃蟹作品集 01:08:48
[都市言情]步行天下 00:47:39
[都市言情]老施 00:29:25
[历史军事]冉小狐 00:20:13
入库新小说
[历史]还是那个我
[历史]一缕相思
[历史]寒兔
[都市]我是木木
[玄幻]恋月儿
[都市]落随心
[历史]独孤求剩
[历史]唐七公子
[历史]三元
[历史]偏叶
[都市]野蔓
[网游]天上蓝瑾
[历史]睡笑呆
[历史]寻找失落的爱情
[都市]六月离歌
[都市]白玉求瑕
[历史]秋瞳羽莲
[玄幻]月下独醉
[都市]北北伞
[历史]恋家的蜗牛
友情连接：求魔最新章节（耳根）_求魔无弹窗_560小说网
& 求魔最新章节列表
魔前一叩三千年，回首凡尘不做仙，只为她……掌缘生灭 请看耳根作品《求魔》
&推荐阅读：
《求魔》正文2546人阅读
&&&&在应用中，常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉及这些几何对象的问题中，常需要了解其邻域中其他几何对象的信息。例如，在空中交通控制问题中，若将飞机作为空间中移动的一个点来看待，则具有最大碰撞危险的2架飞机，就是这个空间中最接近的一对点。这类问题是计算几何学中研究的基本问题之一。下面我们着重考虑平面上的最接近点对问题。
&&&&最接近点对问题的提法是:给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。
&&&&严格地说，最接近点对可能多于1对。为了简单起见，这里只限于找其中的一对。
&&&&这个问题很容易理解，似乎也不难解决。我们只要将每一点与其他n-1个点的距离算出，找出达到最小距离的两个点即可。然而，这样做效率太低，需要O(n2)的计算时间。在问题的计算复杂性中我们可以看到，该问题的计算时间下界为Ω(nlogn)。这个下界引导我们去找问题的一个θ(nlogn)算法。
&&&&这个问题显然满足分治法的第一个和第二个适用条件，我们考虑将所给的平面上n个点的集合S分成2个子集S1和S2，每个子集中约有n/2个点，·然后在每个子集中递归地求其最接近的点对。在这里，一个关键的问题是如何实现分治法中的合并步骤，即由S1和S2的最接近点对，如何求得原集合S中的最接近点对，因为S1和S2的最接近点对未必就是S的最接近点对。如果组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决。但是，如果这2个点分别在S1和S2中，则对于S1中任一点p，S2中最多只有n/2个点与它构成最接近点对的候选者，仍需做n2/4次计算和比较才能确定S的最接近点对。因此，依此思路，合并步骤耗时为O(n2)。整个算法所需计算时间T(n)应满足:　
T(n)=2T(n/2)+O(n2)
&&&& 它的解为T(n)=O(n2)，即与合并步骤的耗时同阶，显示不出比用穷举的方法好。从解递归方程的套用公式法，我们看到问题出在合并步骤耗时太多。这启发我们把注意力放在合并步骤上。
&&&&为了使问题易于理解和分析，我们先来考虑一维的情形。此时S中的n个点退化为x轴上的n个实数x1,x2,..,xn。最接近点对即为这n个实数中相差最小的2个实数。我们显然可以先将x1,x2,..,xn排好序，然后，用一次线性扫描就可以找出最接近点对。这种方法主要计算时间花在排序上，因此如在排序算法中所证明的，耗时为O(nlogn)。然而这种方法无法直接推广到二维的情形。因此，对这种一维的简单情形，我们还是尝试用分治法来求解，并希望能推广到二维的情形。
&&&&假设我们用x轴上某个点m将S划分为2个子集S1和S2，使得S1={x∈S|x≤m}；S2={x∈S|x&m}。这样一来，对于所有p∈S1和q∈S2有p
&&&&递归地在S1和S2上找出其最接近点对{p1,p2}和{q1,q2}，并设δ=min{|p1-p2|,|q1-q2|}，S中的最接近点对或者是{p1,p2}，或者是{q1,q2}，或者是某个{p3,q3}，其中p3∈S1且q3∈S2。如图1所示。
一维情形的分治法
&&&&我们注意到，如果S的最接近点对是{p3,q3}，即|p3-q3|&δ，则p3和q3两者与m的距离不超过δ，即|p3-m|&δ，|q3-m|&δ，也就是说，p3∈(m-δ,m]，q3∈(m,m+δ]。由于在S1中，每个长度为δ的半闭区间至多包含一个点（否则必有两点距离小于δ），并且m是S1和S2的分割点，因此(m-δ,m]中至多包含S中的一个点。同理，(m,m+δ]中也至多包含S中的一个点。由图1可以看出，如果(m-δ,m]中有S中的点，则此点就是S1中最大点。同理，如果(m,m+δ]中有S中的点，则此点就是S2中最小点。因此，我们用线性时间就能找到区间(m-δ,m]和(m,m+δ]中所有点，即p3和q3。从而我们用线性时间就可以将S1的解和S2的解合并成为S的解。也就是说，按这种分治策略，合并步可在O(n)时间内完成。这样是否就可以得到一个有效的算法了呢？还有一个问题需要认真考虑，即分割点m的选取，及S1和S2的划分。选取分割点m的一个基本要求是由此导出集合S的一个线性分割，即S=S1∪S2
，S1∩S2=Φ，且S1{x|x≤m}；S2{x|x&m}。容易看出，如果选取m=[max(S)+min(S)]/2，可以满足线性分割的要求。选取分割点后，再用O(n)时间即可将S划分成S1={x∈S|x≤m}和S2={x∈S|x&m}。然而，这样选取分割点m，有可能造成划分出的子集S1和S2的不平衡。例如在最坏情况下，|S1|=1，|S2|=n-1，由此产生的分治法在最坏情况下所需的计算时间T(n)应满足递归方程:
T(n)=T(n-1)+O(n)
&&&&它的解是T(n)=O(n2)。这种效率降低的现象可以通过分治法中&平衡子问题&的方法加以解决。也就是说，我们可以通过适当选择分割点m，使S1和S2中有大致相等个数的点。自然地，我们会想到用S的n个点的坐标的中位数来作分割点。在选择算法中介绍的选取中位数的线性时间算法使我们可以在O(n)时间内确定一个平衡的分割点m。
&&&& 至此，我们可以设计出一个求一维点集S中最接近点对的距离的算法CPAIR1如下。
function CPAIR1(S);
then δ=|x[2]-x[1]| // x[1..n]存放的是S中n个点的坐标
else if (|S|=1)
then δ:=∞
m:=S中各点的坐标值的中位数;
构造S1和S2,使S1={x∈S|x≤m}，S2={x∈S|x&m}; δ1:=CPAIRI(S1); δ2:=CPAIRI(S2);
p:=max(S1); q:=min(S2);
δ:=min(δ1,δ2,q-p);
return(δ);
由以上的分析可知，该算法的分割步骤和合并步骤总共耗时O(n)。因此，算法耗费的计算时间T(n)满足递归方程：
&&&& 解此递归方程可得T(n)=O(nlogn)。
&&&&这个算法看上去比用排序加扫描的算法复杂，然而这个算法可以向二维推广。
&&&&下面我们来考虑二维的情形。此时S中的点为平面上的点，它们都有2个坐标值x和y。为了将平面上点集S线性分割为大小大致相等的2个子集S1和S2，我们选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1={p∈S|px≤m}和S2={p∈S|px&m}。从而使S1和S2分别位于直线l的左侧和右侧，且S=S1∪S2 。由于m是S中各点x坐标值的中位数，因此S1和S2中的点数大致相等。
&&&&递归地在S1和S2上解最接近点对问题，我们分别得到S1和S2中的最小距离δ1和δ2。现设δ=min(δ1,δ1)。若S的最接近点对(p,q)之间的距离d(p,q)&δ则p和q必分属于S1和S2。不妨设p∈S1，q∈S2。那么p和q距直线l的距离均小于δ。因此，我们若用P1和P2分别表示直线l的左边和右边的宽为δ的2个垂直长条，则p∈P1，q∈P2，如图2所示。
图2 距直线l的距离小于δ的所有点
&&&& 在一维的情形，距分割点距离为δ的2个区间(m-δ,m](m,m+δ]中最多各有S中一个点。因而这2点成为唯一的末检查过的最接近点对候选者。二维的情形则要复杂些，此时，P1中所有点与P2中所有点构成的点对均为最接近点对的候选者。在最坏情况下有n2/4对这样的候选者。但是P1和P2中的点具有以下的稀疏性质，它使我们不必检查所有这n2/4对候选者。考虑P1中任意一点p,它若与P2中的点q构成最接近点对的候选者，则必有d(p,q)&δ。满足这个条件的P2中的点有多少个呢？容易看出这样的点一定落在一个δ×2δ的矩形R中，如图3所示。
包含点q的δ×2δ的矩形R
&&&&由δ的意义可知P2中任何2个S中的点的距离都不小于δ。由此可以推出矩形R中最多只有6个S中的点。事实上，我们可以将矩形R的长为2δ的边3等分，将它的长为δ的边2等分，由此导出6个（δ/2）×（2δ/3）的矩形。如图4(a)所示。
矩形R中点的稀疏性
&&&&若矩形R中有多于6个S中的点，则由鸽舍原理易知至少有一个δ×2δ的小矩形中有2个以上S中的点。设u,v是这样2个点，它们位于同一小矩形中，则
&&&& 因此d(u,v)≤5δ/6&δ 。这与δ的意义相矛盾。也就是说矩形R中最多只有6个S中的点。图4(b)是矩形R中含有S中的6个点的极端情形。由于这种稀疏性质，对于P1中任一点p，P2中最多只有6个点与它构成最接近点对的候选者。因此，在分治法的合并步骤中，我们最多只需要检查6×n/2=3n对候选者，而不是n2/4对候选者。这是否就意味着我们可以在O(n)时间内完成分治法的合并步骤呢？现在还不能作出这个结论，因为我们只知道对于P1中每个S1中的点p最多只需要检查P2中的6个点，但是我们并不确切地知道要检查哪6个点。为了解决这个问题，我们可以将p和P2中所有S2的点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中，所以它们在直线l上的投影点距p在l上投影点的距离小于δ。由上面的分析可知，这种投影点最多只有6个。因此，若将P1和P2中所有S的点按其y坐标排好序，则对P1中所有点p，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者，对P1中每一点最多只要检查P2中排好序的相继6个点。
&&&&至此，我们可以给出用分治法求二维最接近点对的算法CPAIR2如下:
function CPAIR2(S);
then δ:=S中这2点的距离
else if |S|=0
then δ:=∞
1. m:=S中各点x坐标值的中位数; 构造S1和S2，使S1={p∈S|px≤m}和S2={p∈S|px&m}
2. δ1:=CPAIR2(S1);δ2:=CPAIR2(S2);
3. δm:=min(δ1,δ2);
4. 设P1是S1中距垂直分割线l的距离在δm之内的所有点组成的集合， P2是S2中距分割线l的距离在δm之内所有点组成的集合。将P1和P2中的点依其y坐标值从小到大排序，并设P1*和P2*是相应的已排好序的点列;
5.&通过扫描P1*以及对于P1*中每个点检查P2*中与其距离在δm之内的所有点(最多6个)可以完成合并。当P1*中的扫描指针逐次向上移动 时，P2*中的扫描指针可在宽为2δm的一个区间内移动。设δl是按 这种扫描方式找到的点对间的最小距离;
6. δ=min(δm,δl);
return(δ);
下面我们来分析一下算法CPAIR2的计算复杂性。设对于n个点的平面点集S，算法耗时T(n)。算法的第1步和第5步用了O(n)时间，第3步和第6步用了常数时间，第2步用了2T(n/2)时间。若在每次执行第4步时进行排序，则在最坏情况下第4步要用O(nlogn)时间。这不符合我们的要求。因此，在这里我们要作一个技术上的处理。我们采用设计算法时常用的预排序技术，即在使用分治法之前，预先将S中n个点依其y坐标值排好序，设排好序的点列为P*。在执行分治法的第4步时，只要对P*作一次线性扫描，即可抽取出我们所需要的排好序的点列P1*和P2*。然后，在第5步中再对P1*作一次线性扫描，即可求得δl。因此，第4步和第5步的两遍扫描合在一起只要用O(n)时间。这样一来，经过预排序处理后的算法CPAIR2所需的计算时间T(n)满足递归方程：
&&&&显而易见T(n)=O(nlogn)，预排序所需的计算时间为O(n1ogn)。因此，整个算法所需的计算时间为O(nlogn)。在渐近的意义下，此算法已是最优的了。
& & 求点集中的最近点对有以下两种方法:
设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。
1、蛮力法（适用于点的数目比较小的情况下）
&&&& 1）算法描述：已知集合S中有n个点，一共可以组成n(n-1)/2对点对，蛮力法就是对这n(n-1)/2对点对逐对进行距离计算，通过循环求得点集中的最近点对：
&&&& 2）代码描述：
double MinDistance = double.maxvalue；&&//设置一个MinDistance存储最近点对的距离，初始值为无穷大
int PointIndex1,PointIndex2；&//设置PointIndex1,PointIndex2分别存储最近点对的两个点编号
for (i=1; i& i++)&& &//循环计算n(n-1)/2对点对的距离
&&&& for (j=i+1; j&=n; j++)
&&&&&&&&&& double PointDistance = Distance(S[i],S[j]);&&&//求得point i和point j之间的距离
&&&&&&&&& &if PointDistance & MinD&&//如果当前点对距离小于最小点对距离，则设置最小点对距离等于当前点对距离
&&&&&&&&&& {
&&&&&&&&&&&&&&&& MinDistance = PointD
&&&&&&&&&&&&&&&& PointIndex1 =
&&&&&&&&&&&&&&&& PointIndex2 =
&&&&&&&&&&& }
&&&& 3）算法时间复杂度：算法一共要执行 n(n-1)/2次循环，因此算法复杂度为O(n2)
&&& &1）算法描述：已知集合S中有n个点，分治法的思想就是将S进行拆分，分为2部分求最近点对。算法每次选择一条垂线L，将S拆分左右两部分为SL和SR，L一般取点集S中所有点的中间点的x坐标来划分，这样可以保证SL和SR中的点数目各为n/2，
（否则以其他方式划分S，有可能导致SL和SR中点数目一个为1，一个为n-1，不利于算法效率，要尽量保持树的平衡性）
依次找出这两部分中的最小点对距离：δL和δR，记SL和SR中最小点对距离δ&=
min（δL，δR），如图1：
&&&& 以L为中心，δ为半径划分一个长带，最小点对还有可能存在于SL和SR的交界处，如下图2左图中的虚线带，p点和q点分别位于SL和SR的虚线范围内，在这个范围内，p点和q点之间的距离才会小于δ，最小点对计算才有意义。
&&&&&&对于SL虚框范围内的p点，在SR虚框中与p点距离小于δ的顶多只有六个点，就是图二右图中的2个正方形的6的顶点。这个可以反推证明，如果右边这2个正方形内有7个点与p点距离小于δ，例如q点，则q点与下面正方形的四个顶点距离小于δ，则和δ为SL和SR中的最小点对距离相矛盾。因此对于SL虚框中的p点，不需求出p点和右边虚线框内所有点距离，只需计算SR中与p点y坐标距离最近的6个点，就可以求出最近点对，节省了比较次数。
（否则的话，最坏情形下，在SR虚框中有可能会有n/2个点，对于SL虚框中的p点，每次要比较n/2次，浪费了算法的效率）
&&& &代码描述：
&&&& 1）对点集S的点x坐标和y坐标进行升序排序，获得点集Sx和Sy
&&&& 2）令δ=∞;&&&//δ为最小点位距离
&&&&&3）Divide_conquer（Sx，Sy，δ）&&//分治法
&&&&&&&&&&&& if （Sx.count=1） then&δ=∞;&&&&//如果Sx中只有一个点，则δ=∞
&&&&&&&&&&&&&&&&&&return&δ;
&&&&&&&&&&&& else if（Sx.count=2 and d（Sx.[0],Sx.[1]）&δ）&//如果Sx中只有2个点，则δ为两点之间距离
&&&&&&&&&&&&&&&&&&&δ=d（Sx.[0],）Sx.[1]）;&
&&&&&&&&&&&&&&&&&&&return&δ;
&&&&&&&&&&&& else&&&&//如果Sx中多于2个点，则将Sx,Sy分治，以中心点画线，将Sx分为左右两部分SxL和SxR，Sy分为SyL和SyR
&&&&&&&&&&&&&&&&&& j1=1,j2=1,k1=1,k2=1;
&&&&&&&&&&&&&&&&&&&mid =&Sx.count/2;&&&//mid为Sx中的中间点点号
&&&&&&&&&&&&&&&&&& L =&Sx.[mid].x;&&&&&&//L为Sx中的中间点x坐标
&&&&&&&&&&&&&&&&&&&for(i=1,i&Sx.count,i++)
&&&&&&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&&&&&&& if(i&=mid)&&&&&//将Sx中间线以左地方的点存入到SxL，新数组保持原来的升序性质
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&SxL[k1] =&Sx[i]&&&k1++;
&&&&&&&&&&&&&&&&&&&&&&&&&else&&&//将Sx中间线以右的地方的点存入到SxR，新数组保持原来的升序性质
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&SxR.count[k2] = Sx[i]&& k2++;
&&&&&&&&&&&&&&&&&&&&&&&& if(Sy[i].x&&L)&&&//将Sy中间线以左地方的点存入到SyL，新数组保持原来的升序性质
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&SyL[j1] = Sx[i]&& j1++;
&&&&&&&&&&&&&&&&&&&&&&& &else&&&//将Sy中间线以右地方的点存入到SyR，新数组保持原来的升序性质
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&SyR[j2] = Sx[i]&&
j2++;
&&&&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&δL&=&Divide_conquer（SxL，SyL，δ）;&&&&//获取Sx中的的最小点位距离δL
&&&&&&&&&& &&&δR&=&Divide_conquer（SxR，SyR，δ）;&&&//获取Sy中的的最小点位距离δR
&&&&&&&&&&&&&&δ= min (δL,δR);
&&&&&&&&&&&&&&δ=merge(SyL，SyR，δ);&&&&//获Sx中Sy交界处的最小点位距离，并综合&δL和δR&求出点集的最小点位距离δ
&&&&&&return&δ;
&&&&&&函数merge(SyL，SyR，δ)
&&&&&&merge(SyL，SyR，δ)
&&&&&&&&& i1=1,i2=1;
&&&&&&&& &for(i=1,i&SyL.count,i++)&&&//获取SyL中在左边虚框(距离小于δ)内的点，存入到S'yL中，新数组保持原来的升序性质
&&&&&&&&&&&&& if(SyL[i].x&L-δ)
&&&&&&&&&&&&&&&&& then S'yL[i1]= SyL[i], i1++,
&&&&&&&&&& }
&&&&&&&&& for(i=1,i&SyR.count,i++)&&//获取SyR中在右边虚框(距离小于δ)内的点，存入到S'yR中，新数组保持原来的升序性质
&&&&&&&&& {
&&&&&&&&&&&&& if(SyR[i].x&L+δ)
&&&&&&&&&&&&& then S'yR[i2]= SyR[i], i2++,
&&&&&&&&&&}
&&&&&&&&& t=1;
&&&&&&&&& for(i=1,i&S'yL.count,i++)
&&&&&&&&& &{&&&&&
&&&&&&&&&&&&&&& while(S'yR[t].y& S'yL[t].y&and t & SyR.count)&&//获取点集S'yR内距离点S'yL[t]y坐标最接近的点号
&&&&&&&&&&&&&&&&{ t++; }
&&&&&&&&&&&&&&& for( j= max(1,t-3), j&=min(t+3,S'yR.count),j++)& &//计算S'yR中的点与S'yL[t]y坐标相邻的六个点的距离
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&& if(d(S'yL[i],S'yL[j])&δ)&&&&//如果前两点之间距离小于δ
&&&&&&&&&&&&&&&&&&&&& then&δ = d(S'yL[i],S'yL[j]);&&&//则最小点位距离δ为当前两点之间距离
&&&&&&&&&&&&&&& }
&&&&&&&& &return&δ
&3）算法时间复杂度：
&&&&& 首先对点集S的点x坐标和y坐标进行升序排序，需要循环2nlogn次，复杂度为O(2nlogn)
&&&&& 接下来在分治过程中，对于每个S'yL中的点，都需要与S'yR中的6个点进行比较
&&&&&&&&&&& O(n)= 2O(n/2) + (n/2)*6&&（一个点集划分为左右两个点集，时间复杂度为左右两个点集加上中间区域运算之和）
&&&&&&其解为O(n)& O(3nlogn)
&&&&&因此总的时间复杂度为O(3nlogn)，比蛮力法的O(n2)要高效。
( 可是，我用这个方法编写的代码交上去是WA)
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：101024次
积分：1894
积分：1894
排名：第10585名
原创：91篇
转载：23篇
评论：11条
(2)(3)(19)(21)(23)(1)(8)(13)(19)(4)(1)}