CBHA*为两列飞块谜题选择分类启发式

摘要

研究以严格 NP 完全的两列 Flying Block Puzzle 为对象，提出 Class-Based Heuristic A*（CBHA*）。该方法结合空位稀缺时最小位移成本的通用移动约束、按空位比例与目标块几何划分的七个互斥状态类别及可采纳启发式，并按类别在深度优先和垂直距离排序间切换以应对 f 值平台。在 146 个基准实例中，CBHA* 成功率为 93.4%，Depth-Prioritized A*、Standard A* 和 BFS 分别为 64%、39% 和 17%；相较 Standard A*，节点扩展减少 87.98%，平均有效分支因子约为 3。