When A* Performs Worse Than Uninformed Search: A Poor Heuristic Case Study

In graph search, A* search relies on a heuristic heuristic function $h(n)$ to focus exploration. In principle, a “good” heuristic reduces the number of expanded nodes. However, if the heuristic is poorly chosen—especially if it is inconsistent heuristic or effectively misguides the priority ordering—A* can behave much closer to (or even worse than) an uninformed baseline such as uniform-cost search (UCS) or BFS in practice.

A canonical situation where A* can perform worse is when $h(n)$ severely overestimates or is highly inconsistent, causing A* to repeatedly commit to wrong regions of the state space. With inconsistency, nodes may be reopened/re-expanded (the “thrashing” effect), inflating work beyond what UCS would do because UCS expands purely by increasing $g(n)$ without being misled by $h(n)$. This is especially clear in problems where there exist many low-$g$ nodes that lead to dead ends, while a misleading heuristic makes a large set of longer-$g$ paths look promising early.

Key learning point: A* is only guaranteed to be optimally efficient (in terms of expansions relative to alternatives) under assumptions about the heuristic. If those assumptions are violated, the heuristic can dominate the search order and produce excessive expansions compared to an uninformed strategy.

Concrete scenario: “Dead-end region” + misleading heuristic (inconsistent/overconfident)

Consider a directed graph (or state space) with:

• Start $S$
• Goal $G$
• A large dead-end region of states $D=\{d_1,\dots,d_N\}$ reachable via relatively cheap edges (so they have low $g$ values early), but from which reaching $G$ requires a dramatic detour that the heuristic fails to predict.
• A solution corridor $C$ that leads to $G$ but initially involves steps that have higher $g$.

Now define a heuristic $h(n)$ that is poorly chosen:

• It assigns very small $h(n)$ to states in the dead-end region $D$ (making them look closer to the goal than they really are).
• It assigns very large $h(n)$ to states in the solution corridor $C$ (making them appear far).

Then:

• A* prioritizes nodes in $D$ because their $f(n)=g(n)+h(n)$ is small.
• It spends substantial time expanding many dead-end branches.
• If $h$ is also inconsistent, the search may later find that previously expanded nodes had underestimated/overestimated relationships, causing re-expansions and further increasing total work.

This can yield more expansions than UCS, which ignores $h$ and expands strictly by $g(n)$. If UCS quickly discovers the correct-cost route corridor (because its $g$-values are competitive), UCS may outperform A* even though A* is “informed.”

Why this can happen: heuristic dominance + loss of guidance

A* effectively trades off actual cost so far ($g$) and estimated cost to go ($h$) via $f(n)=g(n)+h(n)$ A* search. When $h$ is badly calibrated:

• $h$ can dominate $f$, so the search order mostly reflects your heuristic’s errors rather than promising path cost.
• If $h$ is inconsistent, A* may not maintain the clean “single expansion” behavior; it can revisit states, increasing total expansions. This is frequently summarized as re-expansion or reopening behavior in A* variants.
• Even if the heuristic is admissible, a heuristic can still be “admissible but weak,” providing little additional guidance—so A* can degrade toward UCS-like behavior. With inconsistency or overconfidence, it can become worse.

Intuition check with a small numeric sketch

Suppose at some early depth you have two frontier nodes:

• Dead-end candidate $d$: $g(d)=2$, heuristic $h(d)=0 \Rightarrow f(d)=2$
• Corridor candidate $c$: $g(c)=3$, heuristic $h(c)=50 \Rightarrow f(c)=53$

A* will pop $d$ for expansion. If there are many such $d_i$ with similarly low $f$, A* will explore them first. UCS would expand by $g$, so it would consider $c$ earlier when its $g$ becomes smallest among remaining candidates.

Now add inconsistency: later you might find a path that reduces $g$ for a previously expanded node, causing additional processing in A*—something UCS would not need to correct because it already expands in nondecreasing $g$.