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

简单多边形中两个守卫的min-sum算法研究

作　者: 李玉娟
导　师: 蒋波
学　校: 大连海事大学
专　业: 计算机科学与技术
关键词: 计算几何 two-guard问题简单多边形 min-sum算法射线段图
分类号: O18
类　型: 硕士论文
年　份: 2011年
下　载: 16次
引　用: 1次
阅　读: 论文下载

内容摘要

两个守卫(two-guard)问题是计算几何中的经典问题之一,它的主要研究议题是：对于一个给定的简单多边形P,在它的边沿上有一个入口s和一个出口t,该多边形P被称作走廊。two-guard问题要求守卫从入口s出发,把目标(指非法入侵者)从出口t驱逐出去。这类守卫问题是由著名的画廊问题和巡视员路径问题激发而来,该类问题致力于在一个n边形P中用一组移动的守卫检测一个不可预测的、移动的目标。本文对two-guard问题中的子问题min-sum问题即简单多边形中两个守卫走过的距离的总和达到最小的问题进行了深入研究。由于一台机器人(或守卫)需要的能量和成本是它所移动距离的递增函数,所以研究min-sum问题具有十分重要的价值。首先,研究计算几何领域中的相关基础知识；其次,论述计算几何中的经典守卫问题,如画廊问题、最短巡视员路径问题以及two-guard问题；再次,研究two-guard问题中的两种基本扫描方式,即直扫描和反扫描,论述相关扫描机理,并分别给出在直扫描和反扫描情况下获得控制射点的几种情形,并构造射线段图,应用到min-sum问题的求解方法中；最后,针对min-sum问题,探索一个最优扫描方案,设计相应的数据结构并具体实现该算法,验证该算法的可行性和有效性,对实现结果做较为详细的分析。

全文目录

摘要  5-6
Abstract  6-9
第1章绪论  9-14
  1.1 研究背景与意义  9-10
  1.2 国内外的研究现状  10-12
  1.3 主要研究内容  12
  1.4 论文的组织结构  12-14
第2章 two-guard问题的相关理论基础  14-30
  2.1 计算几何及其经典计算几何问题  14-19
    2.1.1 计算几何的相关概念  14-15
    2.1.2 艺术画廊问题  15-17
    2.1.3 最短巡视员路径问题  17-19
  2.2 two-guard问题  19-20
  2.3 预备知识  20-30
    2.3.1 基本定义  20-26
    2.3.2 扫描简单多边形  26-30
第3章 min-sum问题的求解分析  30-44
  3.1 射线段之间的基本扫描  30-37
    3.1.1 直扫描  30-35
    3.1.2 反扫描  35-37
  3.2 min-sum问题  37-42
    3.2.1 射线段图的构造  37-39
    3.2.2 min-sum问题的求解算法  39-42
  3.3 一个下界  42-44
第4章求解min-sum问题的算法实现  44-55
  4.1 算法思路  44-47
  4.2 数据结构  47-49
  4.3 算法实现  49-55
第5章运行结果及其分析  55-61
  5.1 测试数据分析  55-57
  5.2 运行结果分析  57-61
第6章总结与展望  61-63
  6.1 论文工作总结  61-62
  6.2 进一步研究工作  62-63
参考文献  63-67
致谢  67-68
研究生履历  68-69

简单多边形中两个守卫的min-sum算法研究

内容摘要

全文目录

相似论文