改进双向A*搜索，大幅加速资源受限路径规划。
Resource Constrained Pathfinding with Enhanced Bidirectional A* Search
- 基于双向A*构建新框架，引入高效剪枝策略。
- 在大规模网络中实现比现有方法快100倍以上的搜索速度。
- 适合需要快速求解资源约束路径的智能系统应用。
经典资源受限最短路径（RCSP）问题旨在寻找网络中一对节点间的成本最优路径，同时满足资源使用上限。尽管该问题已研究十余年，近年已有基于启发式搜索的方法提升求解效率。本文基于双向A*搜索范式，提出一种新型约束搜索框架，采用高效的剪枝策略，在大规模网络中显著加速并有效求解RCSP问题。实验表明，与当前最优方法相比，该框架可将约束搜索时间减少两个数量级以上的幅度。
原文摘要 · Abstract (English)
The classic Resource Constrained Shortest Path (RCSP) problem aims to find a cost optimal path between a pair of nodes in a network such that the resources used in the path are within a given limit. Having been studied for over a decade, RCSP has seen recent solutions that utilize heuristic-guided search to solve the constrained problem faster. Building upon the bidirectional A* search paradigm, this research introduces a novel constrained search framework that uses efficient pruning strategies to allow for accelerated and effective RCSP search in large-scale networks. Results show that, compared to the state of the art, our enhanced framework can significantly reduce the constrained search time, achieving speed-ups of over to two orders of magnitude.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。