启发式最短路径算法研究.doc资源-CSDN文库

版权申诉

文档资料

184 浏览量 2022-05-06 18:16:07 上传评论收藏 1.02MB DOC 举报

资源推荐

资源详情

资源评论

启发式最短路径算法研究

——以庐山路网寻径为例

摘要：最短路径算法的效率是GIS、智能交通系统等应用领域普遍关注和迫切

需要解决的问题。在深入分析经典的Dijkstra和启发式最短路径算法的基础上，

选取A*启发式最短路径算法，以庐山交通路网为数据基础，对A*算法和Dijkstra

算法进行了对比分析和测试。实验结果表明A*算法能够限制条件扩展节点,减少

算法遍历的节点数目, 降低执行时间,较经典Dijkstra算法具有更高的效率。在A*

启发性算法中，可以将启发函数h(n)看作是节点值估计的约束条件，如果h(n)包

含的信息越多或约束条件越多，则排除的节点就越多，估价函数f(n)越好。因此，

选择合适的估价函数对算法整体效率有很大影响。

关键词：Dijkstra A* 最短路径算法

Heurisc shortest path algorithm research --

an example of network roung on Lushan Mt.

Abstract: The efficiency of the shortest path algorithm is the widespread concern problem which

is urgent need to solve in GIS,intelligent transportation system and other application field . In

depth analysis of the classical Dijkstra and heuristic shortest path algorithm based on A*, this

paper selects heuristic shortest path algorithm in traffic network with Lushan Mt. for the data base,

and the A * algorithm and Dijkstra algorithm are analyzed and tested. The experimental results

show that A * algorithm can limit the conditions of extended node traversal algorithm, reduce the

number of nodes and the execution time, compared with the classical Dijkstra algorithm,A*

algorithm has higher efficiency. In A * heuristic algorithm, heuristic function h (n) can be regarded

as the node value estimate of the constraints, if h ( n ) contains more information or more

constraint conditions,algorithm excludes more nodes number and the evaluation function is

better.Therefore, choosing the appropriate valuation function on the whole algorithm efficiency

has a great influence.

Key words: Dijkstra ;A* ; shortest path algorithm

目录
第 1  章 绪论.........................................................................4
1 研究目的和意义............................................................................................................... 4
2 国内外研现状.................................................................................................................. 5
第 2  章 Dijkstra 和启发式最佳路径算法研究.............................7
1 图搜索算法和 Dijkstra 算法............................................................................................. 7
2 启发式算法...................................................................................................................... 8
3 A*算法.............................................................................................................................. 8
4 A*算法可接纳性.............................................................................................................. 9
4.1 A*算法的条件....................................................................................................... 9
4.2 定理 1................................................................................................................... 10
4.3 定理 2................................................................................................................... 12
4.4 一致性（或单调）条件......................................................................................13
4.5 定理 3................................................................................................................... 15
5 估价函数的选取............................................................................................................. 17
 第三章 实验环境和数据基础..................................................18
1 软件环境........................................................................................................................ 18
2 硬件环境........................................................................................................................ 18
3 实验数据........................................................................................................................ 18
第 4  章 关键技术.................................................................20
1 启发式函数.................................................................................................................... 20
2 数据预处理.................................................................................................................... 21
2.1 读取数据.............................................................................................................. 21
2.2 数据检查.............................................................................................................. 22
3 邻接表构建拓扑............................................................................................................. 22
4 排序算法................................................................................................................ 22
第 5  章 算法实现.................................................................24
1 实现流程图.................................................................................................................... 24
2 Dijkstra 和 A*算法的实现...............................................................................................25
第 6  章 结论与展望..............................................................29
1 结论................................................................................................................................ 29
2 展望................................................................................................................................ 29
参考文献...........................................................................30
致谢..................................................................................31
2