当前位置:首页 >> 农林牧渔 >>

矢量地图下最短路径问题的研究


&"









!""# 年第 % 期 文章编号: (!""#) #""% $ &’%# "% $ ""&" $ "&am

p;

矢量地图下最短路径问题的研究
!"#"$%&’ () *’(%+"#+ ,$+’ ,%(-."/ (0 1"&+(% 2$3 夏 冰, 鲍远律 (中国科学技术大学自动化系, 安徽合肥 !&""!’)

!"# $%&’ , $#( )*+&,-.(()*+, -. /0+-12+3-4,5436, -. 783, /49 :)8;, -. <;342, =).)3 !&""!’, <;342)
摘 要: 本文讨论了矢量地图下的最短路径问题, 就矢量地图

输入为有向图 L O (I, , 源顶点 7" I, 这里 I 是 P) 顶点的集合, ( 0, P 是图 L 的边集合。边的权值函数 Q ( 0, 6) I 6) I #", " P。算法将顶点集合 I 划分为两类, O R$ S。集合 R 包含的顶点是那些已经确定的到离 源顶点的最近路径的顶点; 集合 S O I $ R。 S 又称为 打开 (T*)4) 集合, ( <C-?)) 集合。当一个 R 又称为关闭 顶点从集合 S 转移到集合 R, 我们就称它已经 “退休” 。 对于每一个顶点 I, 我们都保存当前最短路径的估计 值[ , 并为每一个顶点保存一个 “入边” [ 6] , 即在 E 6] )9 到当前顶点的最短路径中, 那个直接由邻点到当前顶 点的边。这样, 我们就可以根据这个信息, 从目标点反 向回溯重建这条最短的路径。如果有一条以上的最优 路径, 只有最近发现的路径被记录下来。 算法就是不停地展开具有 当 前 最 小 代 价 估 计 E [6] 的顶点 6" S。因为所有边的代价都为非负, 在某 一顶点展开后得到的最短路径, 不可能比当前顶点得 到的最短路径还短。因此, 我们已经确定了某一顶点 就可以将其 “退休” 至集合 R。然 6 的当前最短路径后, 后我们检验, 当前这条路径向相邻顶点展开出去, 是不 是会有比那些相邻顶点当前具有最短路径更短的路 径。如果有, 我们就更新最短路径的估计以及相应的 相邻顶点的入边。 @A? (最好优先) 算法 5E* 最好优先算法是一种启发式的搜索算法, 也就是 它将地图的一些知识带入了搜索标准中。它类似 (3F 但它总是先走向离目标点最近的顶点, 而 MN?+@2 算法, 不是逐渐走向离出发源点越来越远的顶点, 然后一步 步地逼近。 UG7 的关键就是 “面向问题” 寻找可以用来 做决策的标准。标准选择的好坏直接关系到搜寻的结 果, 甚至关系到是否有解。/! 算法就是建立在典型的 (3MN?+@2 算法和 UG7 算法之上的。 @A@ 4! 算法 它比 /! 算法是一种非常有效的路径寻优算法, (3MN?+@2 算法和 UG7 算法都要快。算法的整体框架是 一个图的遍历搜索算法, 但它不同于大多数图的搜索

下最短路径寻优算法的实现进行了深入的研究, 并应用于具 体的城市道路环境中进行检验, 取得了较好的结果。 关键词: 最短路径; 最短路径寻优算法; 矢量地图 /! 算法; 45*6!476: >4 +;3? *2*)@,A) 93?80?? +;) ?;-@+)?+ *2+; *@-BC)1 -. 6)8+-@ 12*,249 ?+09D +;) 2CE-@3+;1? -. ?;-@+)?+ *2+;FG34934E,249 28;3)6) E--9 @)?0C+ A;)4 0?34E 3+ 34 83+D @-29 12*?, 89:;<!=*: 7;-@+)?+ H2+;; 7;-@+)?+ H2+;FG34934E /CE-@3+;1?; /! /CE-@3+;1?; I)8+-@ J2* 中图分类号: :H&"# , K 文献标识码: /

