CBHA* 算法显著提升飞行方块谜题求解效率

arXiv 上发表的一篇研究论文针对「双列飞行方块谜题」（Two-column Flying Block Puzzle）这一严格 NP 完全的空间规划微世界，提出了一种名为 Class-Based Heuristic A*（CBHA*）的改进搜索算法。论文指出，通用启发式难以利用受限空间域的结构性约束，在较难实例上搜索性能会急剧下降，CBHA* 旨在通过「分类触发」的自适应启发式解决这一问题。

算法核心机制

CBHA* 引入了三项相互配合的机制：

General Move Constraint（通用移动约束）：在空位稀缺时刻画最小位移代价，确保启发式在结构受限场景下仍保持可采纳性。
运动学分类体系：将状态空间划分为 7 个互斥类别，每类对应基于「空位比」与「目标方块几何」的严格可采纳启发式。
分类条件下的平局打破策略：在 f 值出现平台时，动态切换深度优先与垂直距离优先的展开顺序，缓解搜索退化。

基准测试结果

研究在 146 个基准实例上对比了多种算法：

CBHA* 成功率：93.4%
Depth-Prioritized A*：64%
Standard A*：39%
BFS：17%

相较于 Standard A*，CBHA* 的节点扩展量下降 87.98%，平均有效分支因子维持在约 3 左右，表明搜索过程没有出现组合爆炸。

适用范围与意义

该工作以双列飞行方块谜题这一受限空间几何为研究载体，其瓶颈几何结构可对应多智能体路径规划、自动驾驶导航、方块重排系统中的「净空—尺寸」约束。研究结论显示，分类触发的自适应启发式是一种「原理清晰」的机制，能够在结构性受限的物理约束系统中实现高效空间规划，具备一定的泛化潜力。不过，该方法主要在特定微世界中验证，向更大规模工业级规划任务的迁移效果尚需进一步验证。