路网寻径中的A星算法改进

摘要

随着经济的发展，城市的地理信息数据呈爆炸式增长且城市路网的结构也变得日益复杂。能否从复杂的城市路网中几乎实时地找出从出发地到日的地的最短路线越发受到老百姓的关注。A星算法作为一种经典的启发式寻路算法，广泛用于城市交通寻路。随着时代的前进，多种改进A星算法已被人们提出。其中以二叉堆存储结构代替传统OPEN表的线性存储结构的改进令人瞩目，虽效率提升明显但逐渐难以满足用户需求。本文在此背景下对上述算法展开了研究。
　　本文首先对图和图搜索算法相关知识进行了叙述，着重介绍本文研究对象----A星算法，对其进行分析并指出其瓶颈。接着简单介绍了已被人提出的A星算法改进方案。基于对上述改进方案的研究并结合较为成熟多核多线程技术，本文提出了两种算法改进方案。第一种方案是节点并行扩展及OPEN表分治并行查找最小代价值节点。该方案让节点扩展时可以在邻接节点代价值计算、节点是否在OPEN表和CLOSE表中等耗时读操作上由多个子线程并行进行，而OPEN表添加节点或更改节点代价值、CLOSE表添加节点等写操作由主线程串行进行。同时，为了减少查找OPEN表中最小代价值节点的时间，基于“分治”思想，提出将OPEN表分成多个节点更少的表，由多线程并行实现二叉堆存储，每个线程找出单个表的最小代价值节点后交由主线程得出全局的最小代价值节点。另一种方案是双向并行运行寻径。该方案提出开启两个线程同时分别从起始节点和目标节点分别朝对方寻径，两个线程各独自拥有OPEN表但共用一个CLOSE表且对此表进行同步处理，当其中一个线程从其独自拥有的OPEN表中找到的最小值节点放入CLOSE表中时，若发现该节点已存在于CLOSE表中并被另一个线程标记，表明路径已经找到。经分析，此算法只适用于两节点间的最短路径只存在一条或多条但多条路径间有重合节点。最后，实验表明在路网较为复杂、起始节点和目标节点距离较远时，两种改进方案有着良好的性能。

目录

声明

摘要

第一章 绪论

1．1 研究背景

1．2 研究现状与发展趋势

1．3 论文结构

第二章 图搜索算法

2．1 图搜索

2．1．1 图与图存储

2．1．2 图的一般搜索过程

2．1．3 盲目式搜索算法

2．1．4 启发式搜索算法

2．2 A星算法

2．2．1 A星算法概述

2．2．2 A星算法的估价函数

2．2．3 A星算法的寻径流程

2．3 本章小结

第三章 改进A星算法

3．1 传统A星算法存在的瓶颈

3．2 已提出的A星算法改进

3．2．1 OPEN表的优化

3．2．2 估价函数的改进

3．3 A星算法的并行化改进

3．3．1 多核CPU上的多线程

3．3．2 节点扩展及查找最小代价值节点并行

3．3．3 双向寻径并行

3．4 本章小结

第四章 实验与结果分析

4．1 编程语言与实验平台

4．1．1 编程语言的选择

4．1．2 实验平台

4．2 实验数据

4．2．1 实验数据的生成

4．2．2 实验数据的预处理和存储

4．3 实验过程

4．4 实验结果及分析

4．4．1 A星-β算法实验结果及分析

4．4．2 A星-γ算法实验结果及分析

4．4．3 实验综合分析

4．5 本章小结

第五章 总结与展望

5．1 全文总结

5．2 未来工作展望

参考文献

在校期间科研成果和参加的科研项目

致谢