>





(全球卫星定位系统) 和 L>7 ( 地理信息系统) LH7 技术在车辆导航和监控领域有着广泛的应用。在车辆 导航和监控系统软件中, 一个基本的辅助决策功能即 寻找两点间的最短路径。在复杂的城市道路网络中, 如何快速准确地找到出发点和目标点之间的最短路径, 取决于不同的路径寻优算法和矢量地图的数据结构。 本文主要研究基于矢量地图的最短路径问题和路 径寻优算法的实现。 ? 最短路径问题的定义 最短 路 径 问 题 ( H2+;.34934E -@ 7;-@+)?+ H2+; /CE-F 是一种计算机图形搜索算法, 即在出发点和目 @3+;1?) 标点之间找出总代价最低的路径。路径寻优算法一方 面要完成探索最低代价的路径, 另一方面要做到尽可 能快, 尽可能少占用内存, 即尽可能降低算法的时间复 杂度和空间复杂度。 @ 路径寻优算法 最短路径的寻优有很多不同的实现方法, 下面介 绍几种主要的路径寻优算法。 @A> (迪杰斯特拉) 算法 =BCD#+%$ 下面给出 (3MN?+@2 算法的简洁描述:
〔收稿日期〕 !""# $ "# $ !!

8MM9 年第 < 期









:9

算法, 采用了启发函数来估计地图上的任意点离目标 点的远近程度。通过这种启发式, 可以协助选择最好 的搜索方向。!! 算法希望通过将搜索方向偏向目标 点, 从而提高搜索的效率。最基本的思想是, 取代 "#$ 排序优先队列, 用[ %&’()* 算法采用的 [ + ,] - ,] .[ + ,] /0 [,] 作为新顶点插入队列的排序标准, 这里, [ 表示 + ,] 源点到当前顶点的实际代价, [ ,] 是当前顶点的启发 0 [ ,] 与从 , 到 ( 的实 值。理论上已经给出证明, 如果 0 际最小代价相比, 是一个低估值 ( 1234)4’(#5*(4) , 那么 !! 就可以产生像 "#%&’()* 算法的最优解。优先队列最 糟糕的情况就是和 "#%&’()* 一样的效率, 但是, 我们如 , 果提供一个良好的启发函数 [ 0 ,] !! 算法的平均效率 就会好得多了。 实现 !! 算法最重要的考虑因素就是内存的使用 和计算的时间, 直接说就是优先队列如何最大限度地 降低时间复杂度和空间复杂度。我们用 6 表示单元 ( 68 ) 。考虑空间复杂度, 数目, 整个算法的复杂度为 7 算法开始时, 如果每一点顶点需要保存 [ 和[ , + ,] 0 ,] 就要花费 7 (6) 。而且, 优先队列的每一个成员也需要 占据空间, 队列的成员最大数目为 6, 因此总的空间复 杂度有个上限 7 (6) 。实际应用中, 优先队列的大小要 比 6 小得多。 ! 矢量地图下算法的实现 我们定义的矢量地图包括地图矢量库和地图数据 库两部分, 在最短路径问题中, 我们主要关心的是地图 矢量库。地图矢量库中定义了矢量地图中几何结构 (点、 线、 面) 的位置形状信息。 下面主要介绍一下道路的有关定义, 因为这些涉 及后面的算法实现。 定义 9 定义 8 矢量边: 一些点的坐标的集合, 表征着一 大节点、 小节点、 节点: 大节点是矢量边 条连续的折线。 的端点; 小节点是指矢量边除端点之外的内部点; 大节 点和小节点统称节点。 定义 : 定义 ; 弧: 一条弧就是一条矢量边, 是若干个节 路: 路是若干条弧的集合。 点的集合。组成弧的节点是顺序排列的。 由图 9 看出, 弧是节点的集合, 路是弧的集合。可 见节点、 弧、 路之间的关系非常密切, 也正是这种各元 素的 “紧密” 联系为下一步基于地理空间信息的决策提 供了基础。
小节点: 8、 :、 <、 = 大节点: 9、 ;、 >、 ? 弧: [9, [ 、;, [ 、;, 8, :, ;] <, =, >] ?] 路: 以上的弧的任意组合均可能构成路 图 9 几种拓扑结构的定义

