两种改进的最优路径规划算法

D0I:10.13374/i.issn1001053x.2005.03.028 第27卷第3期 北京科技大学学报 Vol.27 No.3 2005年6月 Journal of University of Science and Technology Beijing Jun.2005 两种改进的最优路径规划算法 李擎”宋顶立)张双江》李哲引刘建光》王志良) 1)北京科技大学信息工程学院，北京1000832)河北理工大学，唐山063009 3)唐山市交通局货运科，唐山0630004)海湾科技集团，北京100102 摘要在对经典Dijkstra算法和A*算法分析的基础上.对它们分别进行了改进.在经典Dijkstra 算法中，针对当前不相连节点间路径长度为无穷大这一特点，首先对两个节点是否相连进行 判断：若发现两个节点并不相连时，则舍去相应计算，从而减小计算量，针对A*算法在实际 应用中搜索效率低的缺点，将经典A*算法搜索出的原始最优路径中的节点依次进行封堵后， 再按照经典A*算法搜索出相应的新最优路径，最后再将原始最优路径与这些新最优路径进 行对比，以便确定最终的最优路径.仿真研究表明：改进的Dijkstra算法可以减少大量的无关 节点计算，提高运算的效率：改进的A*算法则可以提高搜索到最优路径的成功率， 关键词路径规划；车辆导航；Dijkstra算法；A*算法 分类号TP18;TP273.23 路径规划是指在旅行前或旅行中为驾驶员 dw)=oo,并将h标号为0，t-.d为和w之间的 提供参考行驶路线的过程，是车辆定位与导航系 权值（距离） 统的基本功能之一.针对陆地车辆导航的不同要 (2)按照每个未标号的节点w计算d(w),dw)= 求，在路径规划中可采取多种优化标准，如最短 min{dw),dt十l(t,w)},l(t,w)表示点t到点w之间 距离、最少行驶时间或收费，但无论使用何种标 的权值（距离）.若试w)被修改了，说明在当前得到 准，路径规划最终都可以归结为在特定道路网络 的到w的最优路径上t和w相邻，用t.记录下 中搜索总代价最小的目标路径问题.当前比较流 来.在所有dw)中，选择一个最小的ds),即ds)= 行的方法有Dijkstra算法及其改进算法如邻接节 min{dw)},w未标号.将s标号为ds)h,表示节 点算法、最短路径快速算法、带评价函数的 点w到s的最优路径的长度为武s),且t.与3相邻. Dijkstra算法等等：A*算法及其改进算法如双向 (3)若终点v已标号，则停止.得到一条从 启发式搜索、动态管理优化A*算法阿、A*算法的 到v的最优路径，否则-5，转向(2)再计算. 局部改进算法等等：此外还有空间网络分层分 1.2 Dijkstra算法应用举例 解算法侧、遗传算法等，本文将主要讨论针对Di- 以具体实例说明Dijkstra算法的具体应用， jkstra和A*算法的改进算法. 例1.利用Dijkstra算法求图1中节点A到其 它各节点的最优路径 1 Dijkstra算法的问题和改进 20 1.1 Dijkstra算法的基本步骤 18 最短路径问题是指在一个赋权图的两个指 4.4D 16 ⑧ 3.5 45 定节点和v之间找出一条具有最小权的路， 4.1 14上 4.2 国2 Dijkstra算法是一个解最短路径问题的算法，这 A 2.9 .4 5.6 个算法不仅可以找到最短的(4，)路径，而且可 12 3.4 C 4.2 以给出从，到图中所有节点的最短路径a.其基 10 /2.2 本步骤如下： 4①2.2 (I)设d(o)=0,对所有的节点w≠h来说，设 6 81012 14 收稿日期：200408-10幢回日期：200411-20 图1最优路径规划仿真地图 基金项目：国家十五科技攻关项目No.2001BA605A-02) Fig.1 Map for simulation of optimum path planning 作者简介：李整(1971一)，男，副教授，博士

