将深度优先搜索的启发式计算搬到GPU并行处理，提升求解效率。
A Parallel CPU-GPU Framework for Batching Heuristic Operations in Depth-First Heuristic Search
- CPU负责树搜索，GPU并行计算启发式值，解耦搜索与评估
- 在3×3魔方和4×4滑块谜题上提速2-5倍，支持分类与回归模型
- 适合需要高效启发式搜索的规划、游戏求解等场景
GPU技术的快速发展带来了强大的并行计算能力，为优化经典搜索算法提供了新可能。已有研究通过批量处理A*和加权A*中的启发式评估，利用神经网络启发式实现加速，但尚未解决深度优先算法（如IDA*或预算树搜索BTS）如何实现启发式批处理的问题。由于树搜索中进度依赖于启发式评估完成，该问题更具挑战性。本文提出一种并行化代价有界深度优先搜索（CB-DFS）框架，使搜索在CPU上并行进行，而启发式评估在GPU上并行执行。该方法可适用于IDA*和BTS，在3×3魔方和4×4滑块谜题（STP）上，使用基于分类器和回归的启发式均实现2至5倍性能提升。
原文摘要 · Abstract (English)
The rapid advancement of GPU technology has unlocked powerful parallel processing capabilities, creating new opportunities to enhance classic search algorithms. This hardware has been exploited in best-first search algorithms with neural network-based heuristics by creating batched versions of A* and Weighted A* that delay heuristic evaluation until sufficiently many states can be evaluated in parallel on the GPU. But, research has not addressed how depth-first algorithms like IDA* or Budgeted Tree Search (BTS) can have their heuristic computations batched. This is more complicated in a tree search, because progress in the search tree is blocked until heuristic evaluations are complete. In this paper we show that GPU parallelization of heuristics can be effectively performed when the tree search is parallelized on the CPU while heuristic evaluations are parallelized on the GPU. We develop a parallelized cost-bounded depth-first search (CB-DFS) framework that can be applied to both IDA* and BTS, significantly improving their performance. We demonstrate the strength of the approach on the 3x3 Rubik's Cube and the 4x4 sliding tile puzzle (STP) with both classifier-based and regression-based heuristics.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。