Template-Type: ReDIF-Paper 1.0
Author-Name: Post, H.
Author-Name-Last: Post
Author-Name-First: Henk
Author-Name: Pijls, W.H.L.M.
Author-Name-Last: Pijls
Author-Name-First: Wim
Title: Bidirectional A*: comparing balanced and symmetric heuristic methods
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.
Creation-Date: 2006-10-16
File-URL: https://repub.eur.nl/pub/8035/ei2006-41.pdf
File-Format: application/pdf
Series: RePEc:ems:eureir
Number: EI 2006-41
Keywords: graph theory, network flow, operations research, search, shortest path
Handle: RePEc:ems:eureir:8035