A* vs. Greedy Best-First Search: Optimal vs. Fast Explained

Try A* Solver →Try Greedy Solver →

TL;DR — Both algorithms are informed searches — they use a heuristic $h(n)$ to estimate the cost from a node to the goal. The difference is what they prioritize in the frontier. Greedy Best-First expands the node with the lowest $h(n)$ only — it chases the node that looks closest to the goal and ignores how much it already cost to get there. A* expands the node with the lowest $f(n) = g(n) + h(n)$ , where $g(n)$ is the actual cost from the start to $n$ , and $h(n)$ is the estimated cost from $n$ to the goal. By accounting for $g(n)$ , A* never forgets what the path has already cost and is guaranteed to find the optimal solution when $h(n)$ is admissible.

Feature Comparison

Feature	A* Search	Greedy Best-First Search
Priority Function	$f(n) = g(n) + h(n)$ — actual cost so far plus estimated cost to goal	$f(n) = h(n)$ — estimated cost to goal only; ignores cost already paid
What $g(n)$ Represents	The exact cost of the path from the start node to node $n$ — always tracked and used	Not used — Greedy Best-First completely ignores the cost incurred to reach $n$
What $h(n)$ Represents	A heuristic estimate of the cost from $n$ to the goal — must be admissible (never overestimates) for A* to be optimal	A heuristic estimate of the cost from $n$ to the goal — used as the sole ranking criterion with no admissibility requirement for correctness
Optimality	Guaranteed optimal — finds the lowest-cost solution when $h(n)$ is admissible: $h(n) \leq h^*(n)$ for all $n$	Not guaranteed — can find a suboptimal solution by following a misleading heuristic down a cheaper-looking but more expensive path
Completeness	Complete in finite spaces — will always find a solution if one exists (with a consistent heuristic in graph search)	Not complete in general — can get stuck in infinite loops following a heuristic that never reaches the goal
Speed	Slower than Greedy — expands more nodes because it balances cost-so-far against the heuristic estimate	Faster in practice — aggressively follows the heuristic and usually reaches the goal quickly, often expanding far fewer nodes
Memory Usage	High — stores all generated nodes in memory (exponential in worst case: $O(b^d)$ where $b$ is branching factor and $d$ is solution depth)	High — also stores all generated nodes, same worst-case as A*; can be worse in practice if the heuristic leads it deep into a bad branch
Heuristic Quality Impact	A perfect heuristic ( $h(n) = h^(n)$ ) makes A expand only nodes on the optimal path — zero wasted work. A poor but admissible $h(n)$ degrades toward Uniform Cost Search	A perfect heuristic makes Greedy expand only nodes directly toward the goal — extremely fast. A poor heuristic causes it to explore long detours with no correction mechanism
Relation to Other Algorithms	When $h(n) = 0$ for all nodes, A* reduces exactly to Uniform Cost Search (UCS)	When $h(n) = 0$ for all nodes, Greedy Best-First reduces exactly to BFS (if costs are uniform) or selects arbitrarily
Typical Use Case	Navigation, pathfinding in games (e.g., finding shortest route on a map where correctness matters)	Puzzles or planning where a fast approximate solution is acceptable and the heuristic is highly reliable

Complexity Showdown

Training Time

A*:N/A — search algorithms have no training phase

Greedy:N/A — search algorithms have no training phase

Neither A* nor Greedy Best-First has a training phase. Complexity is measured in terms of nodes expanded during the search.

Prediction Time

A*:

O(b^d)

worst case —

b

is branching factor,

d

is solution depth; with a perfect heuristic, approaches

O(d)

Greedy:

O(b^m)

worst case —

m

is the maximum depth of the search space; typically far fewer nodes expanded in practice

Greedy Best-First expands far fewer nodes on average by aggressively following the heuristic. A* expands more nodes to ensure optimality — it backtracks away from expensive paths even if the heuristic looks promising. In the worst case both are exponential, but Greedy's practical node count is often orders of magnitude smaller.

