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

• 先进计算 • 上一篇    下一篇

A*算法的改进及并行化

熊壬浩1, 刘羽2   

  1. 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 Renhao1, LIU Yu2   

  1. 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

摘要:

针对串行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

中图分类号: