简要介绍资料的主要内容,以获得更多的关注

第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算法为了找到最短路径需要搜索较多的节点,时间复杂度也就相应地较高,当然这种平等对待的策略也是该算法取得最佳解的保证.
路网实验表明, 启发式搜索策略使遍历的结点数目明显减少, 有利于使搜索过程更加快速地趋于目标 结点. 1 传统 Dijkstra 算法 传统 Dijkst ra 算法是用逐点增长的...
路网实验表明 , 启发式搜索策略使遍历的结点数目明显减少 , 有利于使搜索过程更加快速地趋于目标 结点 . 1 传统 Dijkstra 算法 传统 Dijkst ra 算法是用逐点增长...
介绍了Dijkstra算法,在详细分析了该算法的实现方法以及其缺点的基础上,提出一种基于Dijkstra算法的优化算法一优先队列算法,在搜索最小的节点时,该算法的时间复杂度大...
毕业设计使用说明书-基于DIJKSTRA算法的最短路径搜索仿真_工学_高等教育_教育专区...A *算法是一个典型的人工智能启发式搜索算法,该算法的创新,是选择下一 个节点...
一种基于Dijkstra算法的... 5页 1下载券 车辆路径调度问题的启发... 11页 ...研 启发式路径搜索算法研 究综述 吕太 之。伟 李( 南京 理工大学,苏南京209...
2006 一种新的基于 Dijkstra 算法的 QoS 组播树启发式算法李秉智 , 李智 ( ...MCP_ IA 算法讨论了 2 个可 加性参数限制的路径搜索算法[ 4 ] 。 它利用...
启发式最短路径算法研究 ——以庐山路网寻径为例 摘要:最短路径算法的效率是...在众多的路径搜索算法中, Dijkstra算法提供了从图的一个节点到另一个节 点的...
Dijkstra最短路径算法的一种高效率实现_IT/计算机_专业资料。Dijkstra最短路径算法...3. 2 快速搜索技术的实现 无论何种算法, 一个基本思想都是将点按权 值的...
一种基于双向搜索的K则最优路径算法_专业资料。提出了一种基于双向搜索策略的K则最优路径算法,以改进的Dijkstra最优路径算法为基础,从起点和终点同时搜索,分别构造...
2 基于 Dijkst ra 算法的一种最短路径优化算法张福浩, 刘纪平, 李青元 ( 中国测绘科学研究院, 北京 100039) 摘要: 详细介绍了经典的 Dijkstra 算法, 举例说明...
热门文档