算法的基本思想是: 假设求从顶点 ,# 到 ,% 的最短 路径。首先建立两个链表 7@42A#’(、 分别存放 BCD’4A#’(, 待展开和已展开顶点。链表结点的形式描述如下:
E)#3+4F() . "E)#3+46D34 E)#3+46D34 . GHB7G" EHIJ6 24K(L)#3+4:E)#3+4F(); E)#3+4J",A*’(E)#3+4J":#2(4+4); A42+(0:#2(4+4); F)4’4*(:#2(4+4); H6"

其中, E)#3+4J" 为上次历经的桥索引; A*’(E)#3+4J" 为当 前所在的桥索引; A42+(0 为从起始桥到当前桥的当前 路径长度; F)4’4*( 为从起始桥到当前桥的当前路径的 上一段桥保存在 BCD’4A#’( 中的位置。 将起始桥以上述 E)#3+46D34 的结构压入 7@42A#’( 中, A42+(0 . M, F)4’4*( . N 9, A*’(E)#3+4J" . M, E)#3+4J" . 起始桥索引。展开 7@42A#’( 的第一个结点, 即将次结 点从 7@42A#’( 中取出, 压入 BCD’4A#’(, 返回压入位置, 然 后找出展开结点两端的邻接桥, 以 E)#3+46D34 结构按 使 7@42BCD’4 表 A42+(0 的大小顺序地压入 7@42BCD’4 表, 中结点 A42+(0 保持从小到大的顺序, 从而每次展开结 点的 A42+(0 总是当前最小的。当展开结点已在 7@42$ 比 较 两 者 的 A42+(0, 若待压入的结点 A#’( 中 存 在 时, 则取代已存在结点, 否则舍去。重复上述步 A42+(0 小, 骤, 直至 7@42A#’( 的第一个结点 E)#3+4J" . 终 止 桥 索 引。 以上是算法的基本思路, 下面我们就算法的收敛 性和正确性加以说明: ( *)7@42A#’( 中结点的 A42+(0 总保持增长的趋势, 而出发点到目标点的路径长度有穷, 随着 A42+(0 的不 断增长, 最终定有一条路径收敛于终止桥。 ( L)7@42A#’( 总是先展开 A42+(0 最小的结点, 而且

0)









)CC1 年第 6 期

即便展开的子结点已存在于 !"#$%&’( 中, 仍需进行一 次插入操作, 只有插入位置位于表头才能最终认定, 从 而保证了路径的最优 (图 ) 给出优化后算法的工作流 程图) 。 注意到最短路径的走向总是朝着终止桥的方向, 我们可以对算法加以优化: 将寻优的估价函数定为 * ( +) , 其中 ( 表示从起始桥到当前桥实 ,( - +) .( / +) - +) ( +) 取当前桥到终止桥的直线距离。 际走过的长度, / 这样, 在原来的 %#$-(/ 中添加预估长度作为 !"#$%&’( 排序的依据, 将很大程度上提高算法的时间和空间效 率。这种优势在稠密网络中体现得非常明显。 !

5 6

$ %

%&# (&#&) !&# (找出路径: "$&)

%&# (找出路径: #%)

下面我们用图 0 作一示例, 对于由顶点 2、 3、 4及 交叉点 1 7 8 构成的简单拓扑结构, 桥的权值已给出, 考虑从 2 点到 3、 4 点的最优路径选取过程中 !"#$%&’( 的顶点序列, 见表 1。 结果和讨论 笔者利用上述改进的 2" 算法结合矢量地图的结 构实现了最短路径的寻优 (如图 5, 图中较粗的路线即 为选出的最短路径) , 而且寻优的速度很快, 只要 ) 9 0 秒。我们可以看出, 对于这样一个比较稠密的道路网 络, 该算法还是很快捷和有效的。对于启发式的选择, 还可以根据不同的寻优策略做相应的修改。另外, 探 索更快速有效的数据存储结构, 这对算法的进一步完 善和提高也是有益的。

