Bidirectional A*: comparing balanced and symmetric heuristic methods

Henk Post and Wim Pijls

No EI 2006-41, Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute

Abstract: 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 (search for similar items in EconPapers)
Date: 2006-10-16
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://repub.eur.nl/pub/8035/ei2006-41.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ems:eureir:8035

Access Statistics for this paper

More papers in Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute Contact information at EDIRC.
Bibliographic data for series maintained by RePub ( this e-mail address is bad, please contact ).