维普资讯 http://www.cqvip.com 基于ＩＴＳ的加速最短路径搜索算法研究 谢仕义徐兵 （湛江海洋大学信息学院，湛江５２４０００） Ｅ－ｍａｉｌ：ｓｈｉｙｉｘｉｅ＠ｔｏｍ．ｃｏｒｎ 摘 要 文章从路径搜索的基本原理入手，首先介绍了经典Ｄｉｊｋｓｔｒａ最短路径搜索算法，分析比较了基于堆结构和基数 堆结构的Ｄｉｊｋｓｔｒａ算＿击的搜索效率．从而提出了采用多层地图和分级搜索技术来实现对最短路径搜索空间的控制策略和 算击，结合湛江市区电子地图进行对比实验，谊算法有效地解决了最短路径搜索效率的问题。 关键词 最短路径 堆结构 分级搜索 文章编号１００２—８３３１一（２００６）１６—０２１２—０４ 文献标识码Ａ 中图分类号ＴＰ３０１；Ｕ１２１ ＴｌＩｅ Ｒｅｓｅａｒｃｈ ｏｆ Ｑｕｉｃｋｅｎ Ｕｐ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｎｄｉｎｇ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ ＩＴＳ Ｘｉｅ Ｓｈｉｙｉ Ｘｕ Ｂｉｎｇ （Ｉｎｆｏｒｍａｔｉｏｎ Ｃｏｌｌｅｇｅ，Ｚｈａｎｊｉａｎｇ Ｏｃｅａｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｚｈａｎｊｉａｎｇ ５２４０００） Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ａｒｔｉｃｌｅ ｓｔａｒｔｓ ｗｉｔｈ ｔｈｅ ｐａｔｈ ｆｉｎｄｉｎｇ ｐｒｉｎｃｉｐｌｅ，ｉｆｒｓｔ ｉｎｔｒｏｄｕｃｅｓ ｔｈｅ ｔｒａｄｉｔｉｏｎ Ｄｉｊｋｓｔｒａ ｓｈｏｒｔｅｓｔ ｐａｔｈ ｆｉｎｄｉｎｇ ａｌｇｏｒｉｔｈｍ，ｔｈｅｎ ｃｏｍｐａｓｓ ｔｈｅ Ｄｉｊｋｓｔｒａ ａｌｇｏｒｉｔｈｍ ｅｆｉｆｃｉｅｎｃｙ ｏｆ ｈｅａｐ ｓｔｒｕｃｔｕｒｅ ｂａｓｅｄ ｗｉｔｈ ｒａｄｉｃｅｓ ｈｅａｐ ｓｔｒｕｃｔｕｒｅ．Ｗｅ ｐｕｔ ｆｏｒｗａｒｄ ａ ｃｏｎｔｒｏｌ ｓｔｒａｔｅｇｙ ａｎｄ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｒｅａｌｉｚａｔｉｏｎ ｓｈｏｒｔｅｓｔ ｐａｔｈ ｆｉｎｄｉｎｇ ｓｐａｃｅ ｕｓｉｎｇ ｍｕｌｔｉｐｌａｙｅｒ ｍａｐ ａｎｄ ｈｉｅｒａｒｃｈｉｃａｌ ｆｉｎｄｉｎｇ ｔｅｃｈｎｏｌｏｇｙ，Ｆｉｎａｌｌｙ ｗｅ ｉｎｔｅｇｒａｔｅ Ｚｈａｎｊｉａｎｇ ｅｌｅｃｔｏｒｎｉｃ ｍａｐ ｗｉｔｈ ｉｍｉｔａｔｉｎｇ ｅｘｐｅｉｒｍｅｎｔ，ｔｈｅ ｒｅｓｕｌｔ ｉｓ ｔｈａｔ ｈｉｅｒａｒｃｈｉｃａｌ ｆｉｎｄｉｎｇ ａｌｇｏｒｉｔｈｍ ｑｕｉｃｋｅｎｓ ｕｐ ｔｈｅ ｓｈｏｒｔｅｓｔ ｐａｔｈ ｆｉｎｄｉｎｇ ａｌｇｏｒｉｔｈｍ ｇｒｅａｔｌｙ． Ｋｅｙｗｏｒｄｓ：ｓｈｏｒｔｅｓｔ ｐａｔｈ，ｈｅａｐ ｓｔｒｕｃｔｕｒｅ，ｈｉｅｒａｒｃｈｉｃａｌ ｆｉｎｄｉｎｇ １概述 如果把道路交通网中的道路起点、终点和交叉１３表示为节 寻找最短行车距离、最少旅行时间、最低通行收费等问题 点，把道路表示为连接节点的弧，把道路的长度、通行时间等属 是智能交通系统ＩＴＳ（Ｉｎｔｅｌｌｉｇｅｎｔ Ｔｒａｎｓｐｏｒｔａｔｉｏｎ Ｓｙｓｔｅｍ）的重要 性表示为道路的权，那么道路就被抽象为带权的有向图（ ， 研究内容［２１。它主要解决的问题是在特定道路网中寻找具有最 ｛Ｅ１）（如图１所示）。 小代价的最短路径问题。在图论中，迪杰斯特拉（Ｄｉｊｋｓｔｒａ）最短 路径算法是求解这一问题的基本方法．而且已有许多针对Ｉ）ｉ． ｉｋｓｔｒａ算法的具体实现Ｍ。但在车辆导航系统中通常不能直接 ２０ｌ２０１１２ 使用，因为在实际应用中记录路网信息的电子地图数据库往往 规模庞大，而负责路径搜索功能的导航计算机受车载环境和成 ● ’ ４４６６ 农 ０１１２ 本限制，处理能力和系统存储资源都十分有限。难以满足用户 实际使用的需要。所以本方案提出了结合电子地图的数据结 Ｏｌ１２ｏ０３６ 构，利用分级搜索技术来提高最短路径搜索速度的算法。 路● １ ００３６ ２最短路径搜索原理 囤１ 道路交通网的节点图 ２．１ 图与最短路径 在计算机科学中，图不是普通意义上的图形．而是表示定 义在顶点集上的二元关系，它是一种数据结构，它的形式化定 设 ， 为Ｖ中的顶点， ＝扣。 ， ｌ，…， 。）为Ｖ中 义为： 由” 到 ，的一条路径，ｃ（Ｖ，Ｗ）是弧（／３， ）的权值，则路径Ｐ的 Ｇ－（Ｖ，Ｒ） 权值总和可表示为： 其中：Ｖ＝ｌｘｌｘ∈ｄａｔａｏｂｊｅｃｔ｝（Ｖ是顶点的有穷非空集合） ｎ一１ ：｛ １（ 是顶点之间关系的集合） （ ）＝∑ｃ（ ， ） ｌ却 Ｒ＝｛（ ，ｙ）ｌＰ（ｘ，Ｙ）＾（ ，Ｙ∈ ））（Ｐ（ ，ｙ）表示顶点 与Ｙ之 最短路径就是指在带权有向图中。寻找从指定起点到终点 间存在路径） 的一条具有最小权值总和的路径。 基金项目：湛江市科技攻关计划项目（编号：Ｏ３ｏ９ｏ９６） 作者简介：谢仕义，男，副教授，硕士。目前主要研究方向为城市交通，算法设计。 ２１２ ２Ｏｏ６．１６计算机工程与应用 维普资讯 http://www.cqvip.com ２－２道路交通网的计算机存储与表示 在采用矢量编码方式的电子地图数据库中，道路以直线或 折线方式存储，并表示为一系列坐标点的有序集。为获得适用 于路径搜索的路网图，必须将包含交叉点的道路拆分成最基本 的路段，使其只在端点处与其他路段相交。拆分后的基本路段 对应于路网图中的弧，其端点就是图中的顶点。可双向行驶的 则 就是当前从 。出发的最短路径的终点。令： Ｓ＝ＳＵ｛ｖｊｌ （３）修改从 出发到集合 —Ｓ中任一顶点 的可达最短 路径长度，如果 ｄ ］＋Ａ【，Ｊ【 ］＜ｄ【 ］ 则修改ｄ １为： 路段要用两条端点相同、方向相反的弧表示。路网图的拓扑关 系可以用两个数组表示。其中分别存放在顶点相关的信息和与 弧相关的信息，并按顶点的编号次序排序以方便查找。与路网 图拓扑关系无关的其他道路属性信息用单独的数组表示，数组 间存在链接关系。以下是一个简单路网（如图２所示）。其计算 机存储结构及链接关系如表１所列（ａ）、（ｂ）、（ｃ）所示。由于最 短路径算法仅涉及从顶点出发的弧．因此与顶点相关弧的数量 只考虑以顶点为起点的弧；与顶点相关的弧的索引则与以顶点 为起点的序号最靠前的弧相对应。 袭ｌ道路交通网的计算机表示 （ａ）顶点信息表 （ｂ）弧信息表 弧索引号 道路索引 起点 终点 道路索引 路名 类型 长度／ｋｉｎ ２．３ Ｄｉｊｋｓｔｒａ最短路径搜索算法［４１ （１）利用邻接矩阵Ａ来表示带权有向图Ｇ，其元素Ａ嘲们 表示弧（”，， ，）上的权值；若弧（ ，， ，）不存在。则将Ａ 们设为 。ｏ。令Ｓ为已找到从 ．出发的最短路径的终点的集合，将其初 始化为空集。用辅助数组讲］的每一个分量ｄ【 表示从源站点 出发到终点 ．的可能达到的最短距离，取其初始值为： ｄ嘲 Ａ ， Ｅ Ｖ （２）选择 ．，使得： ｄ［ｊ］＝ｍｉｎ｛ｄ［ｉ］ｌｖ Ｅ Ｖ－Ｓ｝ ｄ［ｋｌ＝ｄＩｊｌ＋Ａ Ｉｊｌ［ｋ］ （４）重复操作（２）、（３）共ｎ一１次，由此求得按路径长度递增 次序排列的从 ．出发至图Ｇ中其余各顶点的最短路径序列。 以上算法将产生从源点出发至其余各顶点的最短路径。对 路径搜索来说，我们只需要从源点至指定终点的一条路径。为 此可将算法作简单的修改。设目标路径终点为 ．，则在操作（２） 中，如果发现ｖｊ－Ｉ） ，算法即终止，此时与ｄ［ｆ］对应的路径就是从 源点 。至终点 的最短路径。 对于上述有ｎ个站点的交通网络，算法的时间复杂度为 Ｏ（ｎ‘）。所以可以看出平方阶的算法效率是比较低的，特别是对 于网络节点数比较大时的算法效率就更低了。 ３基于堆结构的快速Ｄｉｊｋｓｔｒａ算法 为了改变传统的Ｄｉｊｋｓｔｒａ算法，而获得高效率的改良Ｄｉｊｋ－ ｓｔｒａ算法 。设 为 中的顶点， 为 中可由 到达的顶点， 则求解由 。至 ．的基于堆数据结构的最短路径算法实现过程 如下： （１）将 中的顶点划分为三类：已标记点、未标记点和已 扫描点；将 ．初始化为已标记点，其他顶点设为未标记点。为每 个顶点 ． ∈Ｖ建立一个对应数据项的属性值权值ｄ和后向顶 点指针Ｐ。分别初始化为： ｆ０， ｄ（ｖ）＝｛Ｐ（ ）＝｛｝ Ｉ。。， ≠ （２）扫描所有已标记点，从中选择一个具有最小权值的顶 点 并设为已扫描点；基于堆数据结构的扫描过程为： ①在堆ｈ中找到具有最小属性值的数据项，将其删除并作 为操作结果返回。并将其设为已扫描点．此操作定义为ｄｅｌｅｔｅ （ｒａｉｎ（ｈ））； ②检查弧（ 。Ｗ）： 若ｄ（ｗ）－￣，则令ｄ（ｗ）＝ｄ（ｖ）．４－ａ（ｖ，Ｗ）。则在堆ｈ中插入 一个新数据项Ｗ，将未标记点设置为已标记点，操作为ｉｎｓｅｔｒ （ｈ，Ｗ）；其中ａ（ｖ，Ｗ）是弧（ ，Ｗ）的权值。 若ｄ（ ）＜∞且ｄ（ｗ）＞ｄ（ｖ）＋ｎ（ 。 ），则将堆ｈ中的数据 项Ｗ的属性值用一个更小的数ｄ（ｖ）＋ｎ（ 。Ｗ）代替，此操作定义 为ｄｅｃｒｅａｓｅ（ｈ。Ｗ。ｄ（ｖ））＋ｎ（ 。Ｗ））； （３）重复进行扫描操作。若终点 ．被设为已扫描点，则搜索 结束。由 ．开始遍历各后向顶点指针Ｐ直至起点 。即可获得 最短路径解。 ＝扣０ ， ”， ＝ ｝，其中Ｐ（ｖ ）＝ ｝，ｉ＝０，１，…。ｎ一１。 起点 到终点 ．之间共包含ｎ一１个顶点。 上述Ｄｉｊｋｓｔｒａ算法的效率等于弧操作的时间复杂度为 Ｏ（ｍ）与顶点操作的时间复杂度Ｏ（ｖ）之和。其中。顶点操作的 时间复杂度Ｏ（ｖ）＝０（ｉｎｓｅｒｔ）＋Ｏ（ｄｅｃｒｅａｓｅ）＋Ｏ（ｄｅｌｅｔｅ）。而ｉｎｓｅｒｔ 计算机工程与应用２００６．１６ ２１３ 维普资讯 http://www.cqvip.com 操作的最大执行次数是／７，，ｄｅｃｒｅａｓｅ操作的最大执行次数是 ｍ一（ｎ—１），所以，执行ｉｎｓｅｒｔ和ｄｅｃｒｅａｓｅ操作的时间复杂度均 为Ｄ（１）。ｄｅｌｅｔｅ操作需要找到堆中具有最小属性值的数据项， 涉及堆中所有元素的比较操作。其执行时间的复杂度为Ｏ（ｎ）。 如果采用斐波纳契堆实现优先队列。可将ｄｅｌｅｔｅ操作的执行时 间减小到Ｄ（１ｏｇｎ），所以整个算法的执行时间复杂度减小为 Ｏ（ｍ＋ｎｌｏｇｎ）。 ４基于基数堆结构的Ｄｉｊｋｓｔｒａ算法 若弧权值ａ（ｖ， ）只取整数且具有上界Ａ，则采用基数堆 结构存放已标记顶点能够缩减Ｄｉｊｋｓｔｒａ算法的时间复杂度。但 顶点权值ｄ（ｖ）必须满足如下性质： （１）对任意的顶点 ，若ｄ（ｖ）＜∞，则有：ｄ（ｖ）∈【０，…， 】。 （２）对任意已标记顶点 ≠ ，有：ｄ０）∈［ｄ ），…，ｄ ）十Ａ】。 其中 是在最近一次扫描操作中产生的已扫描点。 基数堆是Ｂ－－－ｌｏｇ２（ ＋１）＋２个带序号桶结构的集合，每个桶 存放权值在特定范围内的已标记顶点。对于序号为ｉ的桶，它 的关联范围为： ｓｉｚｅ（１）＝１ ８ｉｚｅ（ｆ） ２ ２≤ｆ≤曰一１ ｓｉｚｅ（Ｂ）＝ｎＡ＋１ 为每个桶指定一个权值上界ｕ。则序号为ｉ的桶内所存放 的顶点权值范围可表示为： ｒａｎｇｅ（ｉ）＝［ｕ（ｉ－１），…，ｍａｘ｛ｕ（ｉ－１）＋ｓｉｚｅ（／），ｕ（ｚ）Ｊ】 取ｕ的初始值为： （Ｏ）＝Ｏ ｕ（ ）；２ 一１ １≤ ≤曰一１ ｕ（Ｂ）＝ｎＡ＋１ 则堆结构中的顶点权值范围为［０，…， ＋１１。在Ｄｉｊｋｓｔｒａ算 法执行过程中，每个桶结构的关联范围保持不变，上界ｕ则随 扫描过程的进行作动态调整。此时堆结构的三种操作执行过程 如下： （１）ｉｎｓｅｒｔ（ｈ，∞）：从ｉ＝Ｂ一１开始按递减顺序检查桶ｕ（ｉ），若 ｕ（ｆ）＜ｄ（ ），则将 存入桶ｉ＋１； （２）ｄｅｌｅｔｅ（ｍｉｎ（ｈ））：从ｉ＝１开始按递增顺序检测桶ｉ，并将 第一个非空桶内的最小权值顶点作为操作结果返回； （３）ｄｅｃｒｅａｓｅ（ｈ， ，ｖａｌｕｅ）：令ｄ（ｘ）＝ｖａｌｕｅ，设 在桶』内，若 ｄ（ｘ）∈ｒａｎｇｅ（ｊ），操作结柬；否则从桶＿『中删除 并由ｉ＝ｊ一１开 始重新执行ｉｎｓｅｒｔ（ｈ， ）。 在执行ｄｅｌｅｔｅ操作后，还要修改桶结构的权值上界并重新 调整已标记顶点在整个堆结构内的分布。设ｖ＝ｄｅｌｅｔｅ（ｍｉｎ（ｈ））， 首先对ｕ作如下修改： ｕ（Ｏ）＝ｄ（口）一１，ｕ（１）－－ｄ（ｖ） ｕ（ｉ）＝ｍｉｎｌｕ（ｉ一１）＋ｓｉｚｅ（ｆ），ｕＵ）】２≤ 一１ 式中Ｊ是 所在桶的序号，然后将桶． 中的所有已标记顶 点全部移出并重新执行ｉｎｓｅｒｔ操作。 采用基数堆结构实现Ｄｉｊｋｓｔｒａ算法后，可以计算出时间复 杂度为Ｏ（ｍ＋ｎｌｏｇ２Ａ），即在采用基数堆结构后，Ｄｉｊｋｓｔｒａ算法的 时间复杂度由对数阶减少到线性阶。 ５基于多层地图的分级搜索算法 从Ｄｉｊｋｓｔｒａ算法的时问复杂度分析可以看出，路网图的规 ２１４ ２００６．１６计算机工程与应用 模是决定最短路径搜索时间的关键因素［６１。如果用合理的方法 减少搜索所涉及的顶点和弧的数量，将会使路径搜索效率提 高。所以本算法的基本思想就是采用多层地图和分级搜索技术 来实现对最短路径搜索空间的控制，达到减小算法时间复杂度 的目的。 首先在交通道路网的电子地图上进行全局搜索以获得大 致的目标路径，然后利用该路径将电子地图图层分解为一系列 局部搜索空间进行搜索（如图３），并将获得的局部最短路径合 并在一起得到最终的目标路径。采用分级搜索方法时，原来的 搜索空间就被一系列小的局部搜索空间所替代。当路网图规模 比较大时，这样处理会显著缩小搜索空间。 圈３分级搜索空间示意圈 在多层地图上实现分级搜索的算法为： （１）将图ｅ中的主干公路用一个专门的图层舭表示，并 将起点ｓ与终点ｔ加入到图层ＭＬ中。 （２）在舭中搜索从ｓ到ｔ的最短路径 ＪｌｌｉＩｌ＝（ Ｉ ，ｅｌ， ２， ｅ：，…， 。 ｍ＋ｌ＝ｆ），其中 ；是路径所经过的顶点，ｅｉ是连接相邻 顶点的弧。 （３）将ｓ到ｔ的路径划分成Ｐ段，设第ｉ段的端点分别为 “和 ｃｆ，且／）ｓｌ ， ＝ｔ， ，ｉ＞１；设Ｌ为预定的长度划分界 限； ．，则可按如下条件选取： Ｉ—Ｉ ∑ ≤，Ｊ， ≤ｐ Ｊ司 Ｚｅ￣＞Ｌ，ｉ＜ｐ （４）设Ｇ中顶点 的坐标为 （ ，ｙ），在搜索 时先进行 顶点过滤： ≤ （ ）≤ ｍ蚪， ≤ （Ｙ）≤）， 嘲 式中的过滤参数为： Ｘｒａｉｎ＝ｍｉｎ（ｖ （１，７），…，口 （ ）） 恤＝ｍａｘ（ ，（ ），…， “（ ））－￣ｔｔｔ ｉ＝ｍｉｎ（ｖ （Ｙ），…，口 （Ｙ））－－ｇＬ ）， ＝ｍａｘ（ｖ （Ｙ），…，ｔ， （Ｙ））＋／．ｔｔ 其中参数 是保证顶点过滤后仍有最短路径存在的扩展 因子。 （５）从 １开始在Ｇ中搜索由 ．至 的最短路径Ｒ ， 并将获得的局部最短路径合并生成全局目标路径Ｒ ＝（Ｒ 。， …，Ｒ ｌⅡｉ ）ｏ 维普资讯 http://www.cqvip.com 另外采用分级搜索后．对于道路交通发生变化的情况处理 十分有利。如某条公路被临时关闭，常规的搜索算法必须要在 权随更新后的路网图中重新搜索从源点到终点的最短路径，而 在采用分级搜索后，我们只需更新包含变化路段的一段局部最 短路径．由于这一过程只会涉及一个小的局部搜索空间，因此 重新搜索最短路径的速度会大大加快。 ６仿真实验和结果分析 ６．１ 图层编码与属性数据库结构设计 为了提高程序设计实现的效率和数据的安全性，除了在程 序直接要用到的数据存放在图层的数据表中外，其它的属性数 据都存储于服务器端的ＲＤＢＭＳ数据库中，系统采用ＯＤＢＣ作 为数据库管理的开发方法。图层编码与属性数据库结构采用国 家标准设计，这里主要给出了道路数据库、公交线路数据库、公 交站点数据库的结构设计。 （１１道路．ｔａｂ ＩＤ字段编码ｓｅｇｍｅｎｔＩＤ ｓｔａｒｔＩＤ ｅｎｄｌＤ ｒ０ａｄＮａＴｎｅ ｄｅｐｉｃｔｉｏｎ 字段名 路段编码路段起点编码路段终点编码道路名称备注描述 ｓｅｇｍｅｎｔＩＤ字段编码为 四位数字０ＯＯｌ一９９９９表示各道路一端点的编号 四位数字０００１—９９９９表示各道路另一端的编号 （２）公交线路．ｔａｂ ＩＤ字段编码ｒｏｕｔｅｌＤ ｂｕｓＲｏｕｔｅ ｓｔａｔｉｏｎｓ ｉｓＤｏｕｂｌｅ ｌｅｎｇｔｈ ｄｅｐｉｃｔｉｏｎ 字段名字段名 内部表示公交路线号经过的萎 公交 号 站点是否相同线路长罢 篙 长度备注描述 ｒｏｕｔｅＩＤ字段编码为： ｋ－－ｋ－ｋ ｋ－－ｋ Ｔ］二两位数００—９９表示每一公交线路在两个站点之间的线段编码 Ｌ一——二位数００１—９９９表示公交线路的编号 （３）公交站点．ｔａｂ ｓｔａｔｉｏｎｌＤ字段编码为 ０ｏ１—９９９表示公交站点编号 公变站点所在辖区编号 １表示市内公交．２表示市郊公交 ６．２实验结果 为验证快速路径搜索算法的有效性，我们利用Ｗｉｎｄｏｗｓ ２ＯＯ０ Ｓｅｒｖｅｒ操作系统．Ｍａｐｉｎｆｏ６．０、ＭａｐＸｔｒｅｍｅ ２０００软件平台， ｖｉｓｕａｌ Ｃ十＋开发工具编制程序进行了仿真试验。程序分别按经 典Ｄｉｊｋｓｔｒａ算法、基于基数堆结构的Ｄｉｊｋｓｔｒａ算法、分级搜索算 法３种方法搜索最短路径。搜索地图采用湛江市区交通图，其 中共包含了３ ０１４条弧和２ ０７１个顶点。为应用基数堆结构，我 们将弧长度以５０ｍ为基本单位分成了５１４个级别。在分级搜 索中，划分长度 取为ｌｋｍ，扩展因子 取为Ｏ．１。仿真程序在 Ｐｅｎｔｉｕｍ ＩＩｌ、主存１２８Ｍ、硬盘１０Ｇ计算机上进行了长距离的最 短路径搜索，结果如表２所示。其中的搜索顶点总数是指搜索 结束后的已标记顶点和已扫描顶点总ｌ敏之和；由此可以看出． 在引入了多层地图和分级搜索后．路径搜索算法得到了很好的 改进，使运算速度大大加快。图４是采用分级搜索算法所获得 的最短路径图。 裹２ ３种最短路径搜索算法性能比较 试验～ ！！ｒａ兰 一 笙塑塑室 堕—— 墼…一 次数顶点总数运行时间／ｓ顶点总数运行时问／８顶点总数运行时间／ｓ 图４ 采用分级搜索算法所获得的最短路径围 ７结束语 在车辆出行和导航中由于实时性要求较高，因此一旦出现 由于路况变化或其他原因使车辆未能按预定导航路线行驶，车 载计算机系统就必须重新计算最短路径问题，这时一方面要求 算法的运行速度一定要快，另一方面由于电子地图的规模十分 庞大，使得执行最短路径搜索算法所需要的时间长，存储空 增大，加上实际车载计算机环境的限制。所以采用多层地 啐【ｊ 分级搜索技术控制搜索路网的规模，可以大大提高算法的放 率，非常值得借鉴和推广。（收稿日期：２００５年９月） 参考文献 １．杨晓光。周雪梅，藏华．基于ＩＴＳ环境的公共汽车交通换乘时间最短调 度问题研究『ＪＪ．系统工程，２００３；２ｌ（２）：５６—５９ ２．Ｓｈｉｙｉ Ｘｉｅ，Ｓｈｅｎｇ Ｇａｏ，Ｂｉｎｇ Ｘｕ．Ｓｔｕｄｙ ｏｆ ａｎ Ｏｐｔｉｍｕｍ Ｓｃｈｅｄｕｌｉｎｇ ＡＩ－ ｇｏｒｉｔｈｍ Ａｂｏｕｔ Ｂｕｓｅｓ ｉｎ Ｃｉｔｙ Ｉｎｔｅｌｌｉｇｅｎｔ Ｔｒａｎｓｐｏｒｔ Ｓｙｓｔｅｍｓ［Ｃ］．Ｉｎ：Ｐｒｏ－ ｃｅｅｄｉｎｇｓ ｏｆ ＩＣＭＬＣ２００４，Ｘｉａｎ，２００４一ｌ１：２７９５～２７９９ ３．米涅卡（美）．网络和罔的最优化算法【Ｍ】．中国铁道出版社，１９８４－０２ ４．于东凯，刘玉树．基于平面罔的最短路径算法的研究【Ｍ】．北京理 大 学学报。２００１；２ｌ（１）：３ｌ～３４ ５．Ｔａｎｇ Ｗｅｎｗｕ。Ｓｈｉ Ｘｉａｏｄｏｎｇ，Ｚｈｕ ｄａｋｕｉ．Ｔｈｅ Ｃａｌｃｕｌａｔｉｏｎ ｏｆ Ｔｈｅ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｕｓｉｎｇ Ｍｏｄｉｆｉｅｄ Ｄｉｊｋｓｔｒａ Ａｌｇｏｒｉｔｈｍ Ｉｎ ＧＩＳ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｉｍａｇｅ ａｎｄ Ｇｒａｐｈｉｃｓ，２０００；５（Ａ）（１２）：１０１９－１０２３ ６．Ｈｕａｎｇ Ｙ Ｈ．Ｒｕｎｄｅｎｓｔｅｉｎｅｒ Ｅ Ａ，Ｊｉｎｇ Ｎ．Ｅｖａｌｕａｔｉｏｎ ｏｆ Ｈｉｅｒａｒｃｈｉｃａｌ Ｐａｔｈ Ｆｉｎｄｉｎｇ Ｔｅｃｈｎｏｌｏｇｉｅｓ ｆｏｒ ＩＴＳ Ｒｏｕｔｅ Ｇｕｉｄａｎｃｅ［Ｃ］．Ｉｎ：Ｐｒｏｃｅｅｄｉｎｇｓ ｆｏ １９９６ Ａｎｎｕａｌ Ｍｅｅｔｉｎｇ ｏｆ ＩＴＳ，Ａｍｅｒｉｃａｎ。１９９６：３４０￣３５０ ７．Ｒａｖｉｎｄｒａ Ｋ Ａ，Ｋｕｒｔ Ｍ，Ｊａｍｅｓ Ｂ ０ ｅｔ ａ１．Ｆａｓｔｅｒ Ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｐｒｏｂｌｅｍ［Ｊ］Ｊｏｕｒｎａｌ ｏｆ Ａｓｓｏｃｉａｔｉｏｎ ｆｏｒ Ｃｏｍｐｕｔｉｎｇ Ｍａｃｈｉｎｅｒｙ． １９９０：２１３￣２２３ ８．Ｚｈａｎ Ｆ Ｂ．Ｔｈｒｅｅ Ｆａｓｔｅｓｔ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ａｌｇｏｒｉｔｈｍｓ ｏｎ Ｒｅａｌ Ｒｏａｄ Ｎｅｔ－ ｗｏｒｋｓ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｇｅｏｇｒａｐｈｉｃ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｄｅｃｉｓｉｏｎ Ａｎａｌｙｓｉｓ。 １９９７；ｌ６（１）：６９－８２ 计算机工程与应用２００６．１６ ２１５