算法分析与复杂性理论实验报告凸包问题

1、深 圳 大 学 实 验 报 告 课程名称： 算法分析与复杂性理论 实验项目名称： 实验三 分治法求凸包问题 学院： 计算机与软件学院 专业： 软件工程 指导教师： 杨烜 报告人：文成 学号：2150230509 班级： 15级软工学术型 实验时间： 2015-10-22 实验报告提交时间： 2015-10-24 教务部制实验目的与要求：实验目的：（1） 掌握分治法思想。（2） 学会凸包问题求解方法。实验要求1. 在blackboard提交电子版实验报告，注意实验报告的书写，整体排版。2. 实验报告的实验步骤部分需详细给出算法思想与实现代码之间的关系解释，

2、不可直接粘贴代码（直接粘贴代码者视为该部分内容缺失）。3. 实验报告样式可从/guide.aspx 表格下载学生适用在校生管理实践教学实验：深圳大学学生实验报告）4. 源代码作为实验报告附件上传。5. 在实验课需要现场运行验证。实验内容：1. 对于平面上给定的N个点，确定这个点集的凸包，即，输入是平面上的N个点，输出是凸包轮廓。2. 要求随机生成N个点的平面坐标，应用蛮力法编程计算出点集凸包。3. 要求随机生成N个点的平面坐标，应用分治法编程计算出点集凸包。4. 分别对N=100,

3、1000,10000,100000，统计算法运行时间，比较理论效率与实测效率的差异，同时对蛮力法和分治法的算法效率进行分析和比较。注意需要在不同数据量之间增加测试点，例如10000到100000之间需要增加20000、30000。，以分析效率变化趋势。5. 利用Unity 3D输出算法中间结果，直至最后算法计算结果。同时增加help按钮，详细介绍算法原理。实验过程及内容：（实验代码已作为附件提交，名为“算法实验三.cpp”）凸包问题的描述与定义： 凸包的定义为：平面的一个子集S被称为是“凸”的，当且进当对于任意两点p,qS，线段都完全属于S。几何S的凸包CH(S)，就是包含S的最小凸

4、集，更准确地说，它是包含S的所有凸集的交。由此还可以推出凸包的很多性质，包括一条直线如果与凸包相交（不是相切）的话，最多交于两条边或者两个面。一组平面上的点，求一个包含所有点的最小凸边形，既是凸包问题。形象地说：在一平木板（平面）上钉若干钉子（点），将一橡皮筋套上去后，会把钉子圈起来，形成一个凸边形，即为该点集的凸包。关于用分治法求凸包问题的思路：分治法是一种很基础的算法。基本思路是将问题分解为等价的几个子问题，对子问题进行递归分解和求解，然后将子问题的解合成为所求的解。 由此，可以得到一种最简单的凸包分治算法：将点集依照某种划分方法分为N部分，对每个部分求子凸包，最后将几个子凸包合成一个更大

5、的凸包。由此就可得到凸包问题的分治算法。¹ 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个点。最终得到凸包的表边与点。数据处理分析：关于蛮力法求凸包问题选择不同的两个点有种选择，对这不同的两个点都要对其他

6、的n-2个点求出a*x+b*y-c的值，即时间效率属于O(n3)， 输入不同的n观察输出结果的时间，并填入如下表中：n100150200250300350400450500Time(s)0.2810.9202.2474.3997.50412.02817.84725.13234.399n550600650700750800850900950Time(s)47.56560.95076.42593.928115.41144.00169.63203.81236.65根据上表通过Matlab描点画图可得下图：关于分治法求凸包问题本人程序暂有些问题，当点数增大到1000，10000，后并没有做出来目前只能解决小规模的问题。未采集分治法的时间数据。实验结论：分治法的思想就是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题解合并得到原问题的解。 蛮力法求凸包问题随着规模的增大，效率会越来越低，而使用一种最简单的凸包分治算法效率更高：将点集依照某种划分方法分为N部分，对每个部分求子凸包，最后将几个子凸包合成一个更大的凸包。通过本次试验我对分治法有了更深的了解。利用分治法可以将问题简化，这有助于我们在实际中解决一些复杂性较大的问