该论文旨在解决在最短路径启发式搜索中,如何将神经网络与经典算法(如ALT)结合时保持启发式的可采纳性(admissibility)这一关键问题。研究背景是:传统ALT算法依赖人工选择地标(landmarks),而神经网络虽能学习选择地标,但难以保证其输出的启发式始终满足可采纳性约束,这限制了端到端学习的应用。
论文提出了一个名为AAC(Architecturally Admissible Compressor)的可微分(differentiable)地标选择模块。其核心方法是:
- 设计一个架构,使其前向传播的输出是三角不等式(triangle inequality)下界的行随机(row-stochastic)混合。
- 这种构造确保了对于任何参数设置,生成的启发式函数天生就是可采纳的(admissible by construction),无需额外的收敛、校准或投影步骤。
- 在部署时,该模块可简化为在学得的地标子集上运行的经典ALT算法,从而与神经编码器(neural encoders)进行端到端组合,同时保留经典工具链。
论文的核心创新点在于:
- **首个可微分的、保持可采纳性的压缩架构**:这是经典启发式搜索中“压缩同时保持可采纳性”传统的第一个可微分实例。
- **架构保证的可采纳性**:通过巧妙的架构设计,确保所有参数设置下输出的启发式都自动满足可采纳性,从根本上解决了学习与理论保证之间的矛盾。
- **识别并解决了关键训练瓶颈**:通过对照实验(controlled ablation)发现,性能瓶颈并非架构容量,而是默认初始化下的训练目标漂移(objective drift),并提出“前m个恒等初始化(identity-on-first-m initialization)”来完全消除扩展计数(expansion-count)的差距。
论文对该领域的整体贡献包括:
- **理论贡献**:在匹配的每顶点内存协议(matched per-vertex memory protocol)下,证明了采用最远点采样地标(FPS-ALT)的ALT在度量图(metric graphs)上具有接近最优的覆盖率(coverage),为任何选择器设定了性能上限。
- **实践贡献**:AAC模块在实践中性能接近该理论上限,在多个真实和合成图数据集上验证了其有效性和零可采纳性违规。在匹配内存下,其查询速度也优于FPS-ALT。
- **资源贡献**:开源了AAC模块、一个可复用的匹配内存基准测试协议(包含配对双单侧检验(TOST)等价性和预注册(pre-registration)),以及一个参考的压缩差分启发式基线(baseline),为后续研究提供了工具和标准。