A*算法的改进及并行化

摘要：

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

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

所属期刊栏目：35

分类号：TP18;TP301.6(自动化基础理论)

资助基金：国家自然科学基金资助项目41264005

在线出版日期：2015-10-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：1843-1848