提出并验证了外部内存下双向搜索的高效框架。
On Parallel External-Memory Bidirectional Search
- 构建支持双向与单向搜索的并行外部内存框架。
- PEM-BAE*在硬问题上优于A*、MM和IDA*的并行版本。
- 首次实证双向搜索在大规模问题中显著优于单向搜索。
并行化与外部内存（PEM）技术显著提升了搜索算法解决大规模问题的能力。以往的PEM研究主要聚焦于单向算法，仅有一次关于双向PEM的工作，且仅针对相遇于中间（MM）算法。本文在此基础上，提出一个集成单向与双向最佳优先搜索算法的框架，并开发了最先进的双向启发式搜索算法BAE*的PEM变体（PEM-BAE*）。由于此前对双向启发式搜索（BiHS）未关注问题规模扩展，本工作使我们能评估其在困难问题上的表现。实验表明，PEM-BAE*优于A*和MM算法的PEM版本，以及并行版IDA*。这些发现标志着重要里程碑，揭示即便使用先进启发式，双向搜索在多个领域仍明显优于单向搜索。
原文摘要 · Abstract (English)
Parallelization and External Memory (PEM) techniques have significantly enhanced the capabilities of search algorithms when solving large-scale problems. Previous research on PEM has primarily centered on unidirectional algorithms, with only one publication on bidirectional PEM that focuses on the meet-in-the-middle (MM) algorithm. Building upon this foundation, this paper presents a framework that integrates both uni- and bi-directional best-first search algorithms into this framework. We then develop a PEM variant of the state-of-the-art bidirectional heuristic search (BiHS) algorithm BAE* (PEM-BAE*). As previous work on BiHS did not focus on scaling problem sizes, this work enables us to evaluate bidirectional algorithms on hard problems. Empirical evaluation shows that PEM-BAE* outperforms the PEM variants of A* and the MM algorithm, as well as a parallel variant of IDA*. These findings mark a significant milestone, revealing that bidirectional search algorithms clearly outperform unidirectional search algorithms across several domains, even when equipped with state-of-the-art heuristics.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。