搜索
深圳大学实验报告课程名称：算法分析与复杂性理论实验项目名称：实验二分治法求最近点对问题学院：计算机与软件学院专业：软件工程指导教师：杨烜报告人：文成学号：2150230509班级：15级软工学术型实验时间：2015-10-22实验报告提交时间：2015-10-24教务部制实验目的与要求：实验目的：（1）掌握分治法思想。（2）学会最近点对问题求解方法。实验要求1.在blackboard提交电子版实验报告，注意实验报告的书写，整体排版。2.实验报告的实验步骤部分需详细给出算法思想与实现代码之间的关系解释，不可直接粘贴代码（直接粘贴代码者视为该部分内容缺失）。3.实验报告样式可从表格下载－学生适用－在校生管理－实践教学－实验：深圳大学学生实验报告）4.源代码作为实验报告附件上传。5.在实验课需要现场运行验证。实验内容：1.对于平面上给定的N个点，给出所有点对的最短距离，即，输入是平面上的N个点，输出是N点中具有最短距离的两点。2.要求随机生成N个点的平面坐标，应用蛮力法编程计算出所有点对的最短距离。3.要求随机生成N个点的平面坐标，应用分治法编程计算出所有点对的最短距离。4.分别对N=100,1000,10000,100000，统计算法运行时间，比较理论效率与实测效率的差异，同时对蛮力法和分治法的算法效率进行分析和比较。5.利用Unity3D输出分治算法中间每个步骤的计算结果，并增设help按钮，详细解释算法思想。算法思想提示1.预处理：根据输入点集S中的x轴和y轴坐标进行排序，得到X和Y,很显然此时X和Y中的点就是S中的点。2.点数较少时的情形3.点数|S|3时，将平面点集S分割成为大小大致相等的两个子集SL和SR，选取一个垂直线L作为分割直线，考虑XL和XR，YL和YR，这里还需要排序吗？4.两个递归调用，分别求出SL和SR中的最短距离为dl和dr。5.取d=min(dl,dr)，在直线L两边分别扩展d，得到边界区域Y，Y’是区域Y中的点按照y坐标值排序后得到的点集，Y'又可分为左右两个集合Y’L和Y’R6.对于Y’L中的每一点，检查Y’R中的点与它的距离，更新所获得的最近距离实验过程及内容：（实验代码已作为附件提交，名为“算法实验二.cpp”）当点的数量小于3时，直接计算，当点的个数大于3时，采用分治法。当N=1时当N=2时只有两个点，最近点对就是这两个点测试数据为（1,1）（2,2）预期结果为d=1.414与预期结果相同使用蛮力法求最近点对，核心代码如下（计算两点之间的距离，分别将每个点与其它点的距离求出来，找出最近点距离）当N3时，使用分治法的情况核心代码如下：当N=6时，给定一组测试数据测试数据与与预期结果相同。下面随机生成N个点的平面坐标，求解最近点对。并计算时间产生随机数代码：计算时间代码分治法例举：数据处理分析：扩大N的规模做测试n10100100010000100000蛮力法1秒9秒57秒分治法1秒9秒30秒由以上数据可知，随着N的增大，分治法效率比蛮力法效率越来越高。蛮力法求解最近对问题的过程是：分别计算每一对点之间的距离，然后找出距离最小的那一对，为了避免对同一对点计算两次距离，只考虑i＜j的那些点对(Pi,Pj)。其实也就是组合的问题，即从n个点中选取两个点的所有组合情况的问题，共有（n*(n-1)）种情况。因此时间复杂度为：治法求解含有n个点的最近对问题，其时间复杂性可由下面的递推式表示：)()2(2)(nfnTnT合并子问题的解的时间f(n)＝O(n)，根据通用分治递推式可得T(n)=O(nlog2n)。111112)()1()(22)(ninijninOnninnT实验结论与体会：分治法的思想就是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题解合并得到原问题的解。通过本次试验我对分治法有了更深的了解。利用分治法可以将问题简化，这有助于我们在实际中解决一些复杂性较大的问题，提高程序的运行效率。指导教师批阅意见：成绩评定：指导教师签字：年月日备注：注：1、报告内的项目或内容设置，可根据实际情况加以调整和补充。2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。