基于道路网络知识的启发式层次路径寻找算法.pdfVIP

第 卷 第 期 武 汉 大 学 学 报 信 息 科 学 版 ! # ! )=!?)# 年 月 $%% # ’()*+,-./+01203)4*+,-)05.-(0.()3678+090-:(4/-,; @A4$%% 文章编号 文献标志码 CBDD%$$%%%%#B%!%B%# @ 基于道路网络知识的启发式层次路径寻找算法 翁 敏$ 毋河海$ 杜清运$ 李林燕$ 武汉大学资源与环境科学学院 武汉市珞喻路 号 $ $E #!%%CE% 武汉大学教育部地理信息系统重点实验室 武汉市珞喻路 号 $$ $E #!%%CE% 摘 要基于道路网络的知识探讨了定义一个层次拓扑来帮助路径寻找及如何确定层次之间转换的入!出结 点并结合启发式技术来提高路径计算性能的路径寻找算法#实验表明该方法不仅可以减少计算所需要的 时间和空间也会产生一个符合人类思维特点的解# 关键词层次路径寻找’道路网络’启发式技术 中图法分类号 J$%D 在大量的最短路径算法中最具代表性的是 增多高层次是低层次的子集上下相邻的层次具 基于贪心策略的 算法和基于启发式有哪些信誉好的足球投注网站 有公共结点 这些结点是层次转换的关键点 这 F-gU/,4+ # 策略的 . 算 法 虽 然 它 们 都 能 保 证 获 得 最 优 样 在道路网络的最短路径算法中应用层次思想 @ # 解但实践表明随着网络规模的变大其计算时 可以将路径选择分层次地局限在道路网络一定的 间会变得不可接受(!)所 以需 要 修 改 已 有 的 策 子网络中而不是在整个网络中来有哪些信誉好的足球投注网站最佳解# 略或者探 索 一 种 新 的 策 略 来 提 高 已 有 算 法 的 性 层次算法思想 !! 能 对于在道路网络中的路径寻找来说 一个可 算法等非层次算法是在一个单一层 # F-gU/,4+ 取的办法就是使用道路网络的知识定义一个层次 次上来确定最短路径的而层次算法是在非层次 拓扑来帮助路径寻找#对于道路网络的层次化 算法的基础上通过一系列如何处理分层结构的 文献 分