Bidirectional A*: comparing balanced and symmetric heuristic methods
A widely known algorithm for ¯nding the shortest path in a network is Bidirectional A*. The version of bidirectional A* that is considered the most appropriate hitherto, uses so-called balanced heuristic estimates. In this paper, we focus on symmetric heuristic estimates. First, we show that bidirectional A* using the symmetric heuristic estimate provides us with a feasible approximation. Next a framework is introduced for solving the shortest path problem exactly. It turns out that both the balanced and the symmetric heuristic estimate are instances of a general bidirectional A* framework. The symmetric instance surpasses the balanced instance in space and time.
|Keywords||graph theory, network flow, operations research, search, shortest path|
Post, H., & Pijls, W.H.L.M.. (2006). Bidirectional A*: comparing balanced and symmetric heuristic methods (No. EI 2006-41). Report / Econometric Institute, Erasmus University Rotterdam. Retrieved from http://hdl.handle.net/1765/8035