1. Best-First Search

Best-first search is the foundational strategy underlying all informed graph search algorithms in artificial intelligence. Unlike uninformed methods (breadth-first, depth-first, Dijkstra), which explore the graph without any knowledge about the goal's location, best-first search uses a heuristic evaluation function to prioritise nodes that appear more promising, steering the search toward the goal and reducing wasted exploration. Nilsson ¹ introduced the central framework and Russell and Norvig ² give its modern treatment as the template from which A*, beam search, and many planning algorithms are derived.

The term best-first does not refer to a single algorithm but to a class of algorithms: any method that maintains a priority queue of candidate nodes and always expands the one ranked highest by some evaluation criterion is a best-first search. The classic and simplest member of this class is greedy best-first search, which evaluates nodes using only the heuristic estimate \(h(n)\) of distance to the goal, ignoring the cost already paid to reach \(n\). Its more powerful relative, A* (see A* Search), adds the past cost to obtain the exact evaluation function \(f(n) = g(n) + h(n)\), recovering optimality guarantees that greedy best-first search sacrifices.

1.1 Mathematical Foundation

1.1.1 Graph and Notation

The search operates on a directed graph \(G = (V, E)\) where \(V\) is the set of nodes (states) and \(E \subseteq V \times V\) is the set of directed edges (transitions). Each edge \((n, n')\) carries a non-negative cost \(c(n, n') \geq 0\).

1.1.2 The Evaluation Function

Greedy best-first search assigns each node \(n\) a priority score equal to the heuristic estimate alone:

where \(h(n)\) is any function \(V \to [0, \infty)\) that estimates the cost of the cheapest path from \(n\) to the goal \(g\). The open list is a min-priority queue ordered by \(f_{\text{greedy}}\), so the node appearing closest to the goal by the heuristic's measure is always expanded next.

This single-mindedness is both the strength and the weakness of greedy best-first. When \(h(n)\) is accurate, the algorithm cuts a near-straight path to the goal. When \(h(n)\) is misleading — underestimating the difficulty of a region — the algorithm confidently walks into a dead end and must backtrack, potentially exploring far more nodes than an uninformed search would.

1.1.3 Heuristic Design

The practical behaviour of any best-first algorithm is entirely determined by \(h(n)\). Pearl ³ systematically analyses the relationship between heuristic accuracy and search cost, showing that the expected number of node expansions grows polynomially with problem size when \(h(n) \approx h^*(n)\), but exponentially when \(h\) is weak. Three properties of heuristics are particularly important:

Admissibility. A heuristic is admissible if it never overestimates:

Admissibility is not required for greedy best-first search — only for A* to guarantee optimality — but an inadmissible heuristic can cause greedy best-first to follow even more misleading paths.

Dominance. Heuristic \(h_2\) dominates \(h_1\) if \(h_2(n) \geq h_1(n)\) for all \(n\) while both remain admissible. A dominant heuristic is always preferable: it expands strictly fewer nodes without losing optimality ².

Common examples. For grid pathfinding with only horizontal and vertical moves, the Manhattan distance

is admissible (it equals the true cost when the path is unobstructed) and dominates the trivial zero heuristic. Here \(r_n, c_n\) are the row and column of node \(n\), and \(r_g, c_g\) those of the goal. For free Euclidean movement the straight-line distance \(h_{\text{Euclidean}}(n) = \sqrt{(r_n - r_g)^2 + (c_n - c_g)^2}\) is a natural admissible heuristic.

1.2 The Algorithm

1.2.1 Procedure

Greedy best-first search maintains:

• Open list \(\mathcal{O}\): a min-priority queue of nodes seen but not yet expanded, keyed by \(h(n)\).
• Closed list \(\mathcal{C}\): the set of nodes already expanded (to prevent re-expansion).
• Parent map \(\pi\): records the predecessor of each node on the path currently known to reach it, enabling path reconstruction.

Starting with \(\mathcal{O} = \{s\}\) and \(\mathcal{C} = \emptyset\), the algorithm iterates:

