学位论文 > 优秀研究生学位论文题录展示

可扫描简单多边形中两守卫间min-max距离求解研究

作　者: 郭佳
导　师: 蒋波
学　校: 大连海事大学
专　业: 计算机科学与技术
关键词: 两个守卫问题可扫描简单多边形 min-max算法原子扫描图
分类号: O18
类　型: 硕士论文
年　份: 2013年
下　载: 3次
引　用: 0次
阅　读: 论文下载

内容摘要

可扫描简单多边形中两守卫问题是一些实际应用问题的抽象模型,在扫描过程中两个守卫保持相互可见的约束条件下,研究最优扫描方案,不仅具有理论意义,而且具有重要的实际应用价值。一般而言,可扫描简单多边形中两守卫的扫描过程包括直扫描和反扫描两个过程,本文着重研究反扫描的情形。本文对可扫描简单多边形中两守卫间最大可视距离达到最小的问题进行了研究。首先,分析和研究了两个守卫问题中相关资料,对计算几何的基本概念与经典的艺术画廊问题、Frechet巨离问题,以及两个守卫问题等做了较为详细的论述,以此为基础,深入分析了可扫描简单多边形的特性,着重研究反扫描特性,分析构成原子反扫描的可能情形,以及最优扫描划分为若干个原子直扫描和原子反扫描的构造过程,给出了反扫描过程中构造关键扫描线段和原子反扫描的方法,结合原子直扫描的相关结论,设计出了原子扫描图,并用迪杰斯特拉算法求解min-max问题,得到了最优扫描方案。通过设计数据结构,实现了一个O(nlogn)时间复杂度的解决反扫描问题的算法和O(n2)时间复杂度的解决一般扫描问题的算法,并对运行结果做较为详细的分析,验证了算法的正确性。

全文目录

摘要  5-6
ABSTRACT  6-9
第1章绪论  9-14
  1.1 研究背景与意义  9-10
  1.2 国内外的研究现状  10-12
  1.3 主要研究内容  12
  1.4 论文的组织结构  12-14
第2章两个守卫问题的相关理论基础  14-25
  2.1 计算几何相关基础知识以及经典问题  14-17
    2.1.1 计算几何的相关基础知识  14-15
    2.1.2 艺术画廊问题  15-16
    2.1.3 Frechet距离问题  16-17
  2.2 两个守卫问题  17-18
  2.3 预备知识  18-25
    2.3.1 基本概念  18-24
    2.3.2 可扫描简单多边形  24-25
第3章 min-max问题的求解分析  25-35
  3.1 射线段之间的反扫描  25
  3.2 min-max扫描特性分析  25-35
    3.2.1 关键扫描线段  25-28
    3.2.2 原子扫描  28-32
    3.2.3 守卫扫描过程  32-33
    3.2.4 最优扫描方案  33-35
第4章 min-max问题的算法实现  35-53
  4.1 算法思路  35-37
  4.2 数据结构  37-42
  4.3 算法实现  42-49
  4.4 算法求解分析  49-53
    4.4.1 原子扫描图的构造  49-51
    4.4.2 反扫描  51-52
    4.4.3 一般扫描  52-53
第5章运行结果及其分析  53-60
  5.1 测试数据分析  53-57
  5.2 运行结果分析  57-60
第6章总结与展望  60-62
  6.1 论文工作总结  60
  6.2 进一步研究工作  60-62
参考文献  62-65
致谢  65-66
研究生履历  66

可扫描简单多边形中两守卫间min-max距离求解研究

内容摘要

全文目录

相似论文