PRA*: Massively Parallel Heuristic Search
PRA*: Massively Parallel Heuristic Search
复制标题
PRA*：大规模并行启发式搜索
DOI：
10.1006/jpdc.1995.1036
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
Dana S. Nau
中科院分区：
文献类型：
--
作者：
M. Evett;J. Hendler;A. Mahanti;Dana S. Nau
本文描述了在大规模并行SIMD连接机(CM-2)上运行的A*SEARCH的一个变种。该算法被设计为通过使用收回技术在有限的存储器中运行，该收回技术允许从开放列表中移除启发值较差的节点，直到它们可能需要重新扩展的时间，更有希望的路径已经失败。我们的算法称为PRA*(代表并行撤销A*)，旨在最大限度地利用连接机的内存和处理器。此外，当使用允许启发式算法时，算法保证返回一条最优路径。结果对于15个谜题，PRA*与Korf的IDA*相比，PRA*的节点扩展显著减少。此外，实验结果显示出显著的并行加速比，这表明该算法的设计具有较高的处理器利用率。
Abstract In this paper we describe a variant of A* search designed to run on the massively parallel, SIMD Connection Machine (CM-2). The algorithm is designed to run in a limited memory by the use of a retraction technique which allows nodes with poor heuristic values to be removed from the open list until such time as they may need reexpansion, more promising paths having failed. Our algorithm, called PRA* (for Parallel Retraction A*), is designed to maximize use of the Connection Machine′s memory and processors. In addition, the algorithm is guaranteed to return an optimal path when an admissible heuristic is used. Results comparing PRA* to Korf′s IDA* for the fifteen puzzle show significantly fewer node expansions for PRA*. In addition, empirical results show significant parallel speedups, indicative of the algorithm′s design for high processor utilization.