您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 资本运营 > 分治法解最接近点对问题
算法分析与设计实验报告2014-2015第一学期实验一:用分治法解最接近点对问题指导教师:cccc实验时间:2014年10月28日实验地点:计算中心二楼班级:计ccc学号:124cc08姓名:杨cc成绩:实验一用分治法解最接近点对问题的实验一、实验内容:实践名称:用分治法解最接近点对问题的实验时间安排:3学时一、实验目的通过上机实验,要求掌握分治法的问题描述、算法设计思想、程序设计和算法复杂性分析等。二、实验环境装有VisualC++6.0的计算机。本次实验共计3学时。三、实验内容1、熟悉分治算法思想掌握如何创建应用程序。掌握对最接近点对问题描述,及如何运用算法策略对问题解决和实现。2、掌握如何编译程序理解编译过程中的错误信息,并掌握如何排错。3、掌握如何调试程序掌握如何通过设置断点来单步调试程序,如何查看当前变量的值。4、实验题:完成用分治法解最接近点对问题的实验。要求:实现该实验结果。通过该实验题,解决最接近点对问题。二、实验报告要求1、报告内容包括实验目的、实验内容、实验步骤,实验结果和心得体会五部分;其中实验步骤包括算法分析、算法设计、算法实现主要步骤。2、实验报告以电子文档形式发送到邮箱jsjalg@yeah.net截止时间统一为下周二前。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)心得体会算法是编程的灵魂,是学习计算机的学生应修的内功,好好学习算法不仅更好的编程,而且培养我们锲而不舍的精神,提高分析问题的能力。
本文标题:分治法解最接近点对问题
链接地址:https://www.777doc.com/doc-6002348 .html