第 2 7 卷 第 3 期 2 0 0 5 年 6 月 北 京 科 技 大 学 学 报 J o u r n a l o f U n i v e r s iyt o f S e i e n e e a n d eT c h n o l 0 gy B e ij i n g Vd L2 7 N o . 3 J u n 。 2 0 0 5 两种改进 的最优路径规划算法 李 擎 ” 宋顶 立 ” 张 双 江 ` , 李 哲 ” 刘 建光 ` , 王 志 良 ” l )北京科 技大学 信息 工 程学 院 , 北京 10 00 8 3 2 )河北理 工 大 学 , 唐 山 0 6 3 0 0 9 3 )唐 山 市交通局 货运 科 , 唐 LIJ 06 3 0 0 0 4)海 湾科技 集 团 , 北 京 10 0 10 2 摘 要 在 对经 典 D ij ks tr a 算法和 A * 算 法分析 的基础上对 它们 分别进 行 了改进 . 在经 典 D ij ks tr a 算法 中 , 针 对 当前 不相 连节 点间路 径长度 为无 穷大 这一特 点 , 首先对 两个节 点是 否相连 进行 判 断 ; 若 发现两 个节 点并 不相连 时 , 则 舍去 相应计 算 , 从而减 小计 算量 . 针对 A * 算法在 实 际 应用 中搜索 效率低 的缺 点 , 将经 典 A 中 算法搜 索 出的原始最 优路径 中 的节点依 次进行封 堵后 , 再按 照经 典 A * 算法 搜索 出相应 的新 最优 路径 , 最 后再 将原 始最优 路径 与这 些新 最优路 径进 行对 比 , 以便确 定最 终的最 优路径 . 仿 真研 究表 明 : 改进 的 D ij ks tar 算法 可 以减少 大量 的无关 节点 计算 , 提高运 算 的效率 ; 改进 的 A * 算法 则可 以提高 搜索 到最优 路径 的成 功率 . 关键 词 路 径规 划 ; 车 辆导 航; D ij ks atr 算法 ; A * 算法 分类号 T P 1 8 : T P 2 7 3 + . 2 3 路 径 规 划 是 指 在 旅行 前 或 旅 行 中 为 驾驶 员 提供参 考 行驶路 线 的过程 , 是 车辆 定位 与 导航 系 统 的基 本功 能之 一 针对 陆地 车辆 导航 的不 同要 求 , 在路 径 规划 中可 采 取 多种优 化标 准 , 如最 短 距 离 、 最少 行驶 时 间或 收 费 `1] . 但无 论使用 何种 标 准 , 路 径规 划最 终都 可 以归结 为在特 定道 路 网 络 中搜索 总代 价最 小 的 目标路 径 问题 . 当前 比较流 行 的方 法有 D ij k str a 算法 及 其 改进算 法如 邻 接节 点 算法 口, 、 最 短路 径 快速 算法 `习、 带 评价 函 数 的 D ij ks atr 算法 `4 ,等 等 : A * 算 法及其 改进 算法 如 双 向 启 发式搜 索`5, 、 动态 管理优 化 A * 算 法师, 、 A * 算 法 的 局部 改进 算 法 `7] 等等 ; 此 外还 有 空 间网络 分层 分 解算 法〔盯、 遗 传算 法〔9] 等 . 本 文将 主要讨 论针 对 iD - j ks tr a 和 A * 算 法 的改进 算 法 . 1 D ij k s t r a 算法 的 问题 和 改进 1 . 1 D ij ks tr a 算法 的基 本 步骤 最 短 路 径 问题 是 指 在 一 个 赋权 图 的两 个 指 定 节 点 u 。 和 v 之 间 找 出 一 条 具 有 最 小 权 的 路 . D ij ks atr 算 法 是一 个解 最 短路径 问题 的算 法 , 这 个 算 法不 仅 可 以找 到最 短 的 ( u0 , v) 路 径 , 而 且 可 以给 出从 u0 到 图中所 有节 点的最 短路径 「10 ) ” . 其基 本 步骤 如 下 : ( l) 设 d( u0 ) = 0 , 对所 有 的节 点 w 羊 u 。来说 , 设 收稿 日期 : 2 0 04刊 )8一 10 修 回 日期 : 2 0 0今 11佗0 基金 项 目 : 国家 十五科 技攻 关项 目 困.o 2 0 l0 B A 6 05 A 一 0 2) 作者 简介 : 李擎 ( 19 71 一) , 男 , 副教授 , 博士 d( w ) = 二 , 并 将 u 。标 号 为 O , t ~ u 。 . d 为 u 。和 w 之 间 的 权 值 (距 离 ) . (2 ) 按照 每个 未 标号 的节 点 w 计算 d( w ) , d( w ) = m i n {d( w ) , d( )t + l( 人w ) } , l( r , w ) 表 示 点 t 到 点 w 之 间 的权值 (距 离) . 若 d( w) 被修 改 了 , 说 明在 当前得 到 的 u 。 到 w 的最 优 路径 上 t 和 w 相 邻 , 用 wt 记录 下 来 . 在所 有 d( w) 中 , 选 择 一个 最 小 的d(s ) , 即ds( ) = m in {d( w )} , w 未标 号 . 将 , 标 号 为 d( s) wt/ , 表 示 节 点u 。 到: 的最优 路径 的长 度 为d(s ) , 且 wt 与 : 相 邻 . (3 ) 若终 点 v 已标 号 , 则停 止 . 得 到一 条 从 u0 到 v 的最优 路 径 , 否 则 t ~ : , 转 向 (2) 再计 算 . L Z D ij b t ar 算法 应用 举 例 以具体 实例 说 明 D ij ks atr 算 法 的具 体应 用 . 例 1 . 利 用 D ij k str a 算 法求 图 1 中节 点 A 到其 它 各节 点 的最 优路 径 . 2 0 尸 一一一 一 - ~ 一 一 一二 丁- - - 一 ~ 一 一 一 一 , 叭 3 . 2 3 . 2 又 5 、气`l 好汀气 月 、马l 月斗 3 · 4 \ 衍 0 2 因万乏 l _ 8 10 1 2 14 图 1 最优路 径规 划仿真 地图 F ig . l M a P fo r s im u la 肠o n o f o P肠m u m P a th Pl a n n i o g DOI: 10. 13374 /j . issn1001 -053x. 2005. 03. 028

