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

点击翻译按钮获取中文摘要

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.