算法与复杂性理论实验凸包问题教材.docVIP

深 圳 大 学 实 验 报 告 课程名称： 算法分析与复杂性理论 实验项目名称： 实验三 分治法求凸包问题 学院： 计算机与软件学院 专业： 软件工程 指导教师： 杨烜 报告人：文成 学号：2150230509 班级： 15级软工学术型 实验时间： 2015-10-22 实验报告提交时间： 2015-10-24 教务部制 实验目的与要求： 实验目的： （1）? （2）?。 实验要求 1.?在blackboard提交电子版实验报告，注意实验报告的书写，整体排版。 2.?实验报告的实验步骤部分需详细给出算法思想与实现代码之间的关系解释，不可直接粘贴代码（直接粘贴代码者视为该部分内容缺失）。 3.?实验报告样式可从/guide.aspx?表格下载－学生适用－在校生管理－实践教学－实验：深圳大学学生实验报告） 4.?源代码作为实验报告附件上传。 5.?在实验课需要现场运行验证。 实验内容： 1.?对于平面上给定的N个点，确定这个点集的凸包，即，输入是平面上的N个点，输出是凸包轮廓。 2.?要求随机生成N个点的平面坐标，应用蛮力法编程计算出点集凸包。 3.?要求随机生成N个点的平面坐标，应用分治法编程计算出点集凸包。 4.?分别对N=100,1000,10000,100000，统计算法运行时间，比较理论效率与实测效率的差异，同时对蛮力法和分治法的算法效率进行分析和比较。注意需要在不同数据量之间增加测试点，例如10000到100000之间需要增加20000、30000。。。，以分析效率变化趋势。 5.?利用Unity 3D输出 实验过程及内容： （实验代码已作为附件提交，名为“算法实验三.cpp”） 凸包问题的描述与定义： 凸包的定义为：平面的一个子集S被称为是“凸”的，当且进当对于任意两点p,qS，线段都完全属于S。几何S的凸包CH(S)，就是包含S的最小凸集，更准确地说，它是包含S的所有凸集的交。由此还可以推出凸包的很多性质，包括一条直线如果与凸包相交（不是相切）的话，最多交于两条边或者两个面。 　　形象地说：在一平木板（平面）上钉若干钉子（点），将一橡皮筋套上去后，会把钉子圈起来，形成一个凸边形，即为该点集的凸包。 关于用分治法求凸包问题的思路： 分治法是一种很基础的算法。基本思路是将问题分解为等价的几个子问题，对子问题进行递归分解和求解，然后将子问题的解合成为所求的解。 由此，可以得到一种最简单的凸包分治算法：将点集依照某种划分方法分为N部分，对每个部分求子凸包，最后将几个子凸包合成一个更大的凸包。 由此就可得到凸包问题的分治算法。 Step1：把S中的点按x坐标进行排序。 Step2：划分成两个子集S1，S2. Step3：P1=CH(S1)和P2=CH(S2). Step：合并P1，P2得到解集P. 蛮力法解决凸包问题核心代码 分治法解决凸包问题核心代码如下： 如图所示，分治法实现后的运行程序如下 做一个6个点的测试 最终求出3个顶点（-5，-5）（9,9）（-1，1）为正确答案 将程序改成随机产生点，只需输入点的个数。输入30个点。 最终得到凸包的表边与点。 数据处理分析： 关于蛮力法求凸包问题 选择不同的两个点有种选择，对这不同的两个点都要对其他的n-2个点求出a*x+b*y-c的值，即时间效率属于O(n3)， 输入不同的n观察输出结果的时间，并填入如下表中： n 100 150 200 250 300 350 400 450 500 Time(s) 0.281 0.920 2.247 4.399 7.504 12.028 17.847 25.132 34.399 n 550 600 650 700 750 800 850 900 950 Time(s) 47.565 60.950 76.425 93.928 115.41 144.00 169.63 203.81 236.65 根据上表通过Matlab描点画图