• / 21
  • 下载费用:10 金币  

障碍最短路径算法研究 - 邓俊辉 - Junhui Deng.pdf

关 键 词:
障碍最短路径算法研究 - 邓俊辉 - Junhui Deng.pdf
资源描述:
障碍最短路径算法研究 小组成员 陈 康 ( 2012311316)交叉研 2 班 冯立新 ( 2012210914)计研 123 班 应用背景 障碍最短路径问题是图论中最短路径问题的一个自然的推广,考虑的是在有障碍情况下的最短路径问题。如工厂中机器人在工作间内如何规划运动的线路、GIS 系统里地图上两点之间的最短距离、游戏设计中自动寻路、网络路由策略选择、电路板中线路设计等诸多问题都可归结为有障碍下的最短路径问题。解决这个问题可以带来非常明显经济效益和社会效益。同时这个问题是计算几何领域的古老而经典问题之一,而且与它相关的子问题,如单起始点多终止点障碍最短路径、最短链接、可见图等问题也受到了持续的关注与研究。 问题定义 给定在平面中指定起始点 pStart、 终止点 pEnd 和 N 个互不相交的多边形障碍物 P1, P2, …, Pn,计算 起始点 pStart 和终止点 pEnd 之间的最短路径 。 相关工作 障碍最短路径问题 在计算 几何领域曾经得到了广泛的研究,但是由于一直缺乏简单高效的算法, 目前 这个方向 也 逐渐冷却 。 在 实际应用 中 ,人们 往往 更 愿意使用简单高效的非精确算法( 如 A*等 ) ,但我们 这里 只 讨论精确算法 。 目前求解 障碍最短路径问题有两种 基本 思路 : 一种是 直接 构造 全局可见性图,把问题转化成无障碍图的最短路径求解问题; 另外一种 是 通过区域分割,不断排除不可能区域 , 最终构造出 最短路径地图 。构造 全局 可见性图原理 比较简单,但由于需要 为大量不可能经过的点构造可见性图 , 所以计算代价比较高 。最短路径地图的原理 比较复杂,但算法效率显著 提高 。当前 理论 上 的 最优算法 就是 基于 这种思路 ,利用波浪线的方法对几何区域进行快速分割实现 的 。 通过 构造 可见 性图 求解 最短路径问题 直观 上很容易理解 , 一旦构造出全 局 的可见性图 , 我们 就从 原问题中抽象出了一幅完全图 , 每一条 边 都代表了一个可行的路径 , 接下来要做的就是使用 图论 中 经典 的 Dijkstra 算法求解 最短路径。事实上 构造 可见性图 本身 就 是一个相当基本的问题 , 包括 Art Gallery Problem 在内的一系列经典问题都依赖于该问题,所以单纯对可见性图构造算法有着大量的研究 [3]。 构造 可见性图的 一 种经 典 的 方 法 是 旋 转 扫描 线 算法 [1], 其 复杂 度 为O(n2logn), 其中 n 为障碍 物 顶点 的 数目。 我们 实现的也是这个算法,具体内容我们会在下文中仔细分析。 Ghosh 和 Mount 对该算法进行了改进 [2],使得复杂度降至 O(nlogn+E)( n 是顶点数, E 是可见性图的边数)。 它的思路是以平面扫描三角剖分形式给出了有障碍情况下可见图的构建。主要的思想是 Funnel Sequence( FNL)漏斗的分割和合并。漏斗可以看作覆盖所有障碍的多边形边E 的两 个顶点,按照顺时针或者逆时针顺序的所有可见顶点的序列,相连顶点 形成的边是最靠近 E 的左或者右的线段。通过平面扫描的方式,新加入的多边形的边对应的新漏斗是从原多边凸内链上边的漏斗中分割得到。最后得到的就是要求的可见图。 同样在 三维空间中也存在可见性图,但 由于 2 维可见性图的概念并不能 简单地 直接推广到 3 维, 维数 升高带来 的 代数难度和组合难度 导致 三维空间的可见性图 复杂 度更高 。 Joseph [6]回顾了 3 维可见图的发展历程,指出了 3 维可见 图构造的 NP-hard 性质。 障碍最短路径 的另外一种 求解 思路是直接在几何域上进行运算。 Mitchell[4] 的算法考虑 了移动物体的尺寸,将整幅地图划分成大小相等的小区域 ,计算哪些小区域是可以通过的 , 最终 将每一个小区域抽象成一个节点,形成一个联通图,在此基础上同样应用图论最短路径算法 。算法 的主要代价在于决定哪些小区域是可以通过的, 该算法的时间复杂度 为 O(kn), k 为障碍的个数, n 为障碍多边形的边的个数。目前理论上的最优的算法 在此 基础上由 Hershberger 和 Suri 改进[5] 提出 , 时间复杂度 O(nlogn)。他们采用的是 continuous Dijkstra 方法 ,也就是 形象 的 波浪线传播方法对最短路径地图进行计算 ,算法 通过对平面采用四叉树划分加速波浪的事件传递,对非近邻的波浪则采取近似处理从而得到最优的构造算法。但与大多数理论最优算法类似,该算法在实现上过于复杂,实用性不高。 输入限定和 衰退 处理 计算 几何 的 很多算法 之所以 停留在理论 阶段 ,除了算法 本身比较复杂以外
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:障碍最短路径算法研究 - 邓俊辉 - Junhui Deng.pdf
链接地址:https://www.weizhuannet.com/p-9787630.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开