LLM-Aided A* Search in Non-Geometric Network Graphs

📄 arXiv: 2606.23136v1 📥 PDF

作者: Nouf Alabbasi, Esraa Ghourab, Omar Alhussein

分类: cs.NI, cs.AI, cs.LG

发布日期: 2026-06-22

💡 一句话要点

提出LLM辅助的A*搜索算法以解决非几何网络图中的最短路径问题

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 最短路径 非几何网络图 A*算法 大型语言模型 启发式搜索 网络优化 路径规划

📋 核心要点

  1. 在非几何网络图中，现有的启发式搜索算法面临缺乏有效启发式信息的问题，导致搜索效率低下。
  2. 本文提出了一种LLM辅助的A*算法，通过生成中间路径点来引导搜索，利用地标距离作为启发式信息。
  3. 实验结果显示，使用LLM生成的路径点可以将扩展节点数量减少约50%，并且路径成本仅略有增加，显示出显著的优化效果。

📝 摘要（中文）

在非几何网络图中寻找最短路径是一个挑战，因为边权重编码的是延迟或货币成本等任意度量，而非空间距离。本文提出了一种LLM辅助的A算法，其中LLM生成中间路径点，引导A扩展到有前景的图区域。核心方法是使用地标距离，作为可接受的地标基础启发式（ALT）来恢复缺失的目标距离信号。实验表明，LLM生成的路径点将扩展节点数量减少约50%，同时路径成本仅略有增加。这些结果展示了将LLM指导与经典搜索算法结合的潜力。

🔬 方法详解

问题定义：本文旨在解决在非几何网络图中寻找最短路径的问题。现有方法依赖于空间距离的启发式信息，而在非几何图中缺乏有效的启发式信息，导致搜索效率低下。

核心思路：论文提出的核心思路是利用大型语言模型（LLM）生成中间路径点，这些路径点能够引导A*算法的搜索方向，帮助其更有效地探索图的有前景区域。通过引入地标距离，恢复了缺失的目标距离信号。

技术框架：整体架构包括三个主要模块：首先，使用LLM生成中间路径点；其次，利用地标距离作为启发式信息；最后，执行A*算法进行路径搜索。

关键创新：最重要的技术创新在于将LLM与传统的A*搜索算法结合，利用LLM生成的路径点和地标距离来提升搜索效率。这一方法与现有方法的本质区别在于不再依赖于几何信息，而是通过语言模型提供的上下文信息进行优化。

关键设计：关键设计包括地标距离的计算方法和LLM的输入输出结构。通过精心设计的提示工程，确保LLM能够生成有效的路径点，并且在实验中验证了不同提示对结果的影响。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果显示，LLM生成的路径点使得扩展节点数量减少约50%，而路径成本仅略有增加，表明该方法在优化搜索效率方面具有显著优势。与基线方法相比，LLM辅助的A*算法在多种图拓扑上均表现出色，验证了其有效性。

🎯 应用场景

该研究的潜在应用领域包括网络优化、物流调度和交通管理等。通过提高非几何网络图中路径搜索的效率，能够在实际应用中节省时间和成本，具有重要的实际价值和广泛的应用前景。

📄 摘要（原文）

Finding the shortest path in non-geometric network graphs, where edge weights encode arbitrary metrics such as latency or monetary cost rather than spatial distance, poses a challenge for informed search algorithms. Their efficiency depends on an informative heuristic, typically supplied in spatial domains by geometric distances that have no counterpart on non-geometric graphs. We propose a large language model (LLM)-aided A algorithm in which an LLM generates intermediate waypoints that guide the A expansion toward promising graph regions. At the core of the approach are landmark distances, which serve both as an admissible landmark-based (ALT) heuristic for the search and as a compact structural feature that, supplied to the LLM, restores the distance-to-destination signal it would otherwise lack on non-geometric graphs. Our comprehensive experiments on multiple graph topologies with up to 2,000 nodes demonstrate that LLM-generated waypoints reduce the number of expanded nodes by around 50% while incurring only a marginal path cost increase compared to the optimal solution. We further analyze the impact of prompt engineering and show that incorporating compact structural features, namely heuristic estimates, is more effective than advanced prompting techniques. These findings demonstrate the potential of combining LLM- based guidance with classical search algorithms for efficient network optimization.