图 ) 寻优算法流程图

图 5 最短路径寻优结果

[参考文献]
[1] 郭耀煌, 等编著 : 筹学与工程系统分析 [ ;] : 中国建筑工业出版 社, 1<=8 : 1) : [)] 严蔚敏, 吴伟民, 等编著 : 数据结构 [ ;] : 清华大学出版社, 1<<) : 8: 图 0 简单拓扑结构 表1 结点展 开次数 1 ) 0 当前所 在顶点 ! " # "# #$ ($%$) !$% !"#$%&’( 中的顶点序列 2!3 "# #$ ($%$) !$% 2!4 [0] 孙德敏编著 : 工程最优化 [ ;] : 中国科学技术大学出版社, 1<<> : 11 : [5] 段凌宇 : 城市车辆联网监控系统的设计与实现 [ ?] : 1<<6 : 6 : [6] 姚振旺 : @AB 环境矢量电子地图生成校正平台的设计和实现 [ ?] : 1<<= : 6 :


相关文章:
AutoCAD平台下最短路径问题的研究与实现
AutoCAD 平台下最短路径问题的研究与实现 摘要:本文讲述了在 CAD 平台下,利用 ...一个研究的热点,它是资源分配、线路选择等问题解决的基础,尤其是在 诸如地图、...
地图中最短路径的搜索算法研究综述
地图最短路径的搜索算法研究中,每种算法的优劣的比较原则主要 遵循以下三点:[1] (1)算法的完全性:提出一个问题,该问题存在答案,该算法能够保证找到 相应的...
基于ArcGIS对矢量数据模型的最短路径分析
基于ArcGIS 对矢量数据模型的最短路径分析 摘要: 利用 ArcGIS 中网络分析模块对最短路径问题分情况进行了探讨,分别给出了在不 同情况下如何找到不同最短路径。...
最短路径毕业论文
最短路径算法的研究和应用越来越多,其中最短路径...更是线路选择问题解决的基础,特别是在地图、车辆调 ...本文的其它部分组织如下:第一章概述了交通咨询系统...
初中数学《最短路径问题》典型题型复习
新闻 网页 贴吧 知道 音乐 图片 视频 地图 百科文库 搜试试 3 帮助 全部 ...暂无评价|0人阅读|0次下载|举报文档初中数学《最短路径问题》典型题型复习_初二...
电子地图与最短路径算法结合精简版
电子地图与最短路径算法的结合 专业:信息与计算科学 学生姓名:xx 远 指导老师:宋政芳 [摘要] 最短路径问题在图论研究中是一个长盛不衰的经典问题,旨在寻找图中...
本科生毕业设计——电子地图与最短路径算法的结合
最短路径问题在图论研究中是一个长盛不衰的经典问题, 旨在寻找图中指定 两结点间的最短路径;而电子地图如今蓬勃发展,依托计算机成象等技术,直观 的为人们...
基于HTML5的矢量地图的研究-开题报告
基于HTML5的矢量地图的研究-开题报告_互联网_IT/计算机_专业资料。本科生毕业设计(论文)开题报告 学生姓名: 导师姓名、职称: 所属学院: 专业班级: 伍新华 计算机...
最短路径分析
文是在指导 教师的指导下独立进行研究所取得的成果...其次从 goolge 电子地图中得出各旅游景点间的最短...2.2.2Dijkstra 算法 关于最短路径问题,目前所公认...
基于城市道路网的最短路径分析解决方案.PDF
地图表示和网络拓扑结构的提取 G IS 中的矢量地图...以往的研究证明针对最短路径分析, 表示网络的数 . ...在大数据量的情况下, 这无疑是一个制约计算 是...
更多相关标签:
百度地图最短路径算法 | 地图最短路径算法 | 百度地图api 最短路径 | 地图最短路径 | 最短路径问题 | 最短路径问题ppt | 13.4最短路径问题 | 多段图的最短路径问题 |