A*算法的改进及并行化

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

Improvement and parallelization of A* algorithm

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.