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

在2022-2023年，我们开发了改进的并行搜索算法。虽然对A*图搜索算法的并行化理解得相当好，但对非最优最佳优先搜索算法（如贪婪最佳优先搜索（GBFS））的并行化却知之甚少。最近的研究提出了PUHF，这是一种并行的GBFS，它将搜索限制在对Bench过渡系统（BTS）的探索中，BTS是在某些平局策略下GBFS可以扩展的状态集。然而，PUHF导致线程花费大量时间等待，因此只有保证在BTS中的状态才会被扩展。我们开发了PUHF的PUHF2、PUHF3和PUHF4，这三种改进保持了仅扩展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.