In what cases would BFS and DFS be more efficient than A* search algorithm?

Question

I've tested A* search against Breadth First Searching (BFS) and Depth First Searching (DFS) and I find that fewer nodes are being expanded with A*.

I understand that A* expands paths that are already less expensive by using the heuristic and edge cost function.

In what cases would BFS and DFS be more efficient as compared to A* search algorithm?

Answer 1

BFS uses a queue while A* uses a priority queue. In general, queues are much faster than priority queues (eg. Dequeue() is O(1) vs O(log n)). The advantage of A* is that it normally expands far fewer nodes than BFS, but if that isn't the case, BFS will be faster. That can happen if the heuristic used is poor, or if the graph is very sparse or small, or if the heuristic fails for a given graph.

Keep in mind that BFS is only useful for unweighted graphs. If the graph is weighted, you need to use BFS's older brother, Dijkstra's Algorithm. This algorithm uses a priority queue, and as such should almost never be faster than A*, except in cases where the heuristic fails.

Answer 2

A breadth-first search may outperform A* when the heuristic is inconsistent. (An inconsistent heuristic doesn't obey the triangle inequality. A consistent heuristic never changes more than the edge cost from one state to the next.)

With an inconsistent heuristic A* may expand N states up to 2^N times. The example of where this occurs can be found online. Step through the example if you want to understand what happens. BFS will only expand each state at most once. Note that this can be partially fixed by algorithm B (N states expanded at most N^2 times), but this is still a large overhead. The recent IBEX algorithm has much better worst-case guarantees - N log C*, where C* is the optimal solution cost.

A depth-first search may outperform A* and BFS if the goal is on the first branch. In this demo you can place the goal at different states in the tree to see what happens.

There are other constant factors to consider. DFS only needs a single copy of a state, while A* keeps many states on the OPEN/CLOSED lists. But, in these cases IDA* should be used instead.

Note that theoretically speaking, in unidirectional search with a consistent heuristic, A* does the fewest number of necessary expansions required to prove that the solution is optimal.