2006-10-16
Bidirectional A*: comparing balanced and symmetric heuristic methods
Publication
Publication
Report / Econometric Institute, Erasmus University Rotterdam
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.
Additional Metadata | |
---|---|
, , , , | |
hdl.handle.net/1765/8035 | |
Econometric Institute Research Papers | |
Report / Econometric Institute, Erasmus University Rotterdam | |
Organisation | Erasmus School of Economics |
Post, H., & Pijls, W. (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 |