Bidirectional A* (A-star) Search

Question

I'm implementing a bidirectional A* search (bidirectional as in the search is performed from both the origin and destination simultaneously, and when these two searches meet, I'll have my shortest path - at least with a bit of extra logic thrown in).

Does anyone have any experience with taking a unidirectional A* and bidirectionalising(!) it - what sort of performance gain can I expect? I'd reckoned on it more-or-less halving the search time, at a minimum - but may I see bigger gains that this? I'm using the algorithm to determine shortest routes on a road network - if that's in any way relevant (I've read about MS's "Reach" algorithm, but want to take baby-steps towards this rather than jumping straight in).

Answer 1

In the best possible case it'd run in O(b^(n/2)) instead of O(b^n), but that's only if you're lucky :)

(where b is your branching factor and n is the number of nodes a unidirectional A* would consider)

It all depends on how easily the two searches meet, if they find each other at a good halfway point early in the search you've done away with a lot of search time, but if they branch into wildly different directions you may end up with something slower than simple A* (because of all the extra bookkeeping)