两个守卫问题的最优扫描算法研究与实现

发布时间：2017-05-15 00:01

  本文关键词：两个守卫问题的最优扫描算法研究与实现，由笔耕文化传播整理发布。

【摘要】：Two-guard问题是计算几何学领域的热点问题,研究该问题,不仅涉及到求解多边形的可视性、Frechet距离、最短路径等理论问题的技术方法与研究成果,而且由于Two-guard问题也是很多实际应用问题的抽象模型使得该问题的研究具有很好的实际应用背景,因此,研究该问题,不仅具有理论意义,而且具有很大的实际应用价值。本文在论述画廊问题、Frechet距离问题、简单多边形及其可视性、min-sum与min-max量度标准及含义的基础上,对两个守卫可扫描简单多边形的几何结构极其特性,做了较为深入的研究,分析了可扫描简单多边形的直扫描和反扫描的扫描方式、扫描规则及其扫描方案的构成,详细论述了min-sum度量标准下的扫描规则与射线段图与min-max度量下的关键扫描线段与原子扫描图的构造过程与构造技术,运用图论的技术方法,将几何搜索问题转化为图的遍历问题,分别设计出了时间复杂度为O(n2)的min-sum度量标准下的最优搜索策略和min-max度量标准下的最优搜索策略。针对所设计的扫描策略,设计出了合理的数据结构并编程加以实现,给出了算法运行的可视化结果及其分析。实现结果表明,本文所提出的搜索策略是切实可行的解决方案。
【关键词】：两个守卫问题 min-sum度量 min-max度量 射线段图 原子扫描图
【学位授予单位】：大连海事大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP391.41;O18
【目录】：

• 摘要5-6
• ABSTRACT6-9
• 第1章 绪论9-16
• 1.1 研究背景及意义9-11
• 1.2 国内外研究现状概述11-14
• 1.3 主要研究内容14
• 1.4 论文的组织结构14-16
• 第2章 两个守卫问题的相关理论基础16-27
• 2.1 Two-guard问题的一般描述16-17
• 2.2 Two-guard问题的相关基础17-24
• 2.2.1 计算几何学概述17-18
• 2.2.2 基本概念定义18-23
• 2.2.3 扫描简单多边形23-24
• 2.3 Frechet距离问题24-25
• 2.4 Two-guard问题的最优度量标准25-27
• 2.4.1 min-sum度量标准25
• 2.4.2 min-max度量标准25-27
• 第3章 基于min-sum度量标准的最优搜索算法27-39
• 3.1 相关基础27
• 3.2 扫描操作分析27-30
• 3.2.1 直扫描分析27-29
• 3.2.2 反扫描分析29-30
• 3.3 Min-sum问题的算法构造30-39
• 3.3.1 射线段图的构造31
• 3.3.2 弧的权重31-32
• 3.3.3 算法流程32-36
• 3.3.4 算法伪代码描述36-39
• 第4章 基于min-max度量标准的最优搜索算法39-52
• 4.1 相关基础39-41
• 4.2 扫描操作分析41-44
• 4.2.1 直扫描分析41-42
• 4.2.2 反扫描分析42-44
• 4.2.3 一般扫描分析44
• 4.3 Min-max问题的算法构造44-52
• 4.3.1 原子扫描图的构造44-45
• 4.3.2 弧的权重45-46
• 4.3.3 算法流程46-50
• 4.3.4 算法伪代码描述50-52
• 第5章 算法实现及其结果分析52-62
• 5.1 基本数据结构52-55
• 5.2 测试数据的构造55-56
• 5.3 测试结果分析56-60
• 5.3.1 min-sum问题的测试结果分析56-58
• 5.3.2 min-max问题的测试结果分析58-60
• 5.4 时间复杂度分析60-62
• 5.4.1 Min-sum问题的算法复杂度分析60-61
• 5.4.2 Min-max问题的算法复杂度分析61-62
• 第6章 总结与展望62-64
• 6.1 论文工作总结62
• 6.2 进一步的研究工作62-64
• 参考文献64-68
• 攻读学位期间公开发表论文68-69
• 致谢69

【相似文献】

中国期刊全文数据库 前10条

1 胡国栋;李旭东;胡金喜;;一种判定简单多边形可视顶点的算法[J];甘肃科技;2007年10期

2 宋晓眉;程昌秀;周成虎;;简单多边形顶点凹凸性判断算法综述[J];国土资源遥感;2011年03期

3 胡国栋;李旭东;胡金喜;;简单多边形凸凹顶点的识别[J];甘肃科技;2007年08期

4 周文科;一种简单多边形凸包的快速算法及程序设计[J];广州大学学报(自然科学版);2003年06期

5 曲吉林,杨洪万;平面内任意一组简单多边形的可见性[J];山东师大学报(自然科学版);2000年02期

6 宋立明;闫浩文;王邦松;方爱玲;;两个简单多边形求交的算法[J];测绘与空间地理信息;2011年06期

7 崔先国;毛定山;;简单多边形间最大距离的求解算法[J];测绘科学;2008年06期

8 刘国栋;;整点多边形[J];惠阳师专学报(自然科学版);1991年03期

9 徐嘉;;二面体群作用下简单多边形的分类[J];计算机辅助设计与图形学学报;2012年07期

10 王相海;制定点是否包容于简单多边形中的一个三角剖分方法[J];松辽学刊(自然科学版);1995年02期

中国硕士学位论文全文数据库 前10条

1 刘建东;环形走廊中1-searcher搜索问题的算法研究[D];大连海事大学;2016年

2 刘元;两个守卫问题的最优扫描算法研究与实现[D];大连海事大学;2016年

3 马永卓;简单多边形构造方法研究[D];南昌航空大学;2013年

4 韩冰;简单多边形内LR可视问题的求解算法研究[D];大连海事大学;2011年

5 李玉娟;简单多边形中两个守卫的min-sum算法研究[D];大连海事大学;2011年

6 周志峰;简单多边形中两个守卫的max-min算法研究[D];大连海事大学;2012年

7 郭佳;可扫描简单多边形中两守卫间min-max距离求解研究[D];大连海事大学;2013年

8 汤立东;计算几何中LR可视化问题研究[D];大连海事大学;2010年

9 何雨静;Link-2可视多边形中三守卫问题的求解算法研究[D];大连海事大学;2014年

10 李丽;多边形搜索的几种策略研究[D];兰州理工大学;2011年

  本文关键词：两个守卫问题的最优扫描算法研究与实现，，由笔耕文化传播整理发布。

本文编号：366462