·368 北京科技大学学报 2005年第3期 根据Dijkstra算法的实现步骤，其计算过程可 点的最短路径也相应求出.若以计算一次d(w)= 归纳为表1所示. min{d《w),dt)+l(t,w)}为计算单位，则利用Dijkstra 从表】中可以看出，从A到P的最短路径为 算法计算A到P最短路径时所需的计算次数 AC一FJMO一P,且A到P的距离为dA,P TP)=15+14+13+…+2=119次. 183.在求A到P最短路径的过程中，A到其余各 表1采用Dijkstra算法求解A到其他各节点最优路径的过程 Table 1 Calculation process for an optimum path by use of Dijkstra's algorithm 序号ABC K L M NO P 1 42 3.4 0 0 0 00 0 00 00 0 00 00 2 4.23.4/A 00 9.0 6.9 00 0 00 00 0 3 4.2/A 8.6 8.3 6.9 00 00 0 00 0 00 8.6 8.36.9/C 00 11.9 10.9 0 5 8.5 8.3/8 10.3 11.2 10.9 00 6 8.6/B 11.510.3 11.2 10.9 0 11.510.3/D11.2 10.9 13.5 13.7 11.5 11.210.9/F13.5 13.7 13.1 11.5 11.2/E 13.5 13.7 13. 10 11.5/D 13.5 13.7 13.1 00 13.5 13.713.1 00 16.1 12 13.5H13.7 18.016.1 13 -13.7/H 15.916.1 g 15.9/L16.118.7 15 -16.1/M18.3 13 Dijkstra算法的不足 下面仍以一个具体实例来说明改进的Djks- 在现行电子地图中，网络模型的规模常常较 ra算法的具体应用， 大，节点数多达上千或上万，并且对网络模型的 例2.利用改进的Dsta算法求图1中节点 查询也要求实时性.因此，Dijkstra算法虽然在理 A到其他各节点的最优路径.此例的计算过程和 论上是可行的，但在实际应用中不尽人意，当网 Dijkstra算法基本一致，只是表1中所有o标记的 络模型中节点数和边数较多的情况下，算法的计 部分在改进Dijkstra算法中被省去了，利用改进 算量较大，时间花费较多，效率非常低， 的Dijkstra算法计算A到P最短路径时所需计算 1.4改进Dijkstra算法的基本思想及实现 次数为T(P)=47次，由此可见，改进的Dijkstra算 表1中的数值大多数是∞，都是无用运算，如 法确实减小了计算量（在程序设计中，判断语句 果节点数量很大，将极其浪费运算时间，由于 所花费的时间可以忽略，并不增大计算量) dw)=min{dw),dt+lt,w)},w节点是否在上次己 1.5实验对比 经被计算出最短路径未知，当前节点w是否与节 为了更好地说明改进的Dijkstra算法的有效 点t是否相连也未知，也就是l(1,w)未知，这时d) 性，利用C语言自行编制了最短路径搜索程序并 是已知的，故本次计算的dw)到底是不是∞，取决 进行了仿真实验，采用自绘制的地图，共5张，第 于上一步w)数值和(，w)的数值，从表达式可 一张图16个节点，共24条弧：第二张图32个节 以看出，只要这两个数值不都是∞，本次计算的 点，共55条弧：第三张图43个节点，共75条弧： cdw)就不会是o,所以在上面Dijkstra算法的实现 第四张图62个节点，共111条弧：第五张图78个 步骤第(2)步时，先判断一下，只要原来的(w), 节点，共139条弧.计算结果如表2所示. t,w)的数值中至少有一个不是0，才进行下面的 从表2可以看出，两种算法的计算量有很大 计算dw)=min{dw),dt+lt,w)},这样就保证了 的区别，改进的Dijkstra算法较之经典Dijkstra算 当预见dw)是o时，不对它进行计算，避免了大 法在计算量方面有很大幅度的减少，而且这种减 量无效的计算，提高了搜索效率， 少的程度在节点数目增加（地图更大，更复杂）时

