——以庐山路网寻径为例
摘 要：最短路径算法的效率是GIS、智能交通系统等应用领域普遍关注和迫切需要解决的问题。在深入分析经典的Dijkstra和启发式最短路径算法的基础上，选取A*启发式最短路径算法，以庐山交通路网为数据基础，对A*算法和Dijkstra算法进行了对比分析和测试。实验结果表明A*算法能够限制条件扩展节点,减少算法遍历的节点数目, 降低执行时间,较经典Dijkstra算法具有更高的效率。在A*启发性算法中，可以将启发函数h(n)看作是节点值估计的约束条件，如果h(n)包含的信息越多或约束条件越多，则排除的节点就越多，估价函数f(n)越好。因此，选择合适的估价函数对算法整体效率有很大影响。 关键词：Dijkstra A* 最短路径算法
Heuristic shortest path algorithm research -- an example of network routing on Mount Lu
Abstract: Shortest path algorithm efficiency is application areas such as attention and urgent needs to solve the problem in GIS, intelligent transportation system. In depth analysi
s of the classical Dijkstra and heuristic shortest path algorithm based on A*, selecting heuristic shortest path algorithm in traffic network on the A * algorithm and Dijkstra algorithm are analyzed and tested as Mount Lu for the data base. The experimental results show that A * algorithm can limit the conditions of extended node traversal algorithm, reduce the number of nodes, reduce the execution time, compared with the classical Dijkstra algorithm has higher efficiency. In A * heuristic algorithm, heuristic function h (n) can be as the node value estimate of the constraints, if h ( n ) contains more information or more constraint conditions, then excluding nodes number, evaluation function f ( n ) as possible.Therefore, choosing the appropriate valuation function on the whole algorithm efficiency has a great influence.
Key words: Dijkstra ;A* ; shortest path algorithm
目录
1.序论 3
1.1研究目的和意义 3
1.2国内外研现状 4
2. Dijkstra和启发式最短路径算法研究 6
2.2启发式算法 6
2.3A*算法 7
2.4A*算法可接纳性 8
2.4.1 A*算法的条件 8
2.4.2 定理1 9
2.4.3 定理2 11
2.4.4 一致性（或单调）条件 12
2.4.5 定理3 13
2.5估计函数的选取 15
3.实验环境和数据基础 16
3.1软件环境 16
3.2硬件环境 16
3.3实验数据 16
4．关键技术 17
4.1启发式函数： 17
4.2数据预处理 17
4.2.1读取数据 18
4.2.2数据检查 19
4.3邻接表构建拓扑 19
5．算法实现 21
5.1实现流程图 21
5.2 Dijkstra和A*算法的实现 21
6．结论与展望 26
6.1结论 26
6.2展望 26
7致谢 27
8.参考文献 28
1.序论
1.1研究目的和意义
随着计算机的普及以及地理信息科学的发展，地理信息系统(GocmetyrnIofmratinoSysetm，GIS)因其强大的功能得到日益广泛和深入的应用。网络分析作为GIS最主要的功能之一，在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用，而网络分析中最基本、最关键的问题是最短路径问题[1]。
在众多的路径搜索算法中, Dijkstra算法提供了从图的一个节点到另一个节点的最短路径。 经过一次Dijkstra算法计算, 可以得到从起点到图内被其搜索到的所有节点的最短路径, 其时间复杂度为o(n^2) ( 其中n 为图的节点数)。但是在实际应用中, 所关心的是某两个特定节点之间的最短路径而非起点到其他点的情况, 且在大规模网络中Dijkstra算法的时间复杂度较高, 使其应用受到限制。 Agrawal.R提出了利用堆数据结构来改善Dijkstra算法的寻径速度偷拍设备, 但对Dijkstra 算法的时间复杂度性能提高有限[2][3]。
经典的Dijkstra算法存在搜索空间过大导致效率低的问题。启发式最短路径算法通过启发
式方法实现剪枝效果，能够减少搜索空间，提高算法效率。启发式算法是相对于最优化算法提出的，启发式算法可以这样定义：
一个基于直观或经验构造的算法，在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定事先可以预计。
在这里启发式指的是在一个搜寻树的节点上定义的函数h(n)，用于评估从此节点到目标节点代价最低的路径。启发式算法通常用于信息充分的搜寻算法，典型的如最好优先贪婪算法与A*。最好优先贪婪算法会为启发式函数选择最低代价的节点；A*则会为g(n) + h(n)选择最低代价的节点，（g(n)是从起始节点到当前节点路径的实际代价）。如果h(n)是可接受的，意即h(n)未曾付出超过达到目标的代价，则A*一定会出最佳解。
启发式搜索就是在状态空间中对每一个搜索的位置进行评估，得到当前最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。
1.2国内外研现状
最短路径分析是根据网络的拓扑性质，求网络图数据结构中，从一个顶点出发到其他各顶点之间的最短路径，或求解每对顶点之间的最短路径。最短路径实质上是求加权后的最短路径。最短路径计算分静态最短路径计算和动态最短路径计算。目前基于地理信息系统的最短路径搜索算法研究很多，典型的如：
1.Dijkstra算法
2.A*算法
3.Bellman-Ford算法
4.SPFA算法 (Bellman-Ford算法的改进版本)
5.Floyd-Warshall算法
6.Johnson算法
7.Bi-Direction BFS算法
对于静态最短路径算法，1959 年Dijkstra提出的单源问题算法是最适合拓扑网络中两结点间最短路径搜索的算法之一, 本文将此算法称为“原始Dijkstra算法”,后人在此算法的基础上进行了大量的优化。P. E. Hart , N. J. Nilsson 和B. Raphael共同发表了一篇在启发式搜索方面有深远影响力的论文，在该论文中提出A*算法，论文指出，如果有已知信息可用来估计某一点到目标点的距离，则可用A*搜寻算法，以减小最短路径的搜索范围。Korf于1985年提出了一个IDA*( Iternative Deepening A*)算法，算法把深度最大值Dmax设为起始结点的h值，开始进行深度优先搜索，忽略所有f值大于Dmax的结点，减少了很多搜索量。如果没有解，再加大Dmax的值，直到到一个解。容易证明这个解一定是最优的。其他的启发式搜索这些方法包括深度优先+线型灯最优剪枝式的A*，双向A*，Korf在1993土豆切丝机年提出了递归最优搜索RBFS(方法比IDA*用到的存储稍微多一点，但是比IDA*产生的节点少。
动态路径最短路是外界环境不断发生变化，即不能计算预测的情况下计算最短路。卡内及梅隆机器人中心的Stentz在1994和1995年两篇文章提出D*算法（D-Star,Dynamic A*）。如在游戏中敌人或障碍物不断移动的情况下。最短路经算法现在重要的应用有计算机网络路由算法，机器人探路，交通路线导航，人工智能，游戏设计等等。美国火星探测器核心的寻路算法就是采用的D*（D Star）算法[4][5]。
2. Dijkstra和启发式最短路径算法研究
2.1 图搜索算法和Dijkstra算法
为了更准确地解释本章的启发式搜索过程，这里提出一个通用的图搜索算法，该算法允许启发式的或盲目的进行定制。本文把这个算法叫做图搜索算法。
图搜索算法：
无绳电熨斗
1) 生成一个仅包含开始节点n0的搜索树Tr。把n0放在一个称为OPEN的有序列表中。
2) 生成一个初始值为空的列表CLOSED。
3) 如果OPEN为空，则失败并退出。
4) 选出OPEN中的第一个节点，并将它从OPEN中移出，放入CLOSED中。称该节点为n。
5) 如果n重钙粉生产设备是目标节点，顺着Tr中的弧从n回溯到n0到一条路径，获得解决方案，则成功退
出（弧在第6步产生）。
6) 扩展节点n，生成n的后继节点集M。通过在Tr中建立从n到M中每个成员的弧生成n的后继。
7) 按照任意的模式或启发式方式对列表温玉理疗床OPEN重新排序。
8) 返回步骤3 。
这个算法可用来执行最优搜索、广度优先搜索或深度优先搜索。在广度优先搜索中，新节点只要放在OPEN的尾部即可（先进先出，FIFO），节点不用重排。在深度优先搜索中，新节f (n)= g(n)+ h(n)目标点放在OPEN的开始（后进先出，LIFO）。在最优（也叫启发式）搜索中，按照节点的启发式方式来重排OPEN[6]。
Dijkstra算法用广度优先搜索执行图搜索算法。
2.2启发式算法
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再
从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议