TL;DR

在 AI 赋能路径规划的今天，许多模型为了性能牺牲了保优性 (Admissibility)。本文介绍的 AAC (Architecturally Admissible Compressor) 突破性地提出了一种“由架构保证保优”的可微压缩模块。它不仅能像神经网路一样通过梯度下降优化地标选择，还能在逻辑上保证：无论网络训练得如何，搜索结果永远是最优路径。

背景定位：经典算法与深度学习的断裂

在经典算法领域，ALT (A, Landmarks, Triangle inequality)* 是处理最短路径问题的黄金法则。它利用三角形不等式建立启发式下界，但其核心痛点在于地标选择 (Landmark Selection)——这通常是一个不可微的组合优化问题。

而在深度学习领域，虽然涌现了 Neural A* 等模型，但它们大多通过损失函数来“逼近”保优性。一旦遇到分布外 (OOD) 数据，模型极易产生违规，导致搜索不到最短路径。AAC 的出现，填补了“经典算法的可解释性”与“深度学习的可优化性”之间的鸿沟。

核心直觉：为什么“架构级”保优可行？

AAC 的核心在于一个精妙的数学观察：保优启发式函数的凸组合仍然是保优的。

1. 架构解析

AAC 将地标选择过程参数化为一个行随机矩阵 (Row-stochastic Matrix)。在训练期间，它使用 Gumbel-softmax 进行软选择；在部署时，它退化为从原始地标池中挑选出的最优自集。

注：模型展示了从 Teacher Pool 到压缩后的部署地标的端到端流程。

2. 数学支撑

作者证明了，只要矩阵 $A$ 的每一行和为 1 且非负，压缩后的启发式函数 $h_A$ 就永远不会超过原始的 $h_{ALT}$，更不会超过真实距离 $d(u,t)$。这意味着：

• 无需投影 (Projection)
• 无需精心调参或校准
• 即便训练发散，安全性依然存在

实验战绩：不仅仅是严谨，而且更快

作者在 DIMACS 路网和 OGB-arXiv 论文引用网络等多个场景进行了测试，遵循严格的等效内存预算 (Matched Memory) 协议。

• 搜索效率：在 100 多万节点的 FLA 路网中，AAC 能够维持与 FPS-ALT 相当的节点扩展削减率（约 86%-92%）。
• 运行速度：令人惊讶的是，尽管节点扩展数略多于 FPS，但由于 AAC 的连续内存布局带来了更好的缓存局部性，其 p50 查询延迟比 ALT 快了 24% - 51%。
• 零违规记录：在超过 1500 次查询和所有实验运行中，AAC 记录到的 Admissibility 违规次数为 0。

注：图中展示了在不同内存预算下，随着地标数量增加，节点扩展数的变化曲线。

深度洞察：FPS 真的是不可超越的吗？

论文探讨了一个非常深刻的问题：既然 AAC 是可微的，为什么在某些路网实验中只是“逼近”而非“超越”了传统的 FPS (Farthest-Point Sampling)？

通过覆盖半径 (Covering Radius) 的理论分析，作者发现 FPS 提供的 Gonzalez 2-近似在度规图（如路网）上已经接近理论天花板。这意味着改进空间不在于算法本身，而在于地标池的质量。AAC 的真正价值在于，当图结构不再符合欧几里得直觉（如非度规的引用网络）或边权重动态变化时，它的可微性将展现出绝对优势。

总结与局限

AAC 成功地将经典图论的严谨性“硬编码”进了可微模型中。 尽管在静态路网上相对于 FPS 的提升空间受限，但它为以下场景铺平了道路：

• 端到端感知规划：直接从地形图片预测代价并选择地标。
• 异构图搜索：在没有明显空间结构的抽象图中学习最优锚点。

局限性：AAC 依赖于离线计算的 Teacher Pool，且对于动态变化剧烈的图，重新计算 SSSP（单源最短路径）的开销依然存在。

资深主编点评：AAC 是一篇典型的“硬核”论文，它没有盲目追求神经网络的复杂堆叠，而是回到了搜索算法的本质。它告诉我们，最高级的 AI 优化，往往是在理解了底层物理/数学约束后，通过精巧的架构设计来实现的。