A*算法的改进及并行化

• 作者: 刘羽 熊壬浩
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: A*算法 启发式搜索 高性能计算 并行程序设计 数据结构
• 年，卷（期）: 2015,（7）
• 所属期刊栏目: 先进计算
• 页码范围: 1843-1848
• 页数: 6页
• 分类号: TP18|TP301.6
• 字数: 9262字
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2015.07.1843

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘羽	桂林理工大学机械与控制工程学院	29	105	6.0	8.0
2	熊壬浩	桂林理工大学信息科学与工程学院	4	24	2.0	4.0