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