Is there any situation in which breadth-first search is preferable over A*?

Question

Is there any situation in which breadth-first search is preferable over A*?

Answer 1

The only general situation that comes to my mind where BFS could be preferred over A* is when your graph is unweighted and the heuristic function is $h(n) = 0, \forall n \in V$. However, in that case, A* (which is equivalent to UCS) behaves like BFS (except for the goal test: see section 3.4.2 of this book), i.e. it will first expand nodes at level $l$, then at level $l+1$, etc., this is because nodes at level $l+1$ are farther away from the initial node than nodes at level $l$, i.e. $f(n') = g(n') > f(n) = g(n)$, for all $n' \in V_{l+1}$ and $n \in V_{l}$, where $g(n)$ is the cost of the shortest path from the initial node to $n$ and $V_{l}$ is the subset of nodes of the search space that belong to level/layer $l$ of the search tree.

So, if you think that your goal is close to the initial node in terms of levels/layers and each node has a small branching factor (i.e. not many children), then BFS may be a good idea (but you could also use A*).

BFS can also be used as a sub-routine in other algorithms, such as the Ford–Fulkerson algorithm. So, in these cases, BFS may also be preferable.

Answer 2

There is an inherent assumption in heuristic search that the heuristic function points you in the right direction.

A* largely depends on how good the heuristic function is. Two nice properties for the heuristic function are for it to be admissible and consistent. If the latter stands, I can't think of any case where BFS would outperform A*. However, this property doesn't stand in every case.

If you select a misleading heuristic function (i.e. a function that points you in the wrong direction) then BFS should outperform A*.

---

I drew a dumb example to illustrate my point. You want to reach from the Initial State (IS) to the Goal State (GS). The shade of green indicates the value of the heuristic (the greener the better).

In the third case, where you have a misleading heuristic, A* would tend to explore areas near the top right first, then it would go down towards the GS. This case is actually worse than having no heuristic and using a BFS.