arXiv cs.AI· An T. Le, Vien Ngo·· 11 小时前AI 评分21
AAC：为 ALT 启发式设计的架构可容许可微分地标压缩
AAC: Admissible-by-Architecture Differentiable Landmark Compression for ALT
AI 导读
研究者提出 Architecturally Admissible Compressor（AAC），在固定标签内存预算下按查询需求自适应选择 ALT 地标，并提供两种连续松弛，其中行随机松弛可证明松弛最优与离散最优一致。
正文 · AI 翻译
摘要：我们提出了架构可容许压缩器（Architecturally Admissible Compressor，AAC），它在固定的标签内存预算下，将基于地标的 A* 启发式适配到查询需求。AAC 为 ALT（A*、地标与三角不等式）选择提供了两种连续松弛。在精确地标距离下，每个参数值都定义了最短路径距离的一个下界。两种松弛都仅使用所选标签来部署 ALT。行随机松弛取地标距离的凸组合。我们刻画了保持可容许性的最大线性类，并证明了松弛最优与离散最优一致。分数松弛混合子集启发式，并支持具有精确梯度的连续贪心（AAC-CG）以及用于可微选择的一个熵正则化 oracle。对于期望启发式值，我们证明了一个包含有限步、oracle 误差和有限样本项的近似保证。除非 P${=}$NP，否则极限 $1-1/e$ 因子对于任意给定的池和查询分布都是最优的。在匹配的标签内存下，AAC-CG 在六个道路网络和两个合成图上的全部 $19$ 个图与内存预算测试组合中，相对于最远点 ALT（FPS-ALT）将 A* 扩展数减少了 $1.9$-$22.7$%。每个组合使用一个 $500$ 查询的测试划分；当距离对称时，所有方法共享距离表。在全部 $19$ 个图-预算对中，规范贪心也比 FPS-ALT 扩展更少的节点。在这些对上平均，AAC-CG 在测试查询上达到规范贪心平均启发式值的 $99.6$%。AAC 使可容许性独立于训练成功，而其分析和实验将选择质量与搜索效率区分开来。
| 评论： | 80 页。已被 Transactions on Machine Learning Research (TMLR) 接收。代码：此 https URL |
| 主题： | 人工智能（cs.AI）；机器学习（cs.LG）；机器人学（cs.RO） |
| 引用为： | arXiv:2604.20744 [cs.AI] |
| （或此版本的 arXiv:2604.20744v2 [cs.AI]） | |
| https://doi.org/10.48550/arXiv.2604.20744 由 DataCite 颁发的 arXiv DOI |
提交历史
来自：An Thai Le [查看电子邮件]
[v1]
2026 年 4 月 22 日星期三 16:31:21 UTC（867 KB）
[v2]
2026 年 11 月 4 日星期三 18:26:24 UTC（976 KB）
来源：arXiv cs.AI · arxiv.org