正在加载图片...
第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·