Breadth First Search vs A* with Manhattan Distance in a maze

It's impossible. The intuition is your heuristic is more informed than BFS. This is also the base for proving it.

Formally:

• h'(n) = 0 is also an admissible heuristic function.

• BFS is basically A* using h' as its heuristic function (since it always expands based on f'=g(n) + h'(n) = g(n))

• h dominates h', since for all n: h'(n) <= h(n).
• Since h dominates h', and is monotone, then the nodes expanded by algorithm using h is a subset of those expanded by algorithm using h'. More info and proof in this thread, and in the original article

QED

There are three ways this can happen in general:

1. When A* gets an inconsistent heuristic. A* can do up to 2^N expansions of N states with an inconsistent heuristic. For an undirected graph an inconsistent heuristic has some states with |h(a, g)-h(b, g)| > c(a, b) even if the heuristic is admissible (h(a, g) <= c(a, g)). Manhattan distance is consistent, so this won't work in your example.

2. In a breadth-first search it is assumed that all costs are 1. Thus, when the goal is generated, it can terminate immediately knowing that it has the optimal cost to the goal. A* typically does not terminate until the goal is selected for expansion. Note that if A* was guaranteed that all edges have uniform cost (or some minimum cost), then A* could do the same.

3. A* is only optimal up to necessary expansions - those with f(n) < C* where C* is the optimal solution cost. If a problem instance has more than one state with f(n) = C* then A* could do worse if it did poorly with tie-breaking and BFS got lucky with tie-breaking.

So, now consider this example:

....._.     
SXXXXG.
.......

Here, a . is open space, as is the _ cell. S is the start and G is the goal. The X states are impassible and the _ cell can be reached/expanded, but you can't go down from that state to the goal.

If A* is unlucky it will expand the top route first (assume it expands largest g-cost first, but this also works with other tie-breaking). That route looks promising until it reaches the end, after which A* will have to expand the full alternate route.

Assume BFS gets lucky and expands the state below G before the _ state. Then, BFS will be able to terminate without expanding the _ state, and do fewer expansions that A*.

To be clear, label the states in the previous example as follows:

abcdefg
SXXXXG.
hijklmn

A* with unlucky tie-breaking will expand a, b, c, d, e, f and generate g (but not expand it). Then it will continue and expand h, i, j, k, l, and m, after which it can terminate with the solution.

BFS with lucky tie-breaking will expand h, a, i, b, j, c, k, d, l, e, and m and then terminate with the optimal solution. BFS does one less expansion than A*, because it doesn't expand f.

So, yes, it is possible for BFS to beat A* if the tie-breaking works out in favor of BFS.

Such examples will always be possible unless A* and BFS always expand states in the same order, or if further restrictions are put on the maze so that the heuristic is always perfect next to the goal.

See this paper for common misconceptions about A* search. One addresses the misconception that a better heuristic will do less work, and another addresses the misconception that A* with a 0-heuristic is the same as BFS.

--

Note 1: There is some discussion in the comments about whether the _ state is expanded if it doesn't have any successors. The original A* paper states:

Starting with the node s, they generate some part of the subgraph G, by repetitive application of the successor operator R. During the course of the algorithm, if R is applied to a node, we say that the algorithm has expanded that node.

Thus, if we apply the R operator and find no successors, we still have expanded the node. (They use a greek letter which I've replaced with R.) But, with a small edit to the map above, the _ state does have one successor, so _ is expanded by A* and a successor is generated (not the goal).

Note 2:

There is a question in the comments about Theorem 3 in the A* paper. That theorem states that there always exists some tie-breaking scheme for A* that will be at least as good as any other less informed algorithm. There are two problems with this theorem. First, it only states that A* is capable of beating another algorithm given the right tie-breaking, not that it will always beat every other algorithm. The second problem is that BFS is more informed than A*. BFS knows all edges have unit cost and A* does not. So, the theorem does not apply to BFS, because BFS has more information.

Note 3:

The question only asks "Is this possible." My answer provided here shows the precise conditions under which it is possible. The other answers (one of which has now been deleted) categorically state that it can never happen, and thus are incorrect.