最優良探索の並列化の研究

在2022-2023年，我们开发了改进的并行搜索算法。虽然A*图搜索算法的并行化已经被很好地理解，但对诸如贪婪最佳优先搜索(GBFS)之类的非最优最佳优先搜索算法的并行化却知之甚少。最近的工作提出了PUHF，PUHF是一种并行GBFS，它将搜索限制在BTS的探索上，这是一组状态集，在某些打破平局的策略下，GBFS可以扩展BTS的状态集。然而，PUHF导致线程花费大量时间等待，以便只扩展保证在BTS中的状态。我们开发了PUHF2、PUHF3和PUHF4，PUHF是PUHF的三个改进，它们保持了只有BTS中的节点被附加的限制，但显著减少了空闲时间，并允许更快速地探索BTS，从而获得了比PUHF更好的搜索性能。

In 2022-2023, we developed improved algorithms for parallel search. While parallelization of the A* graph search algorithm is fairly well-understood,　parallelization of non-optimal best-first search algorithms such as Greedy Best-First Search (GBFS) has been much less understood. Recent work has proposed PUHF, a parallel GBFS which restricts search to exploration of the Bench Transition System (BTS), which is the set of states that can be expanded by GBFS under some tie-breaking policy.　However, PUHF causes threads to spend much of the time waiting so that only states which are guaranteed to be in the BTS are expanded.　We developed PUHF2, PUHF3, and PUHF4, three improvements to PUHF which maintain the constraint that only nodes in the BTS are epanded, but significantly reduce idle time and allow more rapid exploration of the BTS, resulting in better search performance compared to PUHF.