A*算法的改进及并行化

doi:10.11772/j.issn.1001-9081.2015.07.1843

计算机应用 ›› 2015, Vol. 35 ›› Issue (7): 1843-1848.DOI: 10.11772/j.issn.1001-9081.2015.07.1843

A^*算法的改进及并行化

熊壬浩¹, 刘羽²

1. 桂林理工大学信息科学与工程学院, 广西桂林 541006;
2. 桂林理工大学机械与控制工程学院, 广西桂林 541006

收稿日期:2015-01-27 修回日期:2015-03-25 出版日期:2015-07-10 发布日期:2015-07-17
通讯作者: 刘羽(1961-),男,广西桂林人,教授,博士,主要研究方向:并行计算、数据挖掘,lewis_5709@163.com
作者简介:熊壬浩(1987-),男,河南周口人,硕士研究生,主要研究方向:并行计算
基金资助:
国家自然科学基金资助项目(41264005)。

Improvement and parallelization of A^* algorithm

XIONG Renhao¹, LIU Yu²

1. College of Information Science and Engineering, Guilin University of Technology, Guilin Guangxi 541006, China;
2. College of Mechanical and Control Engineering, Guilin University of Technology, Guilin Guangxi 541006, China

Received:2015-01-27 Revised:2015-03-25 Online:2015-07-10 Published:2015-07-17

摘要/Abstract

摘要：

针对串行A^*算法时间性能较差的问题,提出了一种基于并行搜索和快速插入(PSFI)的算法。首先,研究了共享存储平台上的常见并行启发式搜索算法;然后,通过使用一种延迟的单表搜索(DSTS)方法和新的数据结构,改进了串行算法;其次,在此基础上,设计出一种基于共享存储平台的并行算法;最后,采用OpenMP加以实现。对24数码问题的测试结果表明,改进的串行和并行算法将运行时间分别减少到原算法的1/140和1/450;与并行的NBlock优先(PBNF)算法相比,并行算法将加速比提高到3.2,同时,改进算法是严格的最佳优先搜索算法,保证了解的质量,且易于实现。

关键词: A^*算法, 启发式搜索, 高性能计算, 并行程序设计, 数据结构

Abstract:

Aiming to improve the low time performance of A^* algorithm, an algorithm based on Parallel Searching and Fast Inserting (PSFI) was presented. Firstly, well known parallel heuristic search algorithms on shared memory platform were researched. Then the original serial A^* algorithm was improved using a Delayed Single Table Searching (DSTS) method and new data structure. In the next place, a kind of parallel algorithm based on shared memory platform was designed. Finally, the proposed algorithm was implemented with OpenMP. The experimental results on 24-puzzle problem show that the improved serial and parallel algorithms decrease the runtime to 1/140 and 1/450 of the unimproved algorithms respectively. The speed-up ratio of parallel algorithm raises to 3.2 compared with the Parallel Best-NBlock-First (PBNF) algorithm. At the same time, the improved algorithm is strict best-first searching algorithm, which ensures the solution quality and is easy to implement.

Key words: A^* algorithm, heuristic search, high-performance computation, parallel programming, data structure

中图分类号:

TP18
TP301.6

熊壬浩, 刘羽. A^*算法的改进及并行化[J]. 计算机应用, 2015, 35(7): 1843-1848.

XIONG Renhao, LIU Yu. Improvement and parallelization of A^* algorithm[J]. Journal of Computer Applications, 2015, 35(7): 1843-1848.

参考文献

