分治法解最接近点对问题

算法分析与设计实验报告2014-2015第一学期实验一：用分治法解最接近点对问题指导教师：cccc实验时间：2014年10月28日实验地点：计算中心二楼班级：计ccc学号：124cc08姓名：杨cc成绩：实验一用分治法解最接近点对问题的实验一、实验内容：实践名称：用分治法解最接近点对问题的实验时间安排：3学时一、实验目的通过上机实验，要求掌握分治法的问题描述、算法设计思想、程序设计和算法复杂性分析等。二、实验环境装有VisualC＋＋6.0的计算机。本次实验共计3学时。三、实验内容1、熟悉分治算法思想掌握如何创建应用程序。掌握对最接近点对问题描述，及如何运用算法策略对问题解决和实现。2、掌握如何编译程序理解编译过程中的错误信息，并掌握如何排错。3、掌握如何调试程序掌握如何通过设置断点来单步调试程序，如何查看当前变量的值。4、实验题：完成用分治法解最接近点对问题的实验。要求：实现该实验结果。通过该实验题，解决最接近点对问题。二、实验报告要求1、报告内容包括实验目的、实验内容、实验步骤，实验结果和心得体会五部分；其中实验步骤包括算法分析、算法设计、算法实现主要步骤。2、实验报告以电子文档形式发送到邮箱[e-mail]截止时间统一为下周二前。1)算法分析问题描述：已知集合S中有n个点，求这些点中最近的两个点的距离算法分析:分治法的思想就是将S进行拆分，分为2部分求最近点对。将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点之间的距离才会小于δ，最小点对计算才有意义。figure2对于SL虚框范围内的p点，在SR虚框中与p点距离小于δ的顶多只有六个点，就是图二右图中的2个正方形的6的顶点。这个可以反推证明，如果右边这2个正方形内有7个点与p点距离小于δ，例如q点，则q点与下面正方形的四个顶点距离小于δ，则和δ为SL和SR中的最小点对距离相矛盾。因此对于SL虚框中的p点，不需求出p点和右边虚线框内所有点距离，只需计算SR中与p点y坐标距离最近的6个点，就可以求出最近点对，节省了比较次数。figure3如上图：把距离分割线中间2δ范围内的点装入temp数组中，按照x坐标从小打到排序。若要找出距离P点最近的点，只需要和其下面六个点比较即可（具有稀疏性质）。再找出距离S1点最近的距离，也是之和其下六个点比较即可。依次对S2,S3,s4,……..,sm进行同样操作。而且对于下图情况同样适用figure4这样，先将带状区间的点按y坐标排序，然后线性扫描，这样合并的时间复杂度为O(nlogn)，2)算法实现#includeiostream#includecstring#includecstdio#includecmath#includealgorithmusingnamespacestd;constdoubleINF=1e20;//用于初始化constintN=100005;//用于申请数组长度为NstructPoint//构造点{doublex;doubley;}point[N];intn;inttmpt[N];//用于保存距离mid为d的长度中的点boolcmpx(constPoint&a,constPoint&b)//按x坐标从小到大排序Point数组{returna.xb.x;}boolcmpy(constint&a,constint&b)//按y坐标从小到大排序Point数组{returnpoint[a].ypoint[b].y;}doublemin(doublea,doubleb){returnab?a:b;}doubledis(inti,intj)//求下标为i和j的两点的Point，的距离{returnsqrt((point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y));}doubleClosestPair(intleft,intright)//最近点对距离，递归求解{doubleMinDistance=INF;if(left==right)returnMinDistance;if(left+1==right)returndis(left,right);intmid=(left+right)1;doubled1=ClosestPair(left,mid);//向左递归doubled2=ClosestPair(mid+1,right);//向右递归MinDistance=min(d1,d2);inti,j,k=0;for(i=left;i=right;i++){if(fabs(point[mid].x-point[i].x)=d)//找出里mid距离d以内的点，保存在tmpt中tmpt[k++]=i;}sort(tmpt,tmpt+k,cmpy);for(i=0;ik;i++)//tmpt中的点两两比较找出最小值{for(j=i+1;jk&&ji+6&&point[tmpt[j]].y-point[tmpt[i]].yd;j++){doubled3=dis(tmpt[i],tmpt[j]);if(MinDistanced3)MinDistance=d3;}}returnd;}voidinput()//输入{for(inti=0;in;i++)scanf(%lf%lf,&point[i].x,&point[i].y);sort(point,point+n,cmpx);}voidoutput()//输出{printf(%.2lf\n,ClosestPair(0,n-1));}voidsolve(){while(scanf(%d,&n),n)//n个点{input();//处理输入output();//处理输出}}intmain(){solve();return0;}3)实验结果杭电ACMonlinejudge1007最近点对，正确。4)心得体会算法是编程的灵魂，是学习计算机的学生应修的内功，好好学习算法不仅更好的编程，而且培养我们锲而不舍的精神，提高分析问题的能力。