提出新并行搜索算法，保证扩展状态数不超串行搜索的常数倍。
Parallel Greedy Best-First Search with a Bound on Expansions Relative to Sequential Search
- 设计逐个基准推进的并行贪心搜索策略
- 实验验证扩展状态数始终在串行搜索的常数倍内
- 适合追求可预测性能的并行搜索应用
非自适应搜索算法（如贪心最佳优先搜索，GBFS）的并行化面临挑战，因直接并行可能导致搜索行为与串行结果显著偏离。此前工作提出PUHF算法，通过限制仅扩展某些串行贪心搜索中可扩展的状态来控制偏差。我们证明，即使在该约束下，PUHF扩展的状态数仍无法被串行GBFS在最坏情况下的状态数的常数倍所限制。为此，我们提出并实验评估了「逐个基准推进」（One Bench At a Time, OBAT）算法，该算法保证其扩展状态数始终在某个串行GBFS策略下的常数倍之内，实现理论可预测的并行性能。
原文摘要 · Abstract (English)
Parallelization of non-admissible search algorithms such as GBFS poses a challenge because straightforward parallelization can result in search behavior which significantly deviates from sequential search. Previous work proposed PUHF, a parallel search algorithm which is constrained to only expand states that can be expanded by some tie-breaking strategy for GBFS. We show that despite this constraint, the number of states expanded by PUHF is not bounded by a constant multiple of the number of states expanded by sequential GBFS with the worst-case tie-breaking strategy. We propose and experimentally evaluate One Bench At a Time (OBAT), a parallel greedy search which guarantees that the number of states expanded is within a constant factor of the number of states expanded by sequential GBFS with some tie-breaking policy.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。