Space Complexity

A*:

O(b^d)

— must keep all frontier and explored nodes in memory

Greedy:

O(b^m)

— same structure; can be worse if the heuristic leads deep into a dead end

Both algorithms store all generated nodes in memory. Neither has a structural memory advantage over the other — memory is the primary practical limitation of both, which is why IDA* and memory-bounded variants exist.

When To Use Which?

Use A* when:

✓You need the optimal (lowest-cost) solution — A* is the standard go-to algorithm when path cost matters and you cannot accept a suboptimal answer.
✓You have an admissible heuristic available — A* is only as good as its heuristic. Without one, it degrades to Uniform Cost Search, which is still optimal but slower.
✓The problem space is finite or the solution is guaranteed to exist — A* is complete and will find the solution, not just an approximation of it.
✓You are doing pathfinding in maps, games, or robotics — A* is the industry standard for grid-based navigation precisely because it balances optimality and speed.

Use Greedy Best-First when:

✓Speed matters more than optimality — Greedy Best-First typically reaches a solution by exploring far fewer nodes than A*, at the cost of possibly finding a longer path.
✓Your heuristic is highly accurate and reliable — if $h(n) \approx h^*(n)$ for most nodes, Greedy will race to a near-optimal solution extremely quickly.
✓The problem space is large and memory is constrained — by following the heuristic aggressively, Greedy avoids expanding large regions of the search space.
✓A good-enough solution is acceptable — in real-time systems or games where decisions must be made in milliseconds, Greedy's speed advantage is often worth the optimality sacrifice.

Common Exam Traps

⚠️

Saying Greedy Best-First is optimal if the heuristic is admissible

Admissibility only guarantees optimality for A*, not Greedy Best-First. Greedy ignores $g(n)$ entirely — even with a perfect admissible heuristic, it can still take a suboptimal path if a shorter-looking detour exists. Admissibility is A*'s condition, not Greedy's.

⚠️

Confusing $f(n)$ , $g(n)$ , and $h(n)$ under exam pressure

$g(n)$ = cost already paid to reach $n$ from the start (exact). $h(n)$ = estimated cost from $n$ to the goal (heuristic). $f(n) = g(n) + h(n)$ = total estimated cost of the path through $n$ . Greedy uses $f(n) = h(n)$ only. A* uses the full $f(n) = g(n) + h(n)$ . Writing this cleanly on an exam shows you understand the core distinction.

⚠️

Assuming A* is always slower than Greedy Best-First in terms of nodes expanded

With a near-perfect heuristic, A* expands almost the same nodes as Greedy and still guarantees optimality. With a poor heuristic, A* expands more nodes than Greedy but finds the correct answer. Greedy can sometimes expand more nodes than A* by going deep into a misleading branch and backtracking.

⚠️

Thinking consistency implies admissibility but not vice versa

It is the other way around: consistency (monotonicity) implies admissibility, but admissibility does not imply consistency. A consistent heuristic satisfies $h(n) \leq c(n, n') + h(n')$ for every edge $(n, n')$ with cost $c$ . Consistency is required for A* to be optimal in graph search (where nodes can be revisited). Admissibility alone is sufficient only in tree search.

⚠️

Saying Greedy Best-First is complete

Greedy Best-First is not complete in general. It can loop forever in a graph if the heuristic keeps pointing toward a cycle. Without a visited-node check, it will revisit nodes indefinitely. Even with a visited-node check, it may fail to find a solution that exists down a path with a temporarily worse heuristic value.

Final Verdict

A* is the right choice whenever you need the optimal solution and have an admissible heuristic. Greedy Best-First is the right choice when you need speed and can tolerate a suboptimal answer. Think of it this way: A* is a careful navigator who accounts for every step taken; Greedy is an impatient one who always heads toward where the goal looks closest, sometimes taking a longer route as a result.

A* Search

Try the A* Solver →Read A* Theory Guide

Greedy Best-First Search

Try the Greedy Solver →Read Greedy Theory Guide