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

简单多边形内Euclidean最短路径问题算法研究

作　者: 侯斌
导　师: 蒋波
学　校: 大连海事大学
专　业: 计算机科学与技术
关键词: 计算几何 Euclidean最短路径问题简单多边形分而治之
分类号: O224
类　型: 硕士论文
年　份: 2010年
下　载: 55次
引　用: 3次
阅　读: 论文下载

内容摘要

Euclidean最短路径问题是计算几何中一个比较典型的问题,它的主要研究议题是：对于给定的一系列欧氏空间中的障碍物与其中的任意两点,希望找出这两点之间的最短路径。本文对该问题中的一个子问题即简单多边形内Euclidean最短路径问题进行深入的研究。简单多边形内Euclidean最短路径问题的几何描述为：给定简单多边形P及其内两点s、t,求解该两点之间的最短路径。该问题的解决算法在很多问题的解决中被使用,如巡视员问题,机器人的运动规划等等。在求解简单多边形内Euclidean最短路径问题时,会遇到大量计算几何的基础问题,如判断两点是否重合、两条线段位置关系,所以本文首先对这些基础问题进行阐述与分析,并给出了相应的解决方法。随后,本文对Euclidean最短路径所具有的性质进行了深入的研究,然后对在该问题上前人已给出的Funnel算法与Rubberband算法进行了深入的研究,并详细分析了这两个算法的时间复杂度。本文的重点是在Rubberband算法基础上给出了改进算法,改进算法在原有的算法上引入了分而治之思想,这样可以把问题的规模缩小,从而使问题的求解速度加快。同时,本文给出了Rubberband算法与改进算法的实现,运用事后分析方法对两算法的运行时间结果曲线进行了拟合,并求解了拟合曲线的方程,从而验证了改进算法的优越性。

全文目录

摘要  5-6
Abstract  6-9
第1章绪论  9-12
  1.1 研究背景与意义  9-10
  1.2 研究内容  10
  1.3 论文的组织结构  10-12
第2章 Euclidean最短路径问题的基础问题  12-25
  2.1 计算几何基础  12-15
    2.1.1 计算几何  12-13
    2.1.2 准备知识  13-15
  2.2 典型算法  15-24
    2.2.1 基础算法  16-17
    2.2.2 三角剖分  17-22
    2.2.3 对偶图最短路径求解  22-24
  2.3 Euclidean最短路径问题  24-25
第3章 Euclidean最短路径问题求解算法  25-38
  3.1 Euclidean最短路径性质  25-27
  3.2 Euclidean最短路径求解算法  27-35
    3.2.1 Funnel算法  27-32
    3.2.2 Rubberband算法  32-35
  3.3 时间复杂度分析  35-38
第4章求解算法的改进  38-47
  4.1 改进算法思路  38-41
  4.2 数据结构  41-43
  4.3 算法实现  43-47
    4.3.1 Rubberband算法实现  43-44
    4.3.2 改进算法实现  44-47
第5章结果分析  47-50
  5.1 测试数据的生成  47-48
  5.2 运行时间结果分析  48-50
第6章总结与展望  50-52
  6.1 论文工作总结  50-51
  6.2 进一步研究工作  51-52
参考文献  52-55
致谢  55-56
研究生履历  56-57

简单多边形内Euclidean最短路径问题算法研究

内容摘要

全文目录

相似论文