一 3 6 8 - 北 京 科 技 大 学 学 报 2 0 0 5 年 第 3 期 根据 D ij ks tr a 算法 的 实现 步骤 , 其 计算 过程 可 归纳 为表 1 所示 . 从表 1 中可 以看 出 , 从 A 到 尸 的最 短 路径 为 A一C 一 尸一决 一 材= 口- 尹 , 且 A 到 尸的距 离 为试月 , )P = 1.8 3 . 在求 A 到 尸最 短 路径 的过 程 中 , A 到 其 余各 点 的最短 路径 也相 应 求 出 . 若 以计算 一 次d( w) = m i n {d( w ) , d( r ) + l ( r , w )} 为计 算单 位 , 则利 用 D ij k s tr a 算 法计 算 A 到 尸 最 短 路 径 时所 需 的计 算 次 数 八尸) = 15+ 14+ 13+ …+ 2 = 1 19 次 . 表 1 采 用 D ij 灿 t ar 算 法求解 A 到其 他各节 点最优路 径的 过程 aT b l e 1 C a l e u l a ti o n p or e e s s fo r a n o P h m u m P a th b y u s e o f D ij ks t r a , s a lg o r i t h m 序 号 g Q 声 : 乙曰`U 0 飞 . : 9只 l 2 3 4 5 6 7 8 9 l 0 l l 翅 B C D E F G H 1 J K L 例 N O P 一 4 2 3 . 4 叨 的 刃 如 刃 co 的 的 的 的 的 的 的 4 . 2 3 . 4 A/ 的 4 . 2阴 83 83 /8 6 一 9 /C 的 的 10 3 8 . 6 B/ 11 , 5 10 3 1 1 . 5 10 3 D/ 1 1 . 5 一 1 1 5 一 11 . 9 11 . 2 11 . 2 11 2 11 . 2 11 . 2 /E 10 乡 10 乡 10 乡 10 . 9 10 , 9F/ 865 1 1 . 5 D/ 16 l 2 l 3 l 4 l 5 13 . 5 13 7 的 co 13 . 5 13 7 13 . 1 的 13 5 13 刀 13 . 1 ① 13 . 5 13 7 13 . 1 的 13 . 5 13 7 13 . 1/J ① 1 3 . S ZH 13 7 一 18 刀 一 13 7 / H 一 15 . 9 一 一 一 15 乡L/ 16 . 1/ M 18 7 18 . 3 1 . 3 D ij ks tr a 算法 的不 足 在 现行 电子 地 图中 , 网 络 模型 的规模 常 常较 大 , 节 点数 多达 上千 或 上万 , 并且 对 网络 模 型 的 查询 也要 求 实时 性 . 因此 , D ij ks atr 算 法虽 然在 理 论上 是可 行 的 , 但在 实 际 应用 中不尽 人意 , 当 网 络模 型 中节 点数 和边 数较 多的情 况下 , 算法 的计 算 量较大 , 时 间花 费较 多 , 效率 非常 低 . 1 . 4 改 进 D ij ks t ar 算 法 的基本 思想 及 实 现 表 1 中 的数值 大多 数是 。 , 都 是无用 运算 , 如 果 节 点数 量 很大 , 将 极 其 浪 费运 算 时间 . 由于 d( w ) = m i n {d( w ) , d( r ) + l ( r , w ) } , w 节 点是 否 在上 次 己 经被 计算 出最短 路径 未知 , 当前 节 点 w 是否 与节 点 t 是 否相 连也 未知 , 也 就 是l(t , w) 未 知 , 这 时d( )t 是 已 知 的 , 故本 次计算 的d( w) 到底是不 是二 , 取决 于 上 一 步 d( w ) 数值 和 l(t , w) 的数值 , 从表 达 式可 以看 出 , 只 要这 两 个数 值不 都是 二 , 本 次计算 的 d( w )就 不会 是 二 . 所 以在上 面 D ij ks tr a 算法 的 实现 步 骤第 (2 ) 步 时 , 先判 断一 下 , 只 要 原来 的d( w ) , l( t , w ) 的数值 中至 少有一个 不是 二 , 才 进行下 面 的 计 算 d( w ) = m i n 丈d( w ) , d( r ) + l( t , w ) } , 这 样 就 保 证 了 当预见 d( w )是 二 时 , 不对 它进 行 计算 , 避 免 了大 量 无效 的计 算 , 提 高 了搜索 效率 . 下 面仍 以一 个具 体 实例来 说 明改进 的D ij ks - tr a 算 法 的具 体应用 . 例 2 . 利用 改进 的 D ij ks atr 算 法 求 图 1 中节 点 A 到其他 各 节 点的最 优路 径 . 此例 的计算 过程 和 D ij ks atr 算 法基 本 一致 , 只 是表 1 中所有 二 标记 的 部 分在 改进 D ij ks atr 算 法 中被省 去 了 , 利 用改 进 的 D ij ik atr 算法 计算 A 到 尸 最短 路径 时所 需计 算 次 数为 厂()P = 4 7 次 . 由此 可 见 , 改进 的 D ij ks tr a 算 法确 实减 小 了计 算量 (在 程 序设 计 中 , 判 断语 句 所花 费 的时 间可 以忽 略 , 并 不增大 计算 量 ) . L S 实 验对 比 为 了更好地 说 明改进 的 D ij ks tr a 算法 的有 效 性 , 利用 C 语 言 自行编 制 了最短 路径 搜索 程序 并 进行 了仿 真实 验 , 采 用 自绘制 的地 图 , 共 5 张 , 第 一 张 图 16 个 节 点 , 共 2 4 条 弧 ; 第 二 张 图 32 个 节 点 , 共 5 条弧 ; 第 三张 图 43 个 节 点 , 共 75 条 弧 ; 第 四张 图 62 个 节 点 , 共 11 条弧 ; 第 五张 图 78 个 节 点 , 共 13 9 条 弧 . 计算 结果 如表 2 所示 . 从表 2 可 以看 出 , 两种 算法 的计 算量 有很 大 的 区 别 , 改进 的 D ij ks atr 算 法较 之经 典 D ij ks tr a 算 法在 计算量 方面 有很大 幅度 的减少 , 而 且这种 减 少 的程度 在节 点 数 目增 加 (地 图更大 , 更 复杂 ) 时

Vol.27N0.3 李擎等：两种改进的最优路径规划算法 ·369· 会变得越来越明显.对于实际系统，由于地图都 信息是人为加入的，有很大的主观性，直接取决 会很大，使用改进Dijkstra算法的改进效果将非 于操作者的经验，对于不同的情形要用不同的启 常显著. 发信息和启发函数，且他们的选取难度比较大， 表2改进Dijkstra算法和经典Di时kstra算法计算次数 很大程度上找不到最优路径，.下面通过一个具 Table 2 Computing overhead of the improved Dijkstra's and tra- 体加以实例说明. ditional Djkstra's algorithm 例3.利用A*算法求图1中从A点出发到N 节点数 经典Dijkstra算法改进的Dj冰stra算法 点的最优路径， 16 119 47(39.5%) 解：在本例中，将评价函数f八广gn)+h()中 32 465 134(28.8%) 的g)取为当前节点到起始节点A的最短距离， 43 861 234(27.2%) 62 而h()取为当前节点到目标节点N的欧氏距离， 1830 441(24.1%) 8 2926 540(18.5%) 在应用A*算法时除采用上面Dijkstra2算法所用过 注：表中的百分数表示改进算法计算量与经典算法计算量的 的拓扑结构外，还应该再给定所有节点的坐标 百分比 Node(x,y),如各点坐标为A(0,13),B(3,I6),C(3, 2A*算法的问题和改进 11),… 根据A*算法的具体实现步骤，可求得从A到 2.1A*算法的基本思想 N的最短路径是AC一E一H一L一N,其距离是： A*算法在人工智能中是一种典型的启发式 dA,N0=16.6. 搜索算法.通过选择合适的估价函数，指导搜索 查看表I可知，用Dijkstra算法搜索的最优路径是 朝着最有希望的方向前进，以求得最优解☒.A* A一B-E一H-L-N,路径长度15.9，很明显A*算 算法中，关键是求估价函数： 法没有找到最优路径，而且通过比较两条路径可 f(n)=g(n)+h(n) 以发现：当采用A*算法搜索路径时，从第二个节 其中，gm)是从起点到当前节点n已付出的代 点就把最优路径舍弃了. 价，h(n)是从当前节点n到目标节点v的代价估计 2.4A*算法改进思想及实现 函数，必须保证h(n)≤h(n(其中h(n)是从当前点 为了克服最优路径可能被轻易舍弃的缺点， 到目标点的实际最小代价) 本文提出采用多次搜索的方法，用增大计算量为 2.2A*算法的步骤 代价来换取尽量多的最优路径备选结果.具体的 A*算法的搜索步骤如下： 方法如下：将经典A*算法搜索出原始最优路径 (1)给起始节点标记，对它的没有标记过的子 中的节点依次进行封堵后，再按照经典A*算法 节点进行扩展： 搜索在每一次封堵情况下的最优路径.最后将这 (2)对每一个子节点计算评价函数值，按评价 些新的最优路径与原始最优路径进行对比以便 值的大小进行排列，找出评价值最小的节点，并 确定最后的最优路径.现举例说明改进A*算法 给它作标记，如果当前节点就是目标节点，则停 的具体应用. 止搜索： 例4.利用改进的A*算法求图1中从A点出 (3)否则，对最新被标记的节点进行第(2)步 发到W点的最优路径， 处理，并记录最短路径 (I)按A*算法寻找路径得到：A一C一E-H一L 2.3A*算法分析 一N,路径长度16.6： A*算法是利用对问题的了解和对问题求解 (2)封闭此路径中节点C后得到的最优路径 过程和解的了解，寻求某种有利于问题求解的启 为：A-B-E-H-L-N,路径长度15.9： 发信息，从而利用这些启发信息去搜索最优路 (③)封闭此路径中节点E后得到的最优路径 径.它不用遍历整个地图，而是每一步搜索都根 为：AC一F-1-LW,路径长度17.1； 据启发函数朝着某个方向搜索，当地图很大很复 (4)封闭此路径中节点H后得到的最优路径 杂时，它的计算复杂度大大优于Dijkstra算法，是 为：AC-E-IL-W,路径长度17.2： 种搜索速度非常快、效率非常高的算法 (⑤)封闭此路径中节点L后得到的最优路径 但是，相应的A*算法也有它的缺点.启发性 为：AC一E-H-KN,路径长度18.7：

叭, 1.2 7 N 0 . 3 李 擎等 : 两种改 进的 最优路 径规 划算 法 . 3 6 9 - 会变 得越 来 越 明显 . 对 于 实 际系统 , 由于 地 图都 会 很 大 , 使 用 改进 D ij ks atr 算 法 的改进 效 果将 非 常显 著 . 表 2 改进 D ij ks t ar 算法 和经 典 D ij ks tar 算法计 算次数 aT b le 2 C o m P u it . g o v e r h e a d o f t h e im p 门v e d D ij ks t ar , s a . d t ar - di幼o . a l jD 如t r a , 5 a lg o ir ht m 节 点数 经典 D ij ks atr 算法 改进 的 D ij ks tr a 算法 16 1 19 4 7 ( 39 乃% ) 3 2 4 6 5 13 4 ( 2 8 名% ) 4 3 8 6 1 2 3 4 (2 7 2 % ) 6 2 1 8 3 0 4 1 (2 4 . 1% ) 7 8 2 9 2 6 5 4 0 ( 18 ) % ) 注 : 表 中的 百分数表 示改 进算法 计算量 与经 典算法 计算量 的 百分 比 Z A * 算法 的 问题 和 改进 .2 I A * 算 法 的基 本思 想 A * 算 法 在 人 工智 能 中 是一 种 典型 的启 发式 搜索 算法 . 通 过选 择合 适 的估 价 函 数 , 指 导搜 索 朝着最有 希 望 的方 向前 进 , 以求得 最优 解 `lz] . A * 算法 中 , 关键 是 求估 价 函 数 : f( n )飞 ( n ) + h ( n ) . 其 中 , 爪n) 是 从起 点 u 。 到 当前 节 点 n 己 付 出 的代 价 , h( n) 是 从 当前节 点 n 到 目标 节 点 v 的代价 估 计 函 数 , 必 须 保证 h (n) ` ’h (n) (其 中’h ( n) 是 从 当前 点 到 目标 点 的实 际最 小代 价 ) . .2 2 A * 算 法 的步 骤 A * 算 法 的搜 索步 骤 如下 : ( l) 给 起始 节 点标记 , 对 它 的没有标 记过 的子 节 点进 行扩 展 ; (2 )对 每一个 子 节点计 算评 价 函数值 , 按评 价 值 的大 小进行 排 列 , 找 出评 价值 最 小 的节 点 , 并 给 它 作标 记 , 如 果 当前 节 点就是 目标节 点 , 则 停 止 搜 索 : (3 ) 否则 , 对 最新 被 标记 的 节点进 行 第 〔2) 步 处 理 , 并 记录 最短 路 径 . .2 3 A * 算法 分析 A * 算法 是 利 用对 问题 的 了解 和对 问题 求解 过程 和解 的 了解 , 寻求 某种 有利 于 问题 求解 的启 发信 息 , 从 而利 用 这 些启 发 信 息 去搜 索 最优 路 径 . 它 不用 遍 历整 个地 图 , 而 是每 一 步搜 索都 根 据启 发 函数 朝 着某个 方 向搜索 . 当地 图很大 很复 杂时 , 它 的计算 复 杂度 大大 优 于 D ij ks tr a 算 法 , 是 一种 搜索 速 度非 常快 、 效率 非 常高 的算法 . 但 是 , 相应 的 A 水 算 法也 有它 的缺 点 . 启 发性 信 息是 人 为加 入 的 , 有很 大 的主观 性 , 直接 取决 于操 作者 的经 验 , 对 于 不 同的情 形要用 不 同的启 发信 息 和启 发 函数 , 且他 们 的选 取难度 比 较 大 , 很大 程度 上 找不 到最 优 路径`la] . 下面通 过 一个 具 体加 以实例 说 明 . 例 3 . 利用 A * 算 法求 图 1 中从 A 点 出发 到 N 点的 最优 路径 . 解 : 在本 例 中 , 将评 价 函 数刀 刀 )气抓 刀 )+h (n ) 中 的以n) 取 为 当前节 点 到起 始节 点 A 的最 短距 离 , 而 h( n) 取 为 当前节 点 到 目标节 点 N 的欧 氏距 离 , 在应 用 A * 算法 时 除采用 上面 D ij ks atr 算 法所用 过 的拓 扑结 构 外 , 还 应 该 再给 定所 有 节 点 的坐 标 No d e x( , y ) , 如 各 点坐 标为 A (0 , 13) , B ( 3 , 16 ) , C ( 3 , 1 1) , ” ` · 根据 A * 算 法 的具 体实 现步 骤 , 可 求得从 A 到 N 的最 短路 径 是 A一C 一石一月匕去一万 , 其 距 离是 : d (A , 的 = 16 . 6 . 查 看表 1 可知 , 用 D ij ks tr a 算法 搜索 的最 优路 径是 A一刀一刃一月二去一 - 厅 , 路径 长 度 1.5 9 , 很 明显 A * 算 法 没有找 到最 优路 径 , 而且通 过 比 较两 条路径 可 以发现 : 当采用 A * 算 法搜 索路 径 时 , 从第 二个 节 点就 把 最优 路径 舍 弃 了 . .2 4 A * 算 法 改进 思想 及 实现 为 了克服最 优路 径可 能 被轻 易舍 弃 的缺点 , 本 文提 出采 用 多次搜 索 的方法 , 用增 大计 算量 为 代价来 换取 尽量 多 的最 优 路径备 选结 果 . 具体 的 方 法 如下 : 将 经 典 A * 算法 搜索 出原始 最优 路径 中的节 点依 次 进行 封 堵后 , 再按 照经 典 A * 算法 搜 索在每 一 次封堵 情况 下 的最优 路径 . 最后 将这 些 新 的最 优 路 径 与原 始 最优 路 径 进行 对 比 以便 确 定最 后 的最优 路 径 . 现 举例 说 明改 进 A * 算法 的具 体应 用 . 例 4 . 利 用 改进 的 A * 算法 求 图 1 中从 A 点 出 发到 N 点 的最 优 路 径 , ( l) 按 A * 算 法 寻找 路径 得 到 : A 一C 一召一 ~ 万叫乙 一万 , 路径 长度 16 .6 ; (2 ) 封 闭此 路径 中节 点 C 后 得 到 的最优 路 径 为 : A一召一忍一月性扭一刀 , 路 径 长度 15 . 9 ; (3 ) 封 闭此路 径 中节 点 E 后 得 到 的最优 路径 为 : A一C 一尸一介也一 - 万 , 路径 长度 17 . 1 ; (4 ) 封 闭此 路 径 中节 点 H 后 得 到 的最优 路径 为 : A一C 一丑一弄王一万 , 路径 长度 1.7 2 ; (5) 封 闭此 路径 中节 点 L 后得 到 的最优 路 径 为 : A一 C 一百一万` 犬` 刃 , 路 径长 度 1.8 7 ;

·370· 北京科技大学学报 2005年第3期 对前面求得的5种路径长度进行对比，得到 算量（但远远小于Dijkstra算法的计算量），却大大 最优路径为A一B-E-H-L-W,其长度为15.9，从 增大了搜索到最优路径的成功率， 而将此路径定为改进A*算法求得的最优路径 参考文献 查看表1可知，此路径正是采用Dijkstra算法时求 [1】苏永云，晏克非，黄翔，等，车辆导航系统的动态最优路径 得的最优路径 搜索方法研究.系统工程，2000,18(4)：327 2.5实验对比 [2]龚洁辉，白玲，高健美，最短路径算法的改进及其实现，解 为了进一步验证改进A算法的有效性，利 放军测绘学院学报，1998,152)：23 用C语言自行编制了最短路径搜索程序并进行 [3]周培德，交通道路网中任意两点之间最短路径的快速算 法.计算机研究与发展，2002,242)：35 了仿真实验.以78个节点（含1个起始节点，77个 [4]鲍培明.距离寻优中Dijkstra算法的优化.计算机研究与 待规划节点)的地图作为对象得到的仿真结果： 发展，2001,38(3)：307 采用经典A*算法对77个节点分别进行路径规 「5]孟以沿，张明路，刘大维，等.基于双向A算法的自土4 划，有45个找到了最优路径.而采用改进的A*算 全问路径规划，天津大学学报，1998.31(6)：24 [6段莉琼，朱建军，王庆社，等，改进的最短路径搜索A◆算 法对77个节点进行路径规划时，有68个找到了 法的高效实现.海洋测绘，2004,24(5：19 最优路径，有8个节点虽未找到最优路径但得到 [刀武元新.人工智能中A·算法的局部改进及其实现.微型 了比经典A*算法更短的路径，只有1个节点和经 电脑应用，2000,16(3)：21 [8]Frank Blischke and Bernd Hessing.Dynamic Route Guidence- 典A*算法结果一致，这充分说明，改进的A*算 Different Approaches to the System Concepts.Soc Automatic 法较之经典的A*算法在搜索最优路径的成功率 Eng,Inc,1998 方面具有明显的优势， [9例杨云，孙向军，曹立鑫，等.一种启发式遗传算法及其在最短 路径求取中的应用.计算机工程与应用，2003(1)上12 3结论 [10]孟禅云.最短路径及其求法.唐山高等专科学校学报，2000 (2):22 本文对经典Dijkstra算法和A*算法进行了改 [11]Lee J.Calculation of the shortest path sbyoptimal decomposi- 进，改进后的算法具有以下特点 tion.IEEE Trans Syst Man Cybern,1982(3):410 (I)改进的Dijkstra算法能在很大程度上节省 [12】樊莉，孙继银，王勇.人工智能中的A·算法应用及编程 微机与发展，2003,13(5)：335 计算量，提高路径规划的速度， [13引赵伟华，章复嘉，梁红兵.车辆导航系统最优路径规划的 (2)改进的A*算法虽在一定程度上增大了计 研究与实现.杭州电子工业学院学报，2003,2341)：16 Two improved optimum path planning algorithms LI Oing",Song Dingli,ZHANG Shuangjiang,LI Zhe,LIU Jianguang,WANG Zhiliang 1)Information Engineering School,University of Science and Technology Beijing,Beijing 100083,China 2)Hebei Polytechnic University,Tangshan 063009,China 3)Freight Section of Traffic Bureau Tangshan,Tangshan 063000,China 4)Gulf Science and Technology Corporation,Beijing 100102,China ABSTRACT An improved Dijkstra's and an improved A*algorithm were proposed based on the analysis of their drawbacks.In the traditional Dijkstra's algorithm,the distance between two unconnected nodes is infinite and some relative calculations are useless.The improved Dijkstra's algorithm proposed that the connection between nodes should be tested at first so that it can decrease the computing overhead to a great extent.When the traditional A*al- gorithm is used in practice,its efficiency is not satisfied.The improved A*algorithm includes such steps as the fol- lowing:firstly,the original optimum path should be planned by the traditional A*algorithm;secondly the nodes in the original optimum path;should be blocked in turn and the traditional A*algorithm is used again in order to look for another new optimum path.finally,these new optimum paths should be compared with the original one so that the final optimum path can be selected.Simulation results show that the improved Dijkstra's algorithm can enhance the calculation efficiency and the improved A*algorithm can find the more optimum path. KEY WORDS optimum path search;intelligent vehicle guidance and location;Dijkstra's algorithm;A*algorithm

3 7 0 北 京 科 技 大 学 学 报 2 0 0 5 年 第3 期 对 前面 求得 的 5 种 路径 长 度进行 对 比 , 得 到 最优 路径 为 A一刀- 忍一万` 乙一宁V , 其长 度为 15 . 9 , 从 而 将此 路径 定 为 改进 A * 算 法求 得 的最 优 路径 . 查看表 1 可 知 , 此 路 径正 是采 用 D ij ks atr 算法 时求 得 的最优 路 径 . .2 5 实验对 比 为 了进一 步验 证 改进 A * 算法 的有 效性 , 利 用 C 语 言 自行编 制 了最 短路 径搜 索程 序并 进行 了 仿真 实验 . 以 78 个 节点 (含 l 个起始 节 点 , 7 个 待规 划节 点 ) 的地 图作为对 象 得到 的仿 真 结果 : 采用 经典 A * 算法 对 7 个节 点 分别 进行 路 径规 划 , 有 45 个 找 到了最优 路径 . 而采 用改进 的A * 算 法对 7 个节 点进行 路径 规划 时 , 有 68 个找 到 了 最优 路径 , 有 8 个节 点虽未 找到 最优 路径但 得 到 了比经 典 A * 算 法更 短 的路 径 , 只 有 1 个节 点和 经 典 A * 算 法 结果 一致 . 这充 分说 明 , 改进 的 A * 算 法较 之经 典 的 A * 算 法在 搜索 最优 路径 的成 功 率 方面 具有 明 显 的优 势 . 3 结 论 本 文对 经 典 D ij ks tr a 算 法和 A 中 算 法进 行 了改 进 , 改进 后 的算 法具 有 以下特 点 . ( l) 改进 的 D ij ks tr a 算法 能在 很大 程度 上节 省 计算量 , 提 高路 径规 划 的速度 . (2 ) 改进 的 A * 算法 虽在 一定 程度 上增 大 了计 算 量 (但 远远 小于 D ij ks tr a 算法 的计 算量 ) , 却 大大 增大 了搜 索到 最优 路径 的成 功率 . 参 考 文 献 【l] 苏永云 , 晏克非 , 黄翔 , 等 . 车 辆导航系 统的动态 最优路径 搜索 方法研 究 . 系统 工程 , 2 00 , 18 (4 ) : 327 12 ] 龚洁辉 , 白玲 , 高健美 . 最短 路径算法 的改进及其 实现 . 解 放 军测绘 学院学报 , 19 8 , 巧 (2 ) : 23 兀3] 周培 德 . 交通道 路 网中任意 两点之 间最短路 径的快速 算 法 . 计算 机研 究与发展 , 2 002 , 2 4 (2) : 35 4[ ] 鲍培 明 . 距 离寻优 中 D ij k s t r a 算法 的优化 . 计 算机 研究与 发 展 , 2 0 0 1 , 38 ( 3) : 3 0 7 15 」 孟 庆 浩 , 张 明路 , 刘大维 , 等 . 基于 双 向 A 水 算 法的 自主 介 , 全 局 路径 规划 。 天 津大 学学报 , 1 998 , 31 (6 ) : 24 6[ 】 段莉 琼 , 朱 建军 , 王 庆社 , 等 . 改进 的最短路 径搜 索 A * 算 法的 高效 实现 . 海洋测 绘 , 2 0 04 , 24 (5 ) : 19 7[ ] 武 元新 . 人 工 智能 中 A 巾 算法 的局部 改进及其 实现 . 微 型 电脑应用 , 2 0 0 , 16 ( 3) : 2 1 [ 8 ] F r an k B li s e hk e an d B e m d eH s s in g . D y n am i e R o u t e G u ide n e卜 D i fe r e n t A P P r o ac h e s t o ht e Sy s te m C o n c e Pt s . S o c A u t o m a it e E n g , I cn , 1 99 8 9[ l 杨 云 , 孙向军 , 曹立鑫 , 等一种 启发式遗传 算法及其 在最短 路径 求取 中的应用 . 计算机 工程 与应 用 , 2 0 0 3 (:1) 12 【10 ] 孟祥 云 . 最 短路 径及其求法 . 唐 山高等专科 学校 学报 , 2 00 ( 2 ) : 2 2 [川 L e e J . C a l e u lat i o n o f ht e s h o rt e st P aht s by o Pt而al de e om P o s i - ti o n . IE E E 介 . n s S y s t M a n C y b e 几 , 19 82 ( 3 ) 二4 10 【12 ] 樊莉 , 孙继 银 , 王 勇 . 人 工 智 能中的 A . 算法应 用及编程 . 微 机与 发展 , 2 0 0 3 , 13 ( 5 ) : 3 3 5 【13 1 赵伟 华 , 章复嘉 , 梁红 兵 . 车辆导 航系统 最优路径 规划 的 研 究与实现 · 杭州 电 子工 业学院 学报 , 20 03 , 23 (l ) : 16 T w o im P or v e d o P t im u m P aht P l aun i n g a l g o ir ht m s L l Q i叮 ` , , oS 馆 D i ngl i , ) , 乙队4N G hS u a 叨i a 馆 ` ), IL hZ 扩 ), LI U iJ WA N G hZ ili a gn , ) l ) I n fo mr at ion E n g l n e e inr g S e h o o l , U n i v er s ity o f s e i e n e e an d eT e hn o l o gy B e ij ing , B e ij i n g l 0 0 08 3 , C h ian 2) H e b 记1 P o ly t e e h n i e U n iV e r s询 , T an g s h an 0 6 3 0 0 9 , C h in a 3 ) F re i ght S e e t i o n o f T r a if e B ur e au l 初 l g sh an , T an g s h an 0 6 30 0 0 , C h in a 4 ) G u lf S e i e n e e an d eT e ho o l o gy C o rp or at i o n , B e ij i n g 10 0 10 2 , C h in a A B S T R A C T A n im P r o v e d D ij k s tra , 5 an d an im P r o v e d A * a lg o ir th rn w e er P r 0 P o s e d b as e d o n ht e an a ly s i s o f ht e i r dr a w b ac ks . hi het t r a dit o n a l Dij ik tr ’as al g o r it hln , t h e id s t a n c e be wt e en wt 0 ucn 0 en cet d on de s is i n if n i t e an d s om e r e lat i v e e a l e u lat i o n s ar e u s e l e s s . hT e im rP o v e d D ij ik atr , 5 a lg ior th m P r o P o s e d ht at ht e e o uen e t i o n b e wt e e n n o d e s s h o u l d b e t e s t e d at if s t 5 0 ht at i t e an d e e er a s e ht e e o m Piut n g o v e ht e ad ot a ger at e x t e in . 认币e n t h e tr ad i t i on a l A * a l - g ior t h rn 1 5 us e d i n P r a e t i e e , i t s e if e i e n e y 1 5 n o t s at i s if e d . hT e im P r o v e d A * al g o ir t知nr in e l u de s s cu h s te P s a s t h e fo l - 1 0 初n g : if r s t ly, ht e o ir g i an l o P t im um P hat s h ou ld b e P l an e d b y ht e tr a di t i o an l A * a lg o ir th m : s e e o n d ly het n o d e s in th e o ir g i n a l op t诵 um Pat h: s h o u ld b e b l o e ke d in t l l r l l a n d ht e tr a dit i aon l A * a l g o ir th nr 1 5 su e d a g ia n i n or d e r t o l o o k fo r an o th e r n e w o P ti m um P at h . if n a lly, ht e s e n e w o Pt加um P hat s s h o lu d b e e o m Par e d w iht ht e o ir g in a l o n e 5 0 t h at ht e if n a l o Pt lm u r n P hat e an b e s e l e e t e d . S im u l at i o n er s lu t s hs o w th a t ht e im Por v e d D ij k s ’atr s a l g o r it h m e an e hn acn e the e a l e u lat i o n e if e i e n e y an d ht e i m P or v e d A * a l g o ir th m e an if dn het m oer o P t汕um P hat . K E Y W O R D S o P tim切 m P hat s e aer h ; i n t e 1l ige nt v ihe e l e glu d a n c e an d l o e iat o n : Dij ks tr 澎s al go ir ht m ; A * al go ir t加m