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!
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.