从边界未知的危险区域中快速撤离的算法研究

发布时间：2017-08-21 08:17

  本文关键词：从边界未知的危险区域中快速撤离的算法研究

  更多相关文章： 计算几何 Online问题 撤离策略 竞争比

【摘要】：从边界未知的危险区域中快速撤离问题的研究,是从很多实际应用问题中抽象出来的一个理论课题,在一定的约定条件下,研究受灾人员如何从边界未知的危险区域中快速撤离的撤离策略,可为解决一些实际应用问题提供技术支撑。因此,本课题的研究,不仅具有重要的理论意义,而且还具有较高的实用价值。本文针对从边界未知的危险区域中快速撤离的策略进行研究,包括单源点问题和多源点问题。为此,首先论述了问题求解过程中所涉及的计算几何学的相关基础知识,如判断某点是否在线段上、构造平面点集的凸包等,并对竞争比、凸包,以及构造凸包的格雷厄姆方法等,作了较为详细的论述。在此基础上,论述了单源点问题及其相关撤离策略,并对等角策略的基本原理、执行过程以及竞争比等,做了较为详细的分析,提出了改进的单源点问题撤离策略。对比分析了多源点问题与单源点问题的问题特征,基于单源点问题的等角撤离策略,结合多源点问题的问题特征,进一步提出了多源点问题的等角撤离策略,并对撤离策略的竞争比做了较为详尽的理论分析,给出了竞争比不超过4(?)2的研究结果。最后,针对所设计的算法,构造测试数据并运行所实现的程序,验证了算法的可行性与有效性。实验结果表明,本文提出的针对单源点问题和多源点问题的撤离策略,能够有效地解决单源点问题和多源点问题,关于竞争比的实验结果与理论分析结果比较一致,且可保障所有受灾人员安全地撤离出危险区域。因此,本文所提出的解决单源点问题和多源点问题的算法是切实可行、有效的。
【关键词】：计算几何 Online问题 撤离策略 竞争比
【学位授予单位】：大连海事大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：X4;TP301.6
【目录】：

• 摘要5-6
• Abstract6-9
• 第1章 绪论9-15
• 1.1 研究背景与意义9-10
• 1.2 国内外研究现状10-12
• 1.3 研究内容12-13
• 1.4 论文的组织结构13-15
• 第2章 相关基础知识15-26
• 2.0 计算几何学概述15-16
• 2.1 基本定义16-18
• 2.2 经典问题及算法18-25
• 2.2.1 基础算法18-21
• 2.2.2 直线搜索问题及其求解算法21-22
• 2.2.3 计算平面点集凸包的算法22-25
• 2.3 本章小结25-26
• 第3章 单源点问题及其求解算法26-40
• 3.1 单源点问题的描述26-27
• 3.2 撤离策略27-39
• 3.2.1 等角撤离策略27-29
• 3.2.2 等角撤离策略竞争比分析29-37
• 3.2.3 等角撤离策略的改进及竞争比分析37-39
• 3.3 本章小结39-40
• 第4章 多源点问题及其求解算法40-54
• 4.1 多源点问题的描述40-41
• 4.2 单源点与多源点问题的对比分析41-42
• 4.3 撤离策略42-46
• 4.4 竞争比分析46-53
• 4.4.1 Online算法的成本D_(online)47-48
• 4.4.2 Offline算法的成本D_(offline)48-53
• 4.5 本章小结53-54
• 第5章 算法有效性验证54-59
• 5.1 单源点问题实验结果及其分析54-56
• 5.2 多源点问题实验结果及其分析56-59
• 第6章 总结与展望59-61
• 6.1 论文工作总结59-60
• 6.2 进一步研究工作60-61
• 参考文献61-64
• 致谢64-65
• 研究生履历65

【参考文献】

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

1 邓礼礼;求图中受限制的所有最短路径算法的分析与研究[D];华东师范大学;2009年

，

本文编号：711791