一种基于Dijkstra算法的启发式最优路径搜索算法
第29卷第3期2007年3月北京科技大学学报
JournalofUniversityofScienceandTechnologyBeijing
Vol.29No.3Mar.2007
一种基于Dijkstra算法的启发式最优路径搜索算法
王景存1,2) 张晓彤1) 陈 彬2) 陈和平2)
1)北京科技大学信息工程学院,北京100083 2)武汉科技大学信息科学与工程学院,武汉430081
摘 要 为了建立一个高效的路径搜索引擎,、题,从经典Dijkstra算法出发,将AI,.该算法在寻径过程中引入代价函数,由代价函数来决定寻径策略().到最佳解的条件及其证明过程,关键词 路径搜索;导航;启发式;最优分类号 TP30116
、导航系统以及计算机网络等高级系统中的一个典型应用,通常需要考
虑以下几个方面:第一,网络规模庞大,节点数量较多;第二,路径搜索频繁;第三,需要近乎实时的相应速度.如果系统是应用在移动设备上,还需要考虑设备的硬件资源(运算、存储等)有限等因素.
在众多的路径搜索算法中,Dijkstra算法提供了从图的一个节点到另一个节点的最短路径.经过一次Dijkstra算法计算,可以得到从起点到图内被其搜索到的所有节点的最短路径,其时间复杂度为
2
o(n)(其中n为图的节点数).但是在实际应用中,所关心的是某两个特定节点之间的最短路径而非起点到其他点的情况,且在大规模网络中Dijkstra算法的时间复杂度较高,使其应用受到限制.文献[1]提出了利用堆数据结构来改善Dijkstra算法的寻径速度,但对Dijkstra算法的时间复杂度性能提高有限.文献[2]提出了预先计算图中每对节点之间的最短路径并存储在数据库中,在实际应用时,根据起点和终点直接在数据库中查询的方法.该方法的时间复杂度得到了很大程度的降低,但是额外存储空间开支较大.文献[3]根据文献[2]的思路,将数据库视图进行分层、编码以便于查询且减少存储空间耗费.这种方法只适合静态图,如果图的拓扑结构发生变化,则必须更新数据库和编码;而且对于移动设备来说,这种额外的存储空间开支使得本就稀缺的存储资源显得更加捉襟见肘.文献[4]结合地理信息系统的特点,将起点和终点的地理信息
收稿日期:20060405 修回日期:200610基金项目:中国科学院计算所知识创新工程“HPC-OG模拟系统及相关技术”研究项目(No.20036040)
),男,副教授,博士研究生作者简介:王景存(1963—
考虑到寻径算法的计算中,在寻找两点之间路径的最优而非最佳解时有较佳的表现;但为了尽量逼近最佳解,必须对图搜索两次.
为了解决大型应用系统中寻径问题,且使算法能较好地平衡最优性、时间复杂度以及空间复杂度,
本文提出了一种启发式最优路径搜索算法(heuristicoptimizationpathfindingalgorithm,HOPA),即在寻径过程中引入代价函数,由代价函数来决定寻径策略(即优先搜索哪些中间节点),以期望减少搜索节点数,从而降低其时间复杂度.
1 HOPA算法
111 启发式路径搜索(heuristicpathfinding,HP)
定义1 寻径算法可应用的网络可以用定义来
G=(V,E)描述,其中V={v|vi=〈xi,yi〉},E={VR},VR={〈u,v〉|P(u,v)∧(u,v∈V)}.V
为网络中的节点的有穷非空集合〈,xi,yi〉为节点vi的地理坐标,VR为网络中两个顶点之间的关系集合,P(u,v)为从顶点u到顶点v一条边的权.
Dijkstra算法首先建立了一个集合V′={v|vi
∈V},该集合初始化时只有一个元素,即路径的起始节点vs,V′为V′的补集.其计算步骤为:在V′中找到所有与V′直接相连的节点,然后将这些节点中与V′之间具有最小权值的节点添加到V′中,如此循环直到将终点ve添加到V′中.Dijkstra算法实际上是宽度优先的搜索算法,它对所有与V′直接相连节点采取同等对待策略,因此导致了Dijkstra算法为了找到最短路径需要搜索较多的节点,时间复杂度也就相应地较高,当然这种平等对待的策略也是该算法取得最佳解的保证.
第3期王景存等:一种基于Dijkstra算法的启发式最优路径搜索算法
i-2
・347・
在Dijkstra算法中引入代价函数来描述新的策略机制,即:在搜索前,先判断从哪些节点查找下去最有可能找到最佳路径.
定义2 设f(vj)=g(vs,vj)+h(vj,ve),其中g(vs,vj)为从起始节点vs经过寻径算法到达vj的权值之和,且g(vs,vs)=0,则称h(vj,ve)为节点vj的代价函数,h(ve,ve)=0,它预测从vj到终点ve的代价,f(vj)的值决定该点是否能被优先查找.
引入代价函数,就可以将均等式的宽度优先搜索机制改进成有方向性的深度优先搜索机制,即启发式路径搜索(HP),描述如下:
集合V
V为V
333
3
3
f(v′i)=d(vs,v′1)+
g=1
,v′+1)+∑d(v′
g
g
d(v′i-1,v′i)+distmin(v′i,ve),
又因为v′i为最短路径的下一个节点,则有
d(v′i-1,v′i)+distmin(v′i,ve)
r-1
d(v′i-1,v′q1)+
∑d(v′,v′+1)+d(v′,ve),
qh
q(h
)
qr
h
即
f(v′i)
.
,当c3i)=g(vs,vc3i),即h(vc3i,
)时,HP算法即为Dijkstra算法.当h(vc3i,ve)≠0时,h(vc3i,vs)越小,在决策中g(vc3i,vs)所
={v3|vi3∈,≠j33
3
vs;Vc={vcciV,(ij)vci≠vcj}表示V中所有与V
起的作用越大;相反h(vc3i,vs)所起的作用越大.
h(vci,vs)的引入使得寻径算法带有方向性,提高
3
直接连接的节点集合.算法的步
骤大体为:首先在Vc3中查找vc3j,使
3333
f(vcj)=min{f(vci),vci∈Vc},
i
然后将vc3j从Vc3中删除并添加到V3中,最后再在集合V
3
+Vc3中查找与vc3j直接相连的节点,并添
加到Vc3中去,重复以上步骤直到将终点ve被添加到集合Vc3中.
定理1 设有序序列V′={vs,v1,v2,…,vj,…,vn,ve}为通过HP找到的从起点vs到终点ve的路径,distmin(vk,vl)表示vk到vl最小权值之和,若满足
(Πvj)((h(vj,ve)≤)),distmin(vj,ve))∧(vj∈V′则V′为最短路径.
证明 设V″={vs,v′1,v′2,…,v′i-1}为最短路径的前i个节点组成的集合,v′i为该最短路径的下一个节点.从v′i-1到终点ve有m条路径,其中一条路径为
Pq={v′i-1,v′q1,v′q2,…,v′qr,ve},q≤m;
了寻径效率.但h(vc3i,vs)只是估计值,不一定能
保证找到的路径就是最佳的;但可以选择恰当的代价函数,使找到的路径尽量逼近最佳解,同时又能降低整个算法的复杂度.112 代价函数选定代价函数用以估计节点到终点的代价.代价函数的值越大,搜索所花费的时间越少,算法的解也就越偏离最佳解;代价函数的值越小,算法的解也就越逼近最优解,同时时间耗费也就越大.可见选取好的代价函数是问题解决的关键.本文以城市交通网为例,说明选取代价函数的方法.
在GIS系统中,城市道路构成的网络具有的最大特点是:节点间具有几何特性,两个相互连接的节点之间的权值几乎可以用两点间的几何距离来表征.另外,还需注意到城市交通网的规划都比较规整,道路分布多近似于垂直和水平分布.
鉴于上述的网络结构,可选取代价函数:
h(vi,vs)=D
(vix-vex)2+(viy-vey)2(1)
令v′p1≠v′i,Pq满足
(v′)),Πv′pi(f(v′pi)
则按照HP算法,必然会优先按照Pq的方向按深度搜索下去.当算法搜索到终点ve时,
fp(ve)=gp(ve,vs)+hp(ve,ve)=gp(ve,vs),
式中,vix和viy分别为节点vi的横坐标和纵坐标,
vex和vey分别为终点ve的横坐标和纵坐标,D为放缩系数且D≥1.由定理1可知:当D=1时,能确保在城市交通网络中找到最短路径.
为了降低算法的复杂度也可以将式(1)近似为:
h(vi,ve)=Dmax{(|vix-vex|),(|viy-vey|)}
(2)
引入符号d(vk,vl)表示边的权,则〈vk,vl〉
i-2
g(ve,vs)=d(vs,v′1)+
r-1
g=1
,v′+1)+∑d(v′
g
g
q(h
)
d(v′i-1,v′q1)+
∑d(v′,v′+1
qh
h
+d(v′qr,ve).
而
如此将不能保证得到的解一定为最佳解.
图1形象地展现了一个典型的城市交通网的网络结构.从vi到ve的最佳路径最有可能是沿着箭
・348・
北 京 科 技 大 学 学 报第29卷
头方向行走,将代价函数设为:
h(vi,ve)=D(|vix-vex|+|viy-vey|)
又|最佳.
vix
(3)
-vex|+|viy-vey|>
插入到K中,其具体步骤为:首先将k插入到K的尾端,即k在K中的下标为n+1;然后比较k与k