[1] STURTEVANT N R, FELNER A, LIKHACHEV M, et al. Heuristic search comes of age [C]// Proceedings of the 26th AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2012: 2186-2188.
[2] LI W, DAI F. Research of increased best-first-search diversity [J]. Computer Engineering and Design, 2013, 34(9): 3237-3239. (李伟生,代飞.基于增加最优优先搜索多样性的研究[J].计算机工程与设计,2013,34(9):3237-3239.)
[3] BURNS E, LEMONS S, ZHOU R, et al. Best-first heuristic search for multi-core machines [J]. Journal of Artificial Intelligence Research, 2010, 39(1): 689-743.
[4] ZHOU R, HANSEN E A. Edge partitioning in external-memory graph search [C]// Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. San Francisco: Morgan Kaufmann, 2007: 1666-1671.
[5] SANZ V, de GIUSTI A, NAIOUF M. 4-(N²-1) puzzle: parallelization and performance on clusters [J]. Journal of Computer Science and Technology, 2010, 10(2): 87-96.
[6] YAN J, HE J, HAN W, et al. How OpenMP applications get more benefit from Many-Core era [C]// IWOMP'10: Proceedings of the 6th International Conference on Beyond Loop Level Parallelism in OpenMP: Accelerators, Tasking and more, LNCS 6132. Berlin: Springer, 2010: 83-95.
[7] RIOS L H O, CHAIMOWICZ L. A survey and classification of A^* based best-first heuristic search algorithms [C]// SBIA'10: Proceedings of the 20th Brazilian Conference on Advances in Artificial Intelligence, LNCS 6404. Berlin: Springer, 2010: 253-262.
[8] MAHAFZAH B A. Parallel multithreaded IDA^* heuristic search: algorithm design and performance evaluation [J]. International Journal of Parallel Emergent and Distributed Systems, 2011, 26(1): 61-69.
[9] PACHECO P S. An introduction to parallel programming [M]. DENG Q, translated. Beijing: China Machine Press, 2012: 153-161.(PACHECO P S.并行程序设计导论[M].邓倩妮,译.北京:机械工业出版社,2012:153-161.)
[10] WEN A, LI S. One direct solution of N-puzzle problem and its optimization [J]. Computer Applications and Software, 2010, 27(5): 266-267.(温安国,李松年.N数码问题直接解及优化研究[J].计算机应用与软件,2010,27(5):266-267.)
[11] LI W, YING T, LI Y, et al. Analysis of parallel computing environment overhead of OpenMP for loop with multi-core processors [C]// PDCAT 2010: Proceedings of the 2010 International Conference on Parallel and Distributed Computing, Applications and Technologies. Piscataway: IEEE, 2010: 515-517.
[12] THOMAN P, JORDAN H, PELLEGRINI S, et al. Automatic OpenMP loop scheduling: a combined compiler and runtime approach [C]// IWOMP'12: Proceedings of the 8th International Conference on OpenMP in a Heterogeneous World, LNCS 7312. Berlin: Springer, 2012: 88-101.
[13] KISHIMOTO A, FUKUNAGA A, BOTEA A. Evaluation of a simple, scalable, parallel best-first search strategy [J]. Artificial Intelligence, 2013, 195(1): 222-248.

[1]	李钊, 董霄霄, 黄程程, 任崇广. 基于启发式搜索的浮点表达式设计空间探索方法[J]. 计算机应用, 2020, 40(9): 2665-2669.
[2]	祁玄玄, 黄家骏, 曹建安. 基于改进A^*算法的无人车路径规划[J]. 计算机应用, 2020, 40(7): 2021-2027.
[3]	孙鹏, 肖经, 赵海盟, 刘帆, 晏磊, 赵红颖. 基于DSP的无人机遥感影像SIFT算法设计与实现[J]. 计算机应用, 2020, 40(4): 1237-1242.
[4]	屈立成, 吕娇, 赵明, 王海飞, 屈艺华. 基于三维时空地图和运动分解的多机器人路径规划算法[J]. 计算机应用, 2020, 40(12): 3499-3507.
[5]	童心赤, 张华军, 郭航. 多方向无人水面艇路径规划算法[J]. 计算机应用, 2020, 40(11): 3373-3378.
[6]	王中玉, 曾国辉, 黄勃, 方志军. 改进A^*算法的机器人全局最优路径规划[J]. 计算机应用, 2019, 39(9): 2517-2522.
[7]	周爱平, 朱琛刚. 基于概要数据结构的全网络持续流检测方法[J]. 计算机应用, 2019, 39(8): 2354-2358.
[8]	何希, 吴炎桃, 邸臻炜, 陈佳. 基于图形处理器的形态学重建系统[J]. 计算机应用, 2019, 39(7): 2008-2013.
[9]	龚鸣清, 叶煌, 张鉴, 卢兴敬, 陈伟. 基于ARMv8架构的面向机器翻译的单精度浮点通用矩阵乘法优化[J]. 计算机应用, 2019, 39(6): 1557-1562.
[10]	赵士操, 肖永浩, 段博文, 李于锋. HSWAP:适用于高性能计算环境的数值模拟工作流管理平台[J]. 计算机应用, 2019, 39(6): 1569-1576.
[11]	陈若男, 文聪聪, 彭玲, 尤承增. 改进A^*算法在机器人室内路径规划中的应用[J]. 计算机应用, 2019, 39(4): 1006-1011.
[12]	徐佳庆, 万文, 蔡东京, 唐付桥, 何杰, 张磊. 高维胖树系统中确定性路由容错策略实现[J]. 计算机应用, 2018, 38(5): 1393-1398.
[13]	王维, 裴东, 冯璋. 改进A^*算法的移动机器人最短路径规划[J]. 计算机应用, 2018, 38(5): 1523-1526.
[14]	王鹏, 周岩. 面向高性能应用的MPI大数据处理[J]. 计算机应用, 2018, 38(12): 3496-3499.
[15]	张润莲, 张鑫, 张楚芸, 奚玉昂. 规则网格数字高程模型中基于距离与坡度的路径规划算法[J]. 计算机应用, 2018, 38(11): 3188-3192.

A^*算法的改进及并行化

Improvement and parallelization of A^* algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

A*算法的改进及并行化

Improvement and parallelization of A* algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

A^*算法的改进及并行化

Improvement and parallelization of A^* algorithm