A* or Bidirectional Breadth First Search?

0
votes

Not sure if this is the right place to ask but,

I have programmed a bidirectional breadth-first search algorithm in Java which searches from both the start node in a graph and the goal node in a graph at the same time. In a graph with 3000000 (3 million) nodes of which all nodes are connected with an average of 4 other nodes (connected with two-way/bidirectional edges) it takes on average only 0.5 seconds on a mediocre CPU to find the shortest path between any two random nodes, with about 10 seconds being the worst-case time that I found over 30 test runs.

Assuming that only a search for one path is required (for example, when plotting a route between a starting point and a destination), what would be the advantages of using an A* algorithm with a decent heuristic in this case? Yes, it might be slightly faster with finding a path, but A* most likely won't find the shortest path.

Can someone elaborate on why A* is often chosen over bidirectional breadth-first search and what advantages it yields in terms of performance (computation time, memory usage, the chance of finding the optimal solution etc.)?

Also, Happy easter everyone!

1
performancesearchbreadth-first-searcha-star
"but A* most likely won't find the shortest path" - if your A* isn't finding the shortest path, either your A* algorithm or your heuristic is wrong. If you haven't tried it and you just think it wouldn't find the shortest path, your understanding of A* is wrong. - user2357112 supports Monica
@user2357112 You would need to have a perfect heuristic in order to find the shortest path with A*, and as far as I know no perfect heuristic is known for finding a path between any two points in a graph. - ImJustACowLol
@user2357112 Let me correct myself : There are perfect heuristics, but with those heuristics the A* algorithm performs virtually the same as a breadth-first algorithm. - ImJustACowLol
"You would need to have a perfect heuristic in order to find the shortest path with A*" - no you would not. You need an admissible heuristic, and for efficient implementation, you usually want a consistent heuristic. - user2357112 supports Monica
If the heuristic is admissible (or monotonic in graph search) then A* guarantees to find a best solution first. - gandaliter

1 Answers

1
votes

Bidirectional search is great when it’s feasible, but it relies on being able to produce goal nodes as easily as start nodes (how would you select a goal node in a chess game, for example?), and the branching factor being similar in both directions. It relies on being able to go backwards at all, come to that. Even if you have a good heuristic, you’re unlikely to be able to take much advantage from it in the reverse part of the search.