分治法解最接近点对问题(共8页).doc

《分治法解最接近点对问题(共8页).doc》由会员分享，可在线阅读，更多相关《分治法解最接近点对问题(共8页).doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上算法分析与设计实验报告2014-2015第一学期实验一：用分治法解最接近点对问题指导教师：cccc 实验时间：2014年10月28日 实验地点：计算中心二楼 班级： 计ccc 学号： 124cc08 姓名： 杨cc 成绩： 实验一 用分治法解最接近点对问题的实验一、实验内容： 实践名称：用分治法解最接近点对问题的实验时间安排：3学时一、实验目的通过上机实验，要求掌握分治法的问题描述、算法设计思想、程序设计和算法复杂性分析等。二、实验环境装有Visual C6.0的计算机。本次实验共计3学时。三、实验内容1、熟悉分治算法思想掌握如何创建应用程序。掌握对最接近点对问题描述

2、，及如何运用算法策略对问题解决和实现。2、掌握如何编译程序理解编译过程中的错误信息，并掌握如何排错。3、掌握如何调试程序掌握如何通过设置断点来单步调试程序，如何查看当前变量的值。4、实验题：完成用分治法解最接近点对问题的实验。要求：实现该实验结果。通过该实验题，解决最接近点对问题。二、实验报告要求1、报告内容包括实验目的、实验内容、实验步骤，实验结果和心得体会五部分；其中实验步骤包括算法分析、算法设计、算法实现主要步骤。2、截止时间统一为下周二前。1) 算法分析问题描述：已知集合S中有n个点，求这些点中最近的两个点的距离算法分析:分治法的思想就是将S进行拆分，分为2部分求最近点对。将S拆分左右

3、两部分为SL和SR，L一般取点集S中所有点的中间点的x坐标来划分，这样可以保证SL和SR中的点数目各为n/2，依次找出这两部分中的最小点对距离：L和R，记SL和SR中最小点对距离= min（L，R） 以L为中心，为半径划分一个长带，最小点对还有可能存在于SL和SR的交界处，如下图2左图中的虚线带，p点和q点分别位于SL和SR的虚线范围内，在这个范围内，p点和q点之间的距离才会小于，最小点对计算才有意义。figure 2对于SL虚框范围内的p点，在SR虚框中与p点距离小于的顶多只有六个点，就是图二右图中的2个正方形的6的顶点。这个可以反推证明，如果右边这2个正方形内有7个点与p点距离小于，例如q

4、点，则q点与下面正方形的四个顶点距离小于，则和为SL和SR中的最小点对距离相矛盾。因此对于SL虚框中的p点，不需求出p点和右边虚线框内所有点距离，只需计算SR中与p点y坐标距离最近的6个点，就可以求出最近点对，节省了比较次数。figure 3如上图：把距离分割线中间2范围内的点装入temp数组中，按照x坐标从小打到排序。若要找出距离P点最近的点，只需要和其下面六个点比较即可（具有稀疏性质）。再找出距离S1点最近的距离，也是之和其下六个点比较即可。依次对S2,S3,s4,.,sm 进行同样操作。而且对于下图情况同样适用figure 4 这样，先将带状区间的点按y坐标排序，然后线性扫描，这样合并的

5、时间复杂度为O(nlogn)，2) 算法实现#include#include#include#include#includeusing namespace std;const double INF =1e20; / 用于初始化const int N=; / 用于申请数组长度为 Nstruct Point / 构造点double x;double y;pointN;int n;int tmptN; / 用于保存距离 mid 为d的长度中的点bool cmpx(const Point &a,const Point &b) / 按x坐标从小到大排序Point数组return a.xb.x;bool

6、cmpy(const int &a,const int &b)/ 按y坐标从小到大排序Point数组return pointa.ypointb.y;double min( double a,double b)return a1;double d1=ClosestPair(left,mid); /向左递归double d2=ClosestPair(mid+1,right); / 向右递归MinDistance=min (d1,d2); int i,j,k=0;for(i=left;i=right;i+)if(fabs(pointmid.x-pointi.x)=d) / 找出里 mid 距离d以内

7、的点，保存在 tmpt 中tmptk+=i;sort(tmpt,tmpt+k,cmpy);for(i=0;ik;i+) / tmpt 中的点两两比较找出最小值for(j=i+1;jk&ji+6&pointtmptj.y-pointtmpti.yd3)MinDistance=d3;return d;void input() /输入for(int i=0;in;i+)scanf(%lf %lf,&pointi.x,&pointi.y);sort(point,point+n,cmpx);void output() /输出printf(%.2lfn,ClosestPair(0,n-1);void solve() while(scanf(%d,&n),n) / n 个点 input(); / 处理输入 output(); / 处理输出 int main()solve();return 0;3) 实验结果杭电ACM onlinejudge 1007 最近点对，正确。4) 心得体会算法是编程的灵魂，是学习计算机的学生应修的内功，好好学习算法不仅更好的编程，而且培养我们锲而不舍的精神，提高分析问题的能力。专心-专注-专业