1. If \(\mathcal{O}\) is empty, terminate — no path exists.
2. Remove \(n = \arg\min_{v \in \mathcal{O}}\, h(v)\) from \(\mathcal{O}\).
3. If \(n = g\), reconstruct the path via \(\pi\) and return it.
4. Add \(n\) to \(\mathcal{C}\).
5. For each successor \(n'\) of \(n\) with edge \((n, n') \in E\):
   • If \(n' \in \mathcal{C}\), skip (already expanded).
   • If \(n' \notin \mathcal{O}\), insert \(n'\) into \(\mathcal{O}\) and record \(\pi(n') = n\).
6. Go to step 1.

1.2.2 Loop Invariant

At the start of each iteration the following invariant holds:

Every node \(n \in \mathcal{O}\) has been reachable from \(s\) via at least one path, and every node \(n \in \mathcal{C}\) has already been expanded — all its successors have been generated and inserted into \(\mathcal{O}\) if not previously seen.

This invariant ensures that if a path to the goal exists and all reachable nodes are eventually inserted into \(\mathcal{O}\), the goal will eventually be removed and returned. However, the path returned is not guaranteed to be the cheapest one, because the algorithm may have reached the goal via a high-cost route that happened to pass through nodes with low \(h\)-values.

1.2.3 Comparison with A*

The only algorithmic difference between greedy best-first and A* is the priority key:

Dropping \(g(n)\) from the priority makes greedy best-first faster in practice — it expands far fewer nodes when the heuristic is good — at the cost of the optimality guarantee. When reaching the goal quickly matters more than finding the cheapest path (real-time games, approximate planning), greedy best-first is often the right trade-off ².

1.3 Completeness and Optimality

1.3.1 Completeness

Greedy best-first search is complete on finite graphs when a visited set (the closed list \(\mathcal{C}\)) is maintained: every node can be reached in finitely many expansions, and duplicate detection ensures no node is expanded twice, so the algorithm must terminate.

On infinite graphs or graphs without duplicate detection it may cycle indefinitely. In the pathological case where a low-\(h\) region forms a sink — nodes that look close to the goal but are surrounded by obstacles — the algorithm will fill \(\mathcal{O}\) with nodes in that region and never escape without explicit backtracking.

1.3.2 Optimality: Why It Fails

Consider the following scenario: the goal \(g\) is reachable by two paths. Path A has total cost 5 but passes through nodes with large \(h\)-values. Path B has total cost 20 but its intermediate nodes all have small \(h\)-values (they are physically close to the goal but separated from it by an obstacle). Greedy best-first will always prefer nodes on Path B, and will find the goal via the expensive route. Neither tie-breaking nor admissibility of \(h\) prevents this: the algorithm has no information about costs already paid.

Formally, optimality requires that the first time the goal is extracted from the open list its associated path is cheapest. In A* this is guaranteed by the monotone non-decreasing property of \(f = g + h\) along any path under a consistent heuristic. In greedy best-first, \(f = h\) has no such property and the ordering of the open list can be completely unrelated to path cost ³.

1.4 Variants and Extensions

Beam search is best-first with a fixed-width open list: at each step only the \(W\) most promising nodes are retained, and the rest are discarded, bounding memory to \(O(W \cdot b)\). This trades completeness and optimality for speed and memory efficiency, and is widely used in machine translation and speech recognition.

A* (see A* Search) recovers optimality by replacing \(h(n)\) with \(g(n) + h(n)\), and additionally proves that with an admissible heuristic no other algorithm exploring the same nodes can do better ⁴.

Weighted A* interpolates between greedy best-first and A by using \(f(n) = g(n) + w \cdot h(n)\) for \(w \geq 1\). At \(w = 1\) this is standard A; as \(w \to \infty\) it approaches greedy best-first. The returned path costs at most \(w \cdot f^*\), where \(f^*\) is the optimal solution cost ².

Bidirectional best-first search runs two simultaneous greedy searches — one forward from \(s\), one backward from \(g\) — and halts when the two frontiers meet, potentially halving the depth explored.

1.5 Complexity

In the worst case, greedy best-first search with branching factor \(b\) and maximum depth \(m\) generates at most \(O(b^m)\) nodes in both time and space. The open list holds all generated but unexpanded nodes simultaneously, so memory is the binding constraint in large state spaces.

When the heuristic is well-informed, the effective branching factor \(b^* < b\) is substantially smaller. Pearl ³ shows that for a heuristic with relative error \(\epsilon\) (i.e. \(h(n) \geq (1-\epsilon) h^*(n)\)), the expected number of expansions grows as \(O(n^\epsilon)\) — polynomial rather than exponential in the path length.

1.6 Limitations and Challenges

Optimality is not guaranteed. Because the cost already paid (\(g(n)\)) is ignored, the algorithm may reach the goal via a long, expensive detour. In applications where solution cost matters — route planning, shortest-path problems — greedy best-first is insufficient on its own.

Heuristic design is domain-specific and non-trivial. A heuristic that is too weak (e.g., constant \(h(n) = 0\)) degrades greedy best-first to breadth-first search; one that severely overestimates will cause the algorithm to behave erratically, expanding nodes that are actually far from the goal. There is no general-purpose recipe for constructing tight heuristics ³.

Memory can become a bottleneck. In large state spaces the open list may grow to hold millions of nodes. Beam search variants cap memory but sacrifice completeness and optimality. A* with consistent heuristics spends memory more efficiently by never re-expanding closed nodes, but still requires \(O(b^d)\) space.

Cycles and repeated states. Without a closed list, greedy best-first in cyclic graphs will loop indefinitely. Maintaining the closed list adds \(O(|V|)\) memory and \(O(\log |V|)\) per-expansion overhead for lookup.

1.7 Interactive Demonstration

The animation below runs greedy best-first search on the same 14 × 10 grid used in the A demonstration, using Manhattan distance as \(h(n)\). Because only \(h(n)\) drives the priority queue, the algorithm makes a beeline toward the goal but can be led astray by obstacles, sometimes finding a longer path than A would. Compare by running both demos on the same map.

The numbers along the top and left edges are column and row indices. Start S is at (row 1, col 1); goal G is at (row 8, col 12). The initial \(h\)-value of S is:

Each expanded cell shows its \(h(n)\) value. Use Step to advance one expansion or Play to run continuously.