D0I:10.13374/1.issnl00103.2007.03.022 第29卷第3期 北京科技大学学报 Vol.29 No.3 2007年3月 Journal of University of Science and Technology Beijing Mar.2007 一种基于Di.jkstra算法的启发式最优路径搜索算法 王景存2)张晓形陈彬)陈和平2) 1)北京科技大学信息工程学院，北京1000832)武汉科技大学信息科学与工程学院，武汉430081 摘要为了建立一个高效的路径搜索引擎，针对大型应用系统中寻径算法的平衡最优性，时间复杂度以及空间复杂度问 题，从经典Dijkstra算法出发，将AI领域的决策机制引入到路径搜索中来，提出了一个启发式最优路径搜索算法.该算法在寻 径过程中引入代价函数，由代价函数来决定寻径策略（即优先搜索哪些中间节点），以期望减少搜索节点数·给出了该算法得 到最佳解的条件及其证明过程，并且以实例数据对两种算法进行了对比测试， 关键词路径搜索；导航；启发式：最优 分类号TP301.6 路径搜索是地理信息系统、导航系统以及计算 考虑到寻径算法的计算中，在寻找两点之间路径的 机网络等高级系统中的一个典型应用，通常需要考 最优而非最佳解时有较佳的表现：但为了尽量逼近 虑以下几个方面：第一，网络规模庞大，节点数量较 最佳解，必须对图搜索两次， 多；第二，路径搜索频繁；第三，需要近乎实时的相应 为了解决大型应用系统中寻径问题，且使算法 速度，如果系统是应用在移动设备上，还需要考虑 能较好地平衡最优性、时间复杂度以及空间复杂度， 设备的硬件资源（运算、存储等）有限等因素， 本文提出了一种启发式最优路径搜索算法(heuristic 在众多的路径搜索算法中，Dijkstra算法提供了 optimization pathfinding algorithm,HOPA),即在寻 从图的一个节点到另一个节点的最短路径，经过一 径过程中引入代价函数，由代价函数来决定寻径策 次Dijkstra算法计算，可以得到从起点到图内被其 略（即优先搜索哪些中间节点），以期望减少搜索节 搜索到的所有节点的最短路径，其时间复杂度为 点数，从而降低其时间复杂度 o(n)(其中n为图的节点数)，但是在实际应用 中，所关心的是某两个特定节点之间的最短路径而 1HOPA算法 非起点到其他点的情况，且在大规模网络中Dijkstra 1.1启发式路径搜索(heuristic pathfinding,HP) 算法的时间复杂度较高，使其应用受到限制，文 定义1寻径算法可应用的网络可以用定义来 献[1]提出了利用堆数据结构来改善Dijkstra算法 G=(V,E)描述，其中V={uv:x,y〉，E= 的寻径速度，但对Dijkstra算法的时间复杂度性能 VRl,VR=k u,IP(u,)A(u,vE V)1.V 提高有限.文献[2]提出了预先计算图中每对节点 为网络中的节点的有穷非空集合，〈xi,y〉为节点v: 之间的最短路径并存储在数据库中，在实际应用时， 的地理坐标，VR为网络中两个顶点之间的关系集 根据起点和终点直接在数据库中查询的方法，该方 合，P(,)为从顶点u到顶点v一条边的权. 法的时间复杂度得到了很大程度的降低，但是额外 Dijkstra算法首先建立了一个集合V=uv: 存储空间开支较大，文献[3]根据文献[2]的思路， ∈V},该集合初始化时只有一个元素，即路径的起 将数据库视图进行分层、编码以便于查询且减少存 始节点，V'为V'的补集，其计算步骤为：在V'中 储空间耗费.这种方法只适合静态图，如果图的拓 找到所有与V'直接相连的节点，然后将这些节点中 扑结构发生变化，则必须更新数据库和编码：而且对 与V'之间具有最小权值的节点添加到V'中，如此 于移动设备来说，这种额外的存储空间开支使得本 循环直到将终点ve添加到V'中，Dijkstra算法实 就稀缺的存储资源显得更加捉襟见肘，文献[4]结 际上是宽度优先的搜索算法，它对所有与V直接相 合地理信息系统的特点，将起点和终点的地理信息 连节点采取同等对待策略，因此导致了Dj以stra算 收稿日期：2006-0405修回日期：2006-10-20 法为了找到最短路径需要搜索较多的节点，时间复 基金项目：中国科学院计算所知识创新工程“HPC-OG模拟系统及 杂度也就相应地较高，当然这种平等对待的策略也 相关技术”研究项目(N。-20036040) 作者简介：王景存(1963一)，男，副教授，博士研究生 是该算法取得最佳解的保证
一种基于 Dijkstra 算法的启发式最优路径搜索算法 王景存12） 张晓彤1） 陈 彬2） 陈和平2） 1） 北京科技大学信息工程学院北京100083 2） 武汉科技大学信息科学与工程学院武汉430081 摘 要 为了建立一个高效的路径搜索引擎针对大型应用系统中寻径算法的平衡最优性、时间复杂度以及空间复杂度问 题从经典 Dijkstra 算法出发将 AI 领域的决策机制引入到路径搜索中来提出了一个启发式最优路径搜索算法．该算法在寻 径过程中引入代价函数由代价函数来决定寻径策略（即优先搜索哪些中间节点）以期望减少搜索节点数．给出了该算法得 到最佳解的条件及其证明过程并且以实例数据对两种算法进行了对比测试． 关键词 路径搜索；导航；启发式；最优 分类号 TP301∙6 收稿日期：20060405 修回日期：20061020 基金项目：中国科学院计算所知识创新工程“ HPC－OG 模拟系统及 相关技术”研究项目（No．20036040） 作者简介：王景存（1963－）男副教授博士研究生 路径搜索是地理信息系统、导航系统以及计算 机网络等高级系统中的一个典型应用通常需要考 虑以下几个方面：第一网络规模庞大节点数量较 多；第二路径搜索频繁；第三需要近乎实时的相应 速度．如果系统是应用在移动设备上还需要考虑 设备的硬件资源（运算、存储等）有限等因素． 在众多的路径搜索算法中Dijkstra 算法提供了 从图的一个节点到另一个节点的最短路径．经过一 次 Dijkstra 算法计算可以得到从起点到图内被其 搜索到的所有节点的最短路径其时间复杂度为 o（ n 2）（其中 n 为图的节点数）．但是在实际应用 中所关心的是某两个特定节点之间的最短路径而 非起点到其他点的情况且在大规模网络中 Dijkstra 算法的时间复杂度较高使其应用受到限制．文 献［1］提出了利用堆数据结构来改善 Dijkstra 算法 的寻径速度但对 Dijkstra 算法的时间复杂度性能 提高有限．文献［2］提出了预先计算图中每对节点 之间的最短路径并存储在数据库中在实际应用时 根据起点和终点直接在数据库中查询的方法．该方 法的时间复杂度得到了很大程度的降低但是额外 存储空间开支较大．文献［3］根据文献［2］的思路 将数据库视图进行分层、编码以便于查询且减少存 储空间耗费．这种方法只适合静态图如果图的拓 扑结构发生变化则必须更新数据库和编码；而且对 于移动设备来说这种额外的存储空间开支使得本 就稀缺的存储资源显得更加捉襟见肘．文献［4］结 合地理信息系统的特点将起点和终点的地理信息 考虑到寻径算法的计算中在寻找两点之间路径的 最优而非最佳解时有较佳的表现；但为了尽量逼近 最佳解必须对图搜索两次． 为了解决大型应用系统中寻径问题且使算法 能较好地平衡最优性、时间复杂度以及空间复杂度 本文提出了一种启发式最优路径搜索算法（heuristic optimization pathfinding algorithmHOPA）即在寻 径过程中引入代价函数由代价函数来决定寻径策 略（即优先搜索哪些中间节点）以期望减少搜索节 点数从而降低其时间复杂度． 1 HOPA 算法 1∙1 启发式路径搜索（heuristic pathfindingHP） 定义1 寻径算法可应用的网络可以用定义来 G＝（ V E）描述其中 V ＝｛v｜vi＝〈xiyi〉｝E＝ ｛VR｝VR＝｛〈uv〉｜P（ uv ）∧（ uv ∈ V ）｝．V 为网络中的节点的有穷非空集合〈xiyi〉为节点 vi 的地理坐标VR 为网络中两个顶点之间的关系集 合P（ uv ）为从顶点 u 到顶点 v 一条边的权． Dijkstra 算法首先建立了一个集合 V′＝｛v｜vi ∈ V｝该集合初始化时只有一个元素即路径的起 始节点 vsV′为 V′的补集．其计算步骤为：在 V′中 找到所有与 V′直接相连的节点然后将这些节点中 与 V′之间具有最小权值的节点添加到 V′中如此 循环直到将终点 v e 添加到 V′中．Dijkstra 算法实 际上是宽度优先的搜索算法它对所有与 V′直接相 连节点采取同等对待策略因此导致了 Dijkstra 算 法为了找到最短路径需要搜索较多的节点时间复 杂度也就相应地较高当然这种平等对待的策略也 是该算法取得最佳解的保证． 第29卷 第3期 2007年 3月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．29No．3 Mar．2007 DOI:10．13374／j．issn1001－053x．2007．03．022
第3期 王景存等：一种基于Dijkstra算法的启发式最优路径搜索算法 347, 在Dijkstra算法中引入代价函数来描述新的策 略机制，即：在搜索前，先判断从哪些节点查找下去 的=ei+ogg+ 最有可能找到最佳路径， d(vi-l,vi）十dist min(vi,ve), 定义2设f(uj)=g(vg,vj)十h(uj,ve),其 又因为为最短路径的下一个节点，则有 中g(,)为从起始节点.经过寻径算法到达 d(1)+distmin(vv) 的权值之和，且g(v,v)=0,则称h(v,ve)为节 点v的代价函数，h(ve,ve)=0,它预测从；到终 d(u-1,g)+, de+）ta(er） 点ve的代价，f()的值决定该点是否能被优先 即 查找， f(vi)-fp(v.). 引入代价函数，就可以将均等式的宽度优先搜 即表明HP算法此时会放弃路径P,并最终会将： 索机制改进成有方向性的深度优先搜索机制，即启 添加到V”中去，证明完毕. 发式路径搜索(HP),描述如下： 不难看出，当f(vci)=g(v,vci),即h(vci, 集合V*={u*lu∈V,(i≠j)u≠u请f, ve)=O时，HP算法即为Dijkstra算法.当h(uci, V为V*的补集，V*初始状态只有一个起始节点 ve)≠0时，h(ui,v)越小，在决策中g(vci,v)所 ";V=ve l vei∈，H(i≠j)vei≠e}表示 起的作用越大；相反h(vei,v,)所起的作用越大， V*中所有与V直接连接的节点集合·算法的步 h(vi,v:)的引入使得寻径算法带有方向性，提高 骤大体为：首先在V。中查找心，使 了寻径效率.但h(vi,v)只是估计值，不一定能 f(vej)=minlf(vci),viEvel, 保证找到的路径就是最佳的；但可以选择恰当的代 然后将，从V。中删除并添加到V*中，最后再在 价函数，使找到的路径尽量逼近最佳解，同时又能降 集合V+V。中查找与直接相连的节点，并添 低整个算法的复杂度， 加到V。中去，重复以上步骤直到将终点v。被添 1.2代价函数选定 代价函数用以估计节点到终点的代价，代价函 加到集合V。中. 数的值越大，搜索所花费的时间越少，算法的解也就 定理1设有序序列V'={01,v2,,j 越偏离最佳解：代价函数的值越小，算法的解也就越 …,vn,ve}为通过HP找到的从起点u,到终点ve 逼近最优解，同时时间耗费也就越大，可见选取好 的路径，dist min(vk,vi)表示vk到vL最小权值之和， 的代价函数是问题解决的关键.本文以城市交通网 若满足 为例，说明选取代价函数的方法， (Hv)(h(vj,ve)≤distmin(vj,ve)A(vj∈V)), 在GIS系统中，城市道路构成的网络具有的最 则V为最短路径. 大特点是：节点间具有几何特性，两个相互连接的节 证明设V”={uu1,u2,…,w-1为最短路 点之间的权值几乎可以用两点间的几何距离来表 径的前i个节点组成的集合，：为该最短路径的下 征，另外，还需注意到城市交通网的规划都比较规 一个节点，从v-1到终点。有m条路径，其中一 整，道路分布多近似于垂直和水平分布， 条路径为 鉴于上述的网络结构，可选取代价函数： Pg=iui-1vg1,vg2…,ugr,e,q≤m 令1卡ui,Pg满足 h(vi:v.)=D (vi-vex)2+(v-vey)2(1) vi(f(i)<f()A(u∈v”), 式中，vx和v分别为节点：的横坐标和纵坐标， vex和vey分别为终点ve的横坐标和纵坐标，D为 则按照HP算法，必然会优先按照P。的方向按 放缩系数且D≥1.由定理1可知：当D=1时，能确 深度搜索下去.当算法搜索到终点v。时， 保在城市交通网络中找到最短路径， fp(ve)=gp(ve,v)+hp(ve;ve)=gp(ve,v.), 为了降低算法的复杂度也可以将式(1)近似为： 引入符号d(vk,v)表示边vk,v)的权，则 h(viv)=2Dmax(lvi-vex),(lv-vey) g(we,")=d(ua,i)十 2 d(vg:0g+1)+ 9 (2) 如此将不能保证得到的解一定为最佳解， d(vi-1:vg1)+2 d(voh v(h+)d(vorve). h 图1形象地展现了一个典型的城市交通网的网 而 络结构.从v:到ve的最佳路径最有可能是沿着箭
在 Dijkstra 算法中引入代价函数来描述新的策 略机制即：在搜索前先判断从哪些节点查找下去 最有可能找到最佳路径． 定义2 设 f （ vj）＝ g（ vsvj）＋ h（ vjv e）其 中 g（ vsvj）为从起始节点 vs 经过寻径算法到达 vj 的权值之和且 g（ vsvs）＝0则称 h（ vjv e）为节 点 vj 的代价函数h（ v ev e）＝0它预测从 vj 到终 点 v e 的代价f （ vj ）的值决定该点是否能被优先 查找． 引入代价函数就可以将均等式的宽度优先搜 索机制改进成有方向性的深度优先搜索机制即启 发式路径搜索（HP）描述如下： 集合 V ∗＝｛v ∗｜v ∗ i ∈ V ∀（ i≠ j） v ∗ i ≠ v ∗ j ｝ V ∗为 V ∗的补集V ∗初始状态只有一个起始节点 vs；V ∗ c ＝｛v ∗ c ｜v ∗ c i ∈ V ∀（ i≠ j ） v ∗ c i ≠ v ∗ c j｝表示 V ∗中所有与 V ∗直接连接的节点集合．算法的步 骤大体为：首先在 V ∗ c 中查找 v ∗ c j 使 f （ v ∗ c j ）＝min i ｛f （ v ∗ c i ）v ∗ c i∈ V ∗ c ｝ 然后将 v ∗ c j 从 V ∗ c 中删除并添加到 V ∗中最后再在 集合 V ∗＋ V ∗ c 中查找与 v ∗ c j 直接相连的节点并添 加到 V ∗ c 中去重复以上步骤直到将终点 v e 被添 加到集合 V ∗ c 中． 定理1 设有序序列 V′＝｛vsv1v2…vj …v nv e｝为通过 HP 找到的从起点 vs 到终点 v e 的路径distmin（ v kvl）表示 v k 到 vl 最小权值之和 若满足 （∀vj）（（ h（ vjv e）≤distmin（ vjv e））∧（ vj∈ V′）） 则 V′为最短路径． 证明 设 V″＝｛vsv′1v′2…v′i－1｝为最短路 径的前 i 个节点组成的集合v′i 为该最短路径的下 一个节点．从 v′i－1到终点 v e 有 m 条路径其中一 条路径为 Pq＝｛v′i－1v′q1v′q2…v′qrv e｝q≤ m； 令 v′p1≠v′iPq 满足 ∀v′pi（ f （ v′pi）＜ f （ v′i）∧（ v′pi∈ V″）） 则按照 HP 算法必然会优先按照 Pq 的方向按 深度搜索下去．当算法搜索到终点 v e 时 f p（ v e）＝gp（ v evs）＋hp（ v ev e）＝gp（ v evs） 引入符号 d（ v kvl）表示边〈v kvl〉的权则 g（ v evs）＝ d（ vsv′1）＋ ∑ i－2 g＝1 d（ v′gv′g＋1）＋ d（ v′i－1v′q1）＋ ∑ r－1 h d（ v′qhv′q（ h＋1）＋ d（ v′qrv e）． 而 f （ v′i）＝ d（ vsv′1）＋ ∑ i－2 g＝1 d（ v′gv′g＋1）＋ d（ v′i－1v′i）＋distmin（ v′iv e） 又因为 v′i 为最短路径的下一个节点则有 d（ v′i－1v′i）＋distmin（ v′iv e）＜ d（ v′i－1v′q1）＋ ∑ r－1 h d（ v′qhv′q（ h＋1））＋ d（ v′qrv e） 即 f （ v′i）＜ f p（ v e）． 即表明 HP 算法此时会放弃路径 Pq并最终会将 v′i 添加到 V″中去．证明完毕． 不难看出当 f （ v ∗ c i ）＝ g （ vsv ∗ c i ）即 h（ v ∗ c i v e）＝0时HP 算法即为 Dijkstra 算法．当 h（ v ∗ c i v e）≠0时h（ v ∗ c ivs）越小在决策中 g（ v ∗ c ivs）所 起的作用越大；相反 h（ v ∗ c ivs）所起的作用越大． h（ v ∗ c ivs）的引入使得寻径算法带有方向性提高 了寻径效率．但 h（ v ∗ c ivs）只是估计值不一定能 保证找到的路径就是最佳的；但可以选择恰当的代 价函数使找到的路径尽量逼近最佳解同时又能降 低整个算法的复杂度． 1∙2 代价函数选定 代价函数用以估计节点到终点的代价．代价函 数的值越大搜索所花费的时间越少算法的解也就 越偏离最佳解；代价函数的值越小算法的解也就越 逼近最优解同时时间耗费也就越大．可见选取好 的代价函数是问题解决的关键．本文以城市交通网 为例说明选取代价函数的方法． 在 GIS 系统中城市道路构成的网络具有的最 大特点是：节点间具有几何特性两个相互连接的节 点之间的权值几乎可以用两点间的几何距离来表 征．另外还需注意到城市交通网的规划都比较规 整道路分布多近似于垂直和水平分布． 鉴于上述的网络结构可选取代价函数： h（ vivs）＝ D （ vix－v e x） 2＋（ viy－v e y） 2 （1） 式中vix 和 viy分别为节点 vi 的横坐标和纵坐标 v e x和 v e y 分别为终点 v e 的横坐标和纵坐标D 为 放缩系数且 D≥1．由定理1可知：当 D＝1时能确 保在城市交通网络中找到最短路径． 为了降低算法的复杂度也可以将式（1）近似为： h（ viv e）＝ 2Dmax｛（｜vix－v e x｜）（｜viy－v e y｜）｝ （2） 如此将不能保证得到的解一定为最佳解． 图1形象地展现了一个典型的城市交通网的网 络结构．从 vi 到 v e 的最佳路径最有可能是沿着箭 第3期 王景存等： 一种基于 Dijkstra 算法的启发式最优路径搜索算法 ·347·
.348 北京科技大学学报 第29卷 头方向行走，将代价函数设为 插入到K中，其具体步骤为：首先将k插入到K的 h(vi,ve)=D(lvi-vex+lv8-veyl)(3) 尾端，即k在K中的下标为n十1；然后比较k与 又|x-ver|+|vy-vey|> (+1)/%,如果k较小，则交换这两个元素，此时k J(vx一ve)2+(v一uey)2,所以亦不能保证解的 的新下标为i?(n+1)/2;接下来再比较k与 最佳 3·如此循环直到比较过程中k较大，或k已经 移到K的首部，如果要将k1从K中删除，其具体 步骤为：首先将k1从K中删除，然后将kn移到K 的首部，则kn的新下标为1；接下来比较kn与 k2×1,k2x1+1,如果kn<min(k2×1,k2x1+1)则交换 kw,min(k2x1,k2x1+1),设km的新下标为i:如果此 时kn<min(k2×,k2x+1)则交换kn,min(k2×i, k2×+1)·如此循环直到比较过程中km为三者中最 大，或km无元素可比较（即2i>n一1） 图1城市交通网示意图 通过对堆的插入和删除过程的分析可知：在一 Fig.1 Conventional diagram of urban traffic network 个二叉堆序列插入一个元素或删除第一个元素需比 代价函数也可以根据具体情况设置成其他形 较的次数bm次，当n足够大时，采用二叉堆比 式，但只要能保证解的最优，就能将P算法优化成 其他数据结构能大大加快查找速度；但在元素个数 HOPA算法， 较小的情况下效果不太明显，对于网络规模较大， 1.3HOPA算法改进 节点数量较多的场合（节点数>103），使用二叉堆对 对HOPA算法的分析可知，HOPA算法将均等 加快寻径算法的速度有举足轻重的作用， 的宽度搜索改进成有策略的深度搜索，可有效地减 2实验验证 少被搜索的节点数（当然，在最坏情况下，还是有遍 历图的所有节点的可能)，从而节省搜索时间，但是 2.1搜索区域比较 如果网络的规模庞大，在V。中找到能满足 建立一个理想网络，即图中所有节点在二维平 f(ve=minf(vei),ve:∈V。}的节点的时间耗费 面内均匀分布，图中的任意一条边的权值相同，所有 的边都按水平方向或垂直方向分布，来模拟一个城 也是不容忽视的，为了缩短HOPA算法的搜索时 间，本文将二叉堆6]引入到对集合V。的查找过 市交通网，虽然这种棋盘分布的理想网络并不能完 全客观地反映实际情况，但可直观地、简略地说明 程中， 定义3对于集合K={k1,k2,,kn{,若其所 H0PA算法（代价函数取式(1），(2)或(3)结果大致 相同，只将选取式(3)的情况列举了出来)与Dijkstra 有元素满足 算法相比其降低被搜索节点数的程度，以及这两种 k:≤k2i ,=1,2,… 算法的搜索空间分布（图2中实心点表示被搜索过 k:≤k2+ 的节点，粗线表示最终路径) 则称该集合为二叉堆 通过图2可以看出，Dijkstra算法的均等宽度优 如果集合 先的搜索策略导致其搜索区域是以起点为中心，呈 F=Iflfi=f(vci,v)AV vei(viE ve) 放射状蔓延到终点，而HOPA算法的搜索区域基本 满足定义3，则 上分布在最终路径的两侧，从而使搜索的节点数大 f(vel)-minif(vci),vcie ve 幅度减少（在实际情况下，HOPA算法的效果虽不会 成立·此时查找最小∫时不用在V。中查找，而只 如此显著，但还是在很大程度上减少搜索的节点 需将其第一个元素取出即可 数)·虽然两种算法得到的解不同，但HOPA算法得 要保证一个集合满足二叉堆，主要体现在对这 到的路径的权值和与Dijkstra算法相同，也就是说 个集合添加元素和删除元素的操作上，设集合K= HOPA算法的解也是最佳解 {k1,2,,kn}是一个二叉堆，现有一元素k需要
头方向行走将代价函数设为： h（ viv e）＝ D（｜vix－v e x｜＋｜viy－v e y｜） （3） 又 ｜ vix － v e x ｜ ＋ ｜ viy － v e y ｜ ＞ （ vix－v e x） 2＋（ viy－v e y） 2所以亦不能保证解的 最佳． 图1 城市交通网示意图 Fig．1 Conventional diagram of urban traffic network 代价函数也可以根据具体情况设置成其他形 式但只要能保证解的最优就能将 HP 算法优化成 HOPA 算法． 1∙3 HOPA 算法改进 对 HOPA 算法的分析可知HOPA 算法将均等 的宽度搜索改进成有策略的深度搜索可有效地减 少被搜索的节点数（当然在最坏情况下还是有遍 历图的所有节点的可能）从而节省搜索时间．但是 如果 网 络 的 规 模 庞 大在 V ∗ c 中 找 到 能 满 足 f （ v ∗ c j ＝min i ｛f （ v ∗ c i ）v ∗ c i ∈ V ∗ c ｝的节点的时间耗费 也是不容忽视的．为了缩短 HOPA 算法的搜索时 间本文将二叉堆［6］ 引入到对集合 V ∗ c 的查找过 程中． 定义3 对于集合 K＝｛k1k2…kn｝若其所 有元素满足 ki≤k2i ki≤k2i＋1 i＝12… n 2 则称该集合为二叉堆． 如果集合 F＝｛f｜f i＝ f （ v ∗ c iv e）∧∀v ∗ c i （ v ∗ c i∈ V ∗ c ）｝ 满足定义3则 f （ v ∗ c1）＝min i ｛f （ v ∗ c i ）v ∗ c i∈ V ∗ c ｝ 成立．此时查找最小 f 时不用在 V ∗ c 中查找而只 需将其第一个元素取出即可． 要保证一个集合满足二叉堆主要体现在对这 个集合添加元素和删除元素的操作上．设集合 K＝ ｛k1k2…kn｝是一个二叉堆现有一元素 k 需要 插入到 K 中其具体步骤为：首先将 k 插入到 K 的 尾端即 k 在 K 中的下标为 n＋1；然后比较 k 与 k? （ n＋1）／2」如果 k 较小则交换这两个元素此时 k 的新下标为 i＝? （ n＋1）／2」；接下来再比较 k 与 k? i／2」．如此循环直到比较过程中 k 较大或 k 已经 移到 K 的首部．如果要将 k1 从 K 中删除其具体 步骤为：首先将 k1 从 K 中删除然后将 kn 移到 K 的首部则 kn 的新下标为1；接下来比较 kn 与 k2×1k2×1＋1如果 kn＜min（ k2×1k2×1＋1）则交换 knmin（ k2×1k2×1＋1）设 kn 的新下标为 i；如果此 时 kn ＜min （ k2× ik2× i＋1）则交换 knmin （ k2× i k2× i＋1）．如此循环直到比较过程中 kn 为三者中最 大或 kn 无元素可比较（即2i＞ n－1）． 通过对堆的插入和删除过程的分析可知：在一 个二叉堆序列插入一个元素或删除第一个元素需比 较的次数≤? lb n」次当 n 足够大时采用二叉堆比 其他数据结构能大大加快查找速度；但在元素个数 较小的情况下效果不太明显．对于网络规模较大 节点数量较多的场合（节点数＞103）使用二叉堆对 加快寻径算法的速度有举足轻重的作用． 2 实验验证 2∙1 搜索区域比较 建立一个理想网络即图中所有节点在二维平 面内均匀分布图中的任意一条边的权值相同所有 的边都按水平方向或垂直方向分布来模拟一个城 市交通网．虽然这种棋盘分布的理想网络并不能完 全客观地反映实际情况但可直观地、简略地说明 HOPA 算法（代价函数取式（1）（2）或（3）结果大致 相同只将选取式（3）的情况列举了出来）与 Dijkstra 算法相比其降低被搜索节点数的程度以及这两种 算法的搜索空间分布（图2中实心点表示被搜索过 的节点粗线表示最终路径）． 通过图2可以看出Dijkstra 算法的均等宽度优 先的搜索策略导致其搜索区域是以起点为中心呈 放射状蔓延到终点而 HOPA 算法的搜索区域基本 上分布在最终路径的两侧从而使搜索的节点数大 幅度减少（在实际情况下HOPA 算法的效果虽不会 如此显著但还是在很大程度上减少搜索的节点 数）．虽然两种算法得到的解不同但 HOPA 算法得 到的路径的权值和与 Dijkstra 算法相同也就是说 HOPA 算法的解也是最佳解． ·348· 北 京 科 技 大 学 学 报 第29卷
第3期 王景存等：一种基于Dijkstra算法的启发式最优路径搜索算法 ·349 6 图2 Dijkstra算法(a)和HOPA算法(b)搜索区域分布 Fig.2 Searching area distribution of Dijkstra (a)and HOPA algorithm (b) 2.2实际情况实验数据对比 3 采用某城市5km×5km的一块区域内的城市 结论 交通网作为验证网络，其网络规模为：2008个节点， 本文提出的HOPA算法，其主要思想是借助AI 3167条边；实验平台：P42.6G,1GDDR.表1中的 的决策机制，将每个节点到达终点的代价估计引入 每组数据是随机抽取2O08对点进行运算后得 到算法中来，将传统的均等式宽度优先搜索机制改 出的 进成带有方向性的深度优先搜索机制，以减少搜索 表1实验数据 的节点数，为了进一步减少搜索时间，在搜索过程 Table 1 Test data 中采用二叉堆这一数据结构，随后的实验证明了本 使用 总耗费 平均每次 与最短 文中的定义和结论的正确性，以及该算法在实际应 烫 代价 放缩 二叉 时间/ 寻径耗费 路径切 用中的优越性， 法 函数 堆 系数 ms 时间/ms合度 1 13532 6.74 94.28% 参考文献 否 2 12703 6.33 78.70% [I】唐文武，施晓东，朱大奎.GIS中使用改进的Dkta算法实现 最短路径的计算.中国图像图形学报，2000,5A(12):1019 3 12375 6.16 40.13% 式(3) [2] Agrawal R.Jagadish H V.Materialization and incremental update 1 9969 4.96 94.28% of path information//Proceedings of the 5th International Confer- 是 2 9609 4.79 78.70% ence on Data Engineering.Los Angeles,1989:374 9228 4.60 40.13% [3]吴京，景宁，陈宏盛。最佳路径的层次编码及查询算法，计算 HOPA 1 14359 7.15 100% 机学报，2000,23(2)：184 [4]严寒冰，刘迎春.基于GIS的城市道路网最短路径算法探讨 213063 6.51 89.68% 计算机学报，2000,23(2)：210 312735 6.34 81.17% 式(1) [5]Aleksandrow J.Matheshwari A.Sack J R.Approximation algo 1 11312 5.63 100% rithms for geometrie shortest path problems//Proceedings of the 是 2 10516 5.24 89.687% Thirty second Annual ACM Symposium on Theory of Computing 3 10250 5.10 81.17% 2000.Portland,2000:286 [6]Elkin M.Computing almost shortest paths//Annual ACM Sym Dijkstra 68921 34.32 100可% posium on Principles of Distributed Computing Newport.2001:53 [7]Jacob R,Marathe M.Nagel K.A computational study of routing 由表1可以看出：Dijkstra算法每次寻径耗费的 algorithms for realistic transportation networks/2nd Workshop 时间为35ms左右：而HOPA算法在能确保所有解 on Algorithm Engineering.Saarbrucken.1998:168 为最佳的情况下，耗费的时间也不超过8ms,效率提 [8]Imielinski T.Julio C N.GPS-based Geographie Addressing 高近4倍多.随着D值的增加，时间耗费能进一步 Routing and Resource Discovery.New York:ACM Press,1999 [9]毕军，付梦印，周培德，等.基于城市道路网的快速路径寻优算 减少，但不能保证所有解都为最佳，其中代价函数采 法.计算机工程，2002,28(12)：36 取式(2)其准确率随D值增加降低较快.通过表1 [10]谭国真，高文.时间依赖的网络中最小时间路径算法，计算 亦可看出，使用二叉堆能进一步提高算法效率. 机学报，2002,25(2)：165
图2 Dijkstra 算法（a）和 HOPA 算法（b）搜索区域分布 Fig．2 Searching area distribution of Dijkstra （a） and HOPA algorithm （b） 2∙2 实际情况实验数据对比 采用某城市5km×5km 的一块区域内的城市 交通网作为验证网络其网络规模为：2008个节点 3167条边；实验平台：P42∙6G1G DDR．表1中的 每组数据是随机抽取 2008 对点进行运算后得 出的． 表1 实验数据 Table1 Test data 算 法 代价 函数 使用 二叉 堆 放缩 系数 总耗费 时间／ ms 平均每次 寻径耗费 时间／ms 与最短 路径切 合度 1 13532 6∙74 94∙28％ 否 2 12703 6∙33 78∙70％ 式（3） 3 12375 6∙16 40∙13％ 1 9969 4∙96 94∙28％ 是 2 9609 4∙79 78∙70％ HOPA 3 9228 4∙60 40∙13％ 1 14359 7∙15 100％ 否 2 13063 6∙51 89∙68％ 式（1） 3 12735 6∙34 81∙17％ 1 11312 5∙63 100％ 是 2 10516 5∙24 89∙68％ 3 10250 5∙10 81∙17％ Dijkstra － － － 68921 34∙32 100％ 由表1可以看出：Dijkstra 算法每次寻径耗费的 时间为35ms 左右；而 HOPA 算法在能确保所有解 为最佳的情况下耗费的时间也不超过8ms效率提 高近4倍多．随着 D 值的增加时间耗费能进一步 减少但不能保证所有解都为最佳其中代价函数采 取式（2）其准确率随 D 值增加降低较快．通过表1 亦可看出使用二叉堆能进一步提高算法效率． 3 结论 本文提出的 HOPA 算法其主要思想是借助 AI 的决策机制将每个节点到达终点的代价估计引入 到算法中来将传统的均等式宽度优先搜索机制改 进成带有方向性的深度优先搜索机制以减少搜索 的节点数．为了进一步减少搜索时间在搜索过程 中采用二叉堆这一数据结构．随后的实验证明了本 文中的定义和结论的正确性以及该算法在实际应 用中的优越性． 参 考 文 献 ［1］ 唐文武施晓东朱大奎．GIS 中使用改进的 Dijkstra 算法实现 最短路径的计算．中国图像图形学报20005A （12）：1019 ［2］ Agrawal RJagadish H V．Materialization and incremental update of path information∥Proceedings of the5th International Conference on Data Engineering．Los Angeles1989：374 ［3］ 吴京景宁陈宏盛．最佳路径的层次编码及查询算法．计算 机学报200023（2）：184 ［4］ 严寒冰刘迎春．基于 GIS 的城市道路网最短路径算法探讨． 计算机学报200023（2）：210 ［5］ Aleksandrow JMatheshwari ASack J R．Approximation algorithms for geometric shortest path problems∥Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing 2000．Portland2000：286 ［6］ Elkin M．Computing almost shortest paths∥Annual ACM Symposium on Principles of Distributed Computing．Newport2001：53 ［7］ Jacob RMarathe MNagel K．A computational study of routing algorithms for realistic transportation networks∥2nd Workshop on Algorithm Engineering．Saarbrucken1998：168 ［8］ Imielinski TJulio C N．GPS-based Geographic Addressing Routing and Resource Discovery．New York：ACM Press1999 ［9］ 毕军付梦印周培德等．基于城市道路网的快速路径寻优算 法．计算机工程200228（12）：36 ［10］ 谭国真高文．时间依赖的网络中最小时间路径算法．计算 机学报200225（2）：165 第3期 王景存等： 一种基于 Dijkstra 算法的启发式最优路径搜索算法 ·349·
.350 北京科技大学学报 第29卷 A heuristic optimization path finding algorithm based on Dijkstra algorithm WANG Jingeun2),ZHA NG Xicotong),CHEN Bin2),CHEN Heping?) 1)Information Engineering School.University of Science and Technology Beijing.Beijing 100083.China 2)Information Engineering School.Wuhan University of Science and Technology.Wuhan 430081.China ABSTRACT To make an efficient path finding engine,a heuristic optimization path finding algorithm was pro- posed for resolving the time and space complexity problems of a searching algorithm in a large application sys- tem.The algorithm was based on the classical Dijkstra algorithm and introduced the decision mechanism in Al into path -finding.To decrease the number of nodes to search,cost function was incorporated into this algorithm and used to decide the path finding policy,that was,which nodes were searched firstly.The condition of get- ting the optimal solution from this algorithm was put forward and proved.These two algorithms were tested comparatively. KEY WORDS path finding:navigation;heuristic:optimization (上接第324页) Basic study of modern blast furnace using natural lump ores rationally WU Shengli),XU Haifa),WANG Guojun2),LI Zhaoyi2),TIAN Yungin),CHEN Hui) 1)Metallurgical and Ecological Engineering School.University of Science and Technology Beijing.Beijing 100083.China 2)Iron making Plant.Shanghai Baosteel Co.(Group).Shanghai 200941,China ABSTRACI The fact that the metallurgical properties of natural lump ores were not insufficiently comprehen- sive and thorough grasped is obstructing the technology development of using lump ores in a modern blast fur- nace.Through analyzing and inspecting each metallurgical property of natural lump ores from main habitats in the world by experiment,the article indicates that the lump ores metallurgical properties can meet a modern blast-furnace except the softening and melting properties.And the interaction between the sinter and the lump ores was found in the high temperature zone of the blast furnace,which can obviously improve the softening and melting properties of the lump ores.The blast burden structure also can be optimized by the interaction. KEY WORDS blast furnace:natural lump ore;metallurgical property;high temperature interaction
A heuristic optimization path-finding algorithm based on Dijkstra algorithm WA NG Jingcun 1）2）ZHA NG Xiaotong 1）CHEN Bin 2）CHEN Heping 2） 1） Information Engineering SchoolUniversity of Science and Technology BeijingBeijing100083China 2） Information Engineering SchoolWuhan University of Science and TechnologyWuhan430081China ABSTRACT To make an efficient path-finding enginea heuristic optimization path-finding algorithm was proposed for resolving the time and space complexity problems of a searching algorithm in a large application system．The algorithm was based on the classical Dijkstra algorithm and introduced the decision mechanism in AI into path-finding．To decrease the number of nodes to searchcost-function was incorporated into this algorithm and used to decide the path-finding policythat waswhich nodes were searched firstly．The condition of getting the optimal solution from this algorithm was put forward and proved．These two algorithms were tested comparatively． KEY WORDS path-finding；navigation；heuristic；optimization （上接第324页） Basic study of modern blast furnace using natural lump ores rationally W U Shengli 1）XU Haif a 1）WA NG Guojun 2）LI Zhaoyi 2）TIA N Y unqin 1）CHEN Hui 1） 1） Metallurgical and Ecological Engineering SchoolUniversity of Science and Technology BeijingBeijing100083China 2） Iron-making PlantShanghai Baosteel Co．（Group）Shanghai200941China ABSTRACT The fact that the metallurgical properties of natural lump ores were not insufficiently comprehensive and thorough grasped is obstructing the technology development of using lump ores in a modern blast furnace．Through analyzing and inspecting each metallurgical property of natural lump ores from main habitats in the world by experimentthe article indicates that the lump ores’metallurgical properties can meet a modern blast-furnace except the softening and melting properties．And the interaction between the sinter and the lump ores was found in the high temperature zone of the blast furnacewhich can obviously improve the softening and melting properties of the lump ores．The blast burden structure also can be optimized by the interaction． KEY WORDS blast furnace；natural lump ore；metallurgical property；high-temperature interaction ·350· 北 京 科 技 大 学 学 报 第29卷