Bidirectional A*: comparing balanced and symmetric heuristic methods
2006-10-16
Research Paper
This publication is part of collection
| Related Files |
|---|
View PDF Version
(ei2006-41.pdf, 0.9MB) |
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
Automatically Extracted Terms
- algorithm
- search
- heuristic
- search space
- process
- space
- bidirectional
- section
- post-phase
- node v
- estimate
- distance
- predecessor
- function
- lemma
- length
- figure
- ~ ~ ~
- property
- network
