分治算法之平面最接近点问题.

《分治算法之平面最接近点问题.》由会员分享，可在线阅读，更多相关《分治算法之平面最接近点问题.（14页珍藏版）》请在金锄头文库上搜索。

1、分治算法的应用课程名称： 算法设计与分析 院 系： 计算机科学与信息工程学院 学生姓名： * 学 号： * 专业班级： *指导教师： * 2013年12月27日分治算法的应用摘 要：分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。如果分解得到的子问题相对来说还太大，则可反复使用分治法策略将这些子问题分成更小的同类型子问题，必要时逐步合并这些子问题的和，最终就可得到原问题的解。有分治法的基本思想我们了解到，分治法求解很自然的可以利用一个递归过程来表示，可以这样说分治法就是一种找大规模问题与小规模问题的关系，是递归设计方法的一种具体策略。分

2、治法与动态规划法实际上都是递归思想的运用, 二者的根本策略都是对问题进行分解，找到大规模与小规模的关系，然后通过解小规模的解，得出大规模的解,不同点： 适用于分治法的问题分解成子问题后，各子问题间无公共子问题，而动态规划法相反。大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。子问题规模大致相同、平衡，这样最有效,通常 k = 2 , 从分治法的一般设计模式可以看出，用它设计出的程序一般是一个递归过程。因此，分治法的计算效率通常可以用递归方程来进行分析。 关键词

3、：分治法 平面最接近点 二分法 递归 子问题目 录第1章 绪论31.1 分治算法的知识介绍31.2 分治算法的问题描述3第2章 分治算法的理论知识52.1数据结构和算法效率52.2分治算法之折半查找5第3章 平面最接近点问题63.1 平面最接近点问题描述63.2 平面最接近点问题算法分析73.3 测试结果与分析9第4章 结论11参考文献12第1章 绪论1.1 分治算法的知识介绍 分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。如果分解得到的子问题相对来说还太大，则可反复使用分治法策略将这些子问题分成更小的同类型子问题，必要时逐步合并这些

4、子问题的和，最终就可得到原问题的解。有分治法的基本思想我们了解到，分治法求解很自然的可以利用一个递归过程来表示，可以这样说分治法就是一种找大规模问题与小规模问题的关系，是递归设计方法的一种具体策略。分治法解题的一般步骤为是：（1）分解，将要解决的问题划分成若干规模较小的同类问题。（2）求解，当子问题划分得足够小时，用较简单的方法解决。（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。常见的三种分治方法：（1）二分法，一种每次将原问题分解为两个子问题的分治法，是一分为二的哲学思想的应用。这种方法很常用，由此法产生了许多经典的算法和数据结构。（2）合并法，分解并在解决之前合并是一种分

5、治法的变形，其特点是将分解出的子问题在解决之前合并。（3）管道传输分治法，管道传输分治法是一种分治的变形，它利用某种称为“管道”的数据结构在递归调用结束前将其中的某些结果返回。此方法经常用来减少算法的深度。 1.2 分治算法的问题描述 当求解一个输入规模为n且区只有相当大的问题时，用蛮力策略效率一般的不到保证，若问题满足以下条件，就能用分治法来提高解决问题的效率。（1） 能将这n个数据分解成k个不同的子集合，且得到的K个子问题是可以独立求解的子问题，其中1kn。（2） 分解所得到的子问题与原问题具有相似的结构，便于利用递归或者循环结构。（3） 再求出这些子问题的解之后就可以推解原问题的解。（4

6、） 特别地，对于一些分解后不独立的子问题，即表现在子问题之间包含了公共的子问题，虽然分解后的子问题不独立，但可以通过对重叠子问题进行专门处理，并对所有问题合并并设计，就可以用二分策略解决。（5） 平面最接近点问题描述：给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。如果这n个点在数轴上，则可以转化为求两个实数差值最小的点，即为一维最接近点问题，否则为二维最接近点问题，这n个点在一个二维的坐标轴上。 第2章 分治算法的理论知识2.1数据结构和算法效率对于平面最接近点问题，我们首先想到的是用暴力的方法，我们只要将每一点与其他n-1个点的距离算出，找出达到最小距离的两个

7、点即可，即所谓的循环遍历法，这样的时间复杂度是O(n2)，这个问题显然满足分治法的第一个和第二个适用条件，我们将所给平面上n个点的集合S分成两个子集S1和S2，每个子集中约有n/2个点。然后在每个子集中递归地求最接近的点对，这样的时间复杂度是O(nlognlogn)，另外对于二维最接近点问题，我们用一个结构体来存储每个点的横纵坐标，再用一个一位数组来存储重叠的子集，再用一个数组来存储最近距离的结点，使用数组更方便输入和排序,而对于一维的问题，因为把原问题分成子问题后，重叠的自己最多只有一个，所以只用一个一位数组存储输入的数据就可以了。而且为了提高分治的效率，先对输入的数据进行排序，选取适当的分

8、割点，然后在运用分治策略。2.2分治算法之折半查找折半查找法也称为二分查找法或二分搜索法，它充分利用了元素间的次序关系，采用分治策略而较快地查找数据。现要求给出一个待查找的实例，并给出二分搜索算法，编写程序利用此算法实现查找。它的基本思想是，将n个元素分成个数大致相同的两半，取an/2与欲查找的x作比较，如果x=an/2则找到x，算法终止。如果xan/2，则我们只要在数组a的右半部继续搜索x。二分搜索法的应用极其广泛，其主要思想也是递归，即来源于分治递归算法，而且它的思想易于理解，但是要写一个正确的二分搜索算法也不是一件简单的事。第3章 平面最接近点问题3.1 平面最接近点问题描述我们用分治的

9、方法，将所给平面上n个点的集合S分成两个子集S1和S2，每个子集中约有n/2个点。然后在每个子集中递归地求最接近的点对。在这里，一个关键的问题是如何实现分治法中的合并步骤，即由S1和S2的最接近点对，如何求得原集合S中的最接近点对。如果这两个点分别在S1和S2中，问题就变得很简单了，但是如果这两个点一个在S1中，一个在S2中，问题就变得复杂了，我们首先考虑一维的情形，对于一维的情形，假设我们用m点将S分为S1和S2两个集合，这样一来，对于所有的p(S1中的点)和q(S2中的点)，有pq。递归地在S1和S2上找出其最接近点对p1,p2和q1,q2，并设d = min |p1-p2| , |q1-

10、q2| ，由此易知，S中最接近点对或者是p1,p2，或者是q1,q2，或者是某个q3,p3，如图1所示。 如果最接近点对是q3,p3，即|p3-q3|d，则p3和q3两者与m的距离都不超过d，且在区间(m-d,d和(d,m+d各有且仅有一个点。这样，就可以在线性时间内实现合并，时间的复杂度是O(nlogn)。图3-1 一维情形在二维情形下，类似的，利用分治法，由图3-1可见，形成的宽为2d的带状区间，最多可能有n个点，合并时间最坏情况下为n2,。但是，P1和P2中的点具有以下稀疏的性质，对于P1中的任意一点，P2中的点必定落在一个d X 2d的矩形中，且最多只需检查六个点（鸽巢原理）， 这样，

11、先将带状区间的点按y坐标排序，然后线性扫描，这样合并的时间复杂度为O(nlogn)，几乎为线性了。 图3-2二维情形3.2 平面最接近点问题算法分析给你n个点，且这n个点都在x坐标轴上，求在平面上距离最近的两个点，输入数据为点的个数和n个点的坐标，输入数据个数为0时终止程序，如果两个点的坐标相等，则距离为0，一维问题主要代码实现如下：void Closest_Pair(int left,int right)if(left=right) return;if(left+1=right)if(dataright-dataleft 1;Closest_Pair(left,mid);Closest_Pa

12、ir(mid+1,right);if(datamid+1 - datamid 1; double d1 = Closest_Pair(left,mid); double d2 = Closest_Pair(mid+1,right); if(d1d2) p0=pointleft.x;p1=pointleft.y;p2=pointmid.x;p3=pointmid.y; else p0=pointmid+1.x;p1=pointmid+1.y;p2=pointright.x;p3=pointright.y; d = min(d1,d2); int i,j,k=0; /分离出宽度为d的区间 for(i = left; i = right; i+) if(fabs(pointmid.x-pointi.x) = d) tmptk+ = i; sort(tmpt,tmpt+k,cmpy);