----------------------android培训、java培训、期待与您交流! ----------------------
一、实验目的和要求
(1)进一步掌握递归算法的设计思想以及递归程序的调试技术;
(2)理解这样一个观点:分治与递归经常同时应用在算法设计之中。
(3)分别用蛮力法和分治法求解最近对问题;
(4)分析算法的时间性能,设计实验程序验证分析结论。
二、实验内容
设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S,设计算法找出集合S中距离最近的点对。
三、实验环境
MyEclipse 5.5.1 GA
java
四、实验原理
1、蛮力法(适用于点的数目比较小的情况下)
1)算法描述:已知集合S中有n个点,一共可以组成n(n-1)/2对点对,蛮力法就是对这n(n-1)/2对点对逐对进行距离计算,通过循环求得点集中的最近点对
2)算法时间复杂度:算法一共要执行 n(n-1)/2次循环,因此算法复杂度为O(n2)
2、分治法
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:
图1
以L为中心,δ为半径划分一个长带,最小点对还有可能存在于SL和SR的交界处,如下图2左图中的虚线带,p点和q点分别位于SL和SR的虚线范围内,在这个范围内,p点和q点之间的距离才会小于δ,最小点对计算才有意义。
图2
对于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次,浪费了算法的效率
2)算法时间复杂度:
首先对点集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)要高效。
五、实验数据
图3 两种算法的时间复杂度对比
六、实验结果
1)输入点
2) 蛮力法
3)分治法
七、实验总结
通过这次实验,我深刻了解到分治法的实用性,有效性。当遇到规模较大的问题,用我们以前学过的方法就太不明智了。将原问题划分成若干个较小规模的子问题,再继续求解,划分,能够简化问题。递归法,是一个很重要的方法,具有结构自相似的特性,刚开始学习编写的时候遇到了很多问题,不知道要找边界,不知道如何划分问题。
---------------------- android培训、java培训、期待与您交流! ----------------------
详细请查看:http://edu.csdn.net/heima