分治法解最接近点对问题

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部分求最近点对。

3、将S拆分左右两部分为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虚

4、框范围内的p点，在SR虚框中与p点距离小于的顶多只有六个点，就是图二右图中的2个正方形的6的顶点。这个可以反推证明，如果右边这2个正方形内有7个点与p点距离小于，例如q点，则q点与下面正方形的四个顶点距离小于，则和为SL和SR中的最小点对距离相矛盾。因此对于SL虚框中的p点，不需求出p点和右边虚线框内所有点距离，只需计算SR中与p点y坐标距离最近的6个点，就可以求出最近点对，节省了比较次数。 figure 3如上图：把距离分割线中间2范围内的点装入temp数组中，按照x坐标从小打到排序。若要找出距离P点最近的点，只需要和其下面六个点比较即可（具有稀疏性质）。再找出距离S1点最近的距离

5、，也是之和其下六个点比较即可。依次对S2,S3,s4,.,sm 进行同样操作。 而且对于下图情况同样适用figure 4   这样，先将带状区间的点按y坐标排序，然后线性扫描，这样合并的时间复杂度为O(nlogn)，2) 算法实现#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<algorithm>using namespace std;const double INF =1e20; / 用于初始化cons

6、t 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.x<b.x;bool cmpy(const int &a,const int &b)/ 按y坐标从小到大排序Point数组return pointa.y<pointb.y;double min( double

7、a,double b)return a<b?a:b;double dis(int i,int j) / 求下标为 i和 j的两点的Point，的距离return sqrt( (pointi.x-pointj.x)*(pointi.x-pointj.x)+(pointi.y-pointj.y)*(pointi.y-pointj.y) );double ClosestPair(int left,int right) /最近点对距离，递归求解double MinDistance=INF;if(left=right)return MinDistance;if(left+1=right)retur

8、n dis(left,right);int mid=(left+right)>>1;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以内的点，保存在 tmpt 中tmptk+=i;sort(tmpt,tmpt+k,cmpy);for(i=0;i<

9、k;i+) / tmpt 中的点两两比较找出最小值for(j=i+1;j<k&&j<i+6&&pointtmptj.y-pointtmpti.y<d;j+)double d3=dis(tmpti,tmptj);if(MinDistance>d3)MinDistance=d3;return d;void input() /输入for(int i=0;i<n;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();