Best First Search in AI: How It Works, Pseudocode, and Comparison With A Comparison

Quick Answer

Best First Search is an informed (heuristic-driven) search strategy in artificial intelligence that expands the node it judges most promising at each step, instead of expanding nodes strictly by depth (as in Depth-First Search) or by insertion order (as in Breadth-First Search). It does this by keeping a priority queue of frontier nodes ordered by an evaluation function f(n), and always popping the node with the best (typically lowest) f-value. Greedy Best First Search and A* Search are the two most important members of this family: Greedy Best First Search uses f(n) = h(n) and is fast but not guaranteed optimal, while A* uses f(n) = g(n) + h(n) and is both complete and optimal when the heuristic is admissible.

Key Highlights of Best First Search in AI

• Best First Search generalizes uninformed search by adding a heuristic function h(n) that estimates the cost from any node to the goal, letting the algorithm prioritize which node to expand next rather than expanding nodes blindly.
• The algorithm relies on two core data structures: an OPEN list (a priority queue of frontier nodes ordered by f-value) and a CLOSED list (already-expanded nodes), a structure that traces back to Doran and Michie's 1966 "Graph Traverser" program at the University of Edinburgh.
• Greedy Best First Search (f(n) = h(n)) is neither complete nor optimal and can get trapped following a locally attractive but globally poor path, while A* Search (f(n) = g(n) + h(n)) is optimal and complete whenever the heuristic is admissible (never overestimates true cost).
• Worst-case time and space complexity for best-first search is O(b^m), where b is the branching factor and m is the maximum search depth, though A* with a good heuristic performs far better in practice than this bound suggests.
• On the classic Romania route-finding problem (from AIMA, Russell and Norvig's widely used AI textbook), Greedy Best First Search reaches Bucharest quickly using straight-line distance as h(n), but takes a longer route than A*, which accounts for both the distance already traveled and the estimated remaining distance.
• Modern GPS navigation, video game pathfinding, and robot motion planning all rely on best-first search variants (mainly A* and its extensions) because they scale to enormous graphs while still finding good, and often provably optimal, paths.

What Is Best First Search in AI

In artificial intelligence, a search problem is typically defined by a start state, a set of possible actions that move between states, a goal test, and (often) a cost associated with each action. Search algorithms explore the resulting state space, represented as a graph or tree, to find a sequence of actions from the start to a goal.

Search strategies fall into two broad families. Uninformed (blind) search algorithms, such as Breadth-First Search and Depth-First Search, have no information about which unexplored node is more likely to lead to the goal; they explore based purely on the structure of the search tree. Informed (heuristic) search algorithms, by contrast, use problem-specific knowledge, encoded as a heuristic function h(n), to estimate how close a given node n is to the goal, and use that estimate to guide exploration.

Best First Search is the general name for the class of informed search algorithms that always expand the node currently judged "best" according to some evaluation function f(n), where the frontier (the set of nodes discovered but not yet expanded) is maintained as a priority queue ordered by f(n). The specific definition of f(n) determines which particular algorithm you get. When f(n) = h(n) alone, the result is Greedy Best First Search. When f(n) = g(n) + h(n), where g(n) is the actual cost from the start node to n, the result is A* Search. Because A* and Greedy Best First Search share this "always expand the best frontier node" structure, both are correctly described as best-first search algorithms, and in practice "best-first search" and "greedy best-first search" are sometimes used loosely to mean the same thing, which is a common source of confusion worth clearing up early.

This distinction matters directly for anyone building toward a career in applied AI or machine learning; understanding how search and optimization strategies trade off speed against guaranteed correctness is foundational material in most structured Artificial Intelligence certification training curricula, since the same trade-off reappears constantly in planning, scheduling, and optimization problems well beyond simple pathfinding.

Origins: From the Graph Traverser to Modern Heuristic Search

The idea of guiding search with an evaluation function is not new. One of the earliest documented implementations is the "Graph Traverser" program, built by J. E. Doran and Donald Michie at the Experimental Programming Unit, University of Edinburgh, and described in their 1966 paper "Experiments with the Graph Traverser Program," published in Proceedings of the Royal Society of London A. The Graph Traverser evaluated intermediate states according to how many features they shared with the goal state, using an evaluation function to decide which state to expand next, which is precisely the mechanism modern best-first search still uses.

That early work set the stage for more rigorous heuristic search theory through the 1960s and 1970s, culminating in the formalization of A* Search by Peter Hart, Nils Nilsson, and Bertram Raphael in 1968, and later the systematic treatment given in Stuart Russell and Peter Norvig's textbook "Artificial Intelligence: A Modern Approach" (AIMA), which remains the standard reference most university AI courses, including those at UC Berkeley and MIT, build their informed search material around.

How Best First Search Works

Best First Search operates on a graph (or an implicit tree generated by expanding states one action at a time) and maintains two collections of nodes:

• OPEN list (the frontier): a priority queue holding nodes that have been generated but not yet expanded, ordered by their f-value so the node with the best score is always at the front.
• CLOSED list (the explored set): nodes that have already been expanded, kept so the algorithm does not waste time re-expanding them (in graph search) or, in some variants, purely for bookkeeping and path reconstruction.

At a high level, the algorithm proceeds as follows:

1. Place the start node on OPEN with its initial f-value.
2. Loop: if OPEN is empty, report failure (no solution exists).
3. Remove the node with the lowest f-value from OPEN; call it n.
4. If n is a goal state, reconstruct the path from the start to n (using stored parent pointers) and return it as the solution.
5. Otherwise, move n to CLOSED and generate its successors (the states reachable from n via a single action).
6. For each successor, compute its f-value. If it is not already in OPEN or CLOSED, add it to OPEN. If it is already present with a worse recorded cost, update its cost and parent pointer (this update step is what allows A* to correct an earlier suboptimal path estimate).
7. Return to step 2.

The entire behavior of the algorithm, and specifically whether it behaves like Greedy Best First Search or like A*, is determined by how f(n) is defined:

• Greedy Best First Search: f(n) = h(n). The algorithm always moves toward the node that looks closest to the goal right now, completely ignoring how much it already cost to get there.
• A* Search: f(n) = g(n) + h(n). The algorithm balances the cost already incurred (g) against the estimated remaining cost (h), which is what allows it to avoid greedily committing to a path that looks good locally but is expensive overall.
• Uniform Cost Search (for comparison): f(n) = g(n), i.e., h(n) = 0 for all n. This is technically a degenerate case of best-first search with no heuristic guidance at all, and it behaves identically to Dijkstra's algorithm on a graph with non-negative edge weights.

Best First Search Pseudocode

The following pseudocode describes generalized best-first search; substituting the definition of f(n) turns it into Greedy Best First Search or A* Search.

function BEST-FIRST-SEARCH(problem, f):
    node <- NODE(state = problem.INITIAL, path_cost = 0)
    frontier <- a priority queue ordered by f, initially containing node
    reached <- a lookup table, with one entry: {problem.INITIAL: node}

    while frontier is not empty:
        node <- POP node with lowest f-value from frontier
        if problem.IS-GOAL(node.state):
            return node   // success: reconstruct path via parent pointers

        for each child in EXPAND(problem, node):
            s <- child.state
            if s is not in reached OR child.path_cost < reached[s].path_cost:
                reached[s] <- child
                add child to frontier with priority f(child)

    return failure  // frontier exhausted, no solution

function EXPAND(problem, node):
    s <- node.state
    for each action in problem.ACTIONS(s):
        s_next <- problem.RESULT(s, action)
        cost <- node.path_cost + problem.ACTION-COST(s, action, s_next)
        yield NODE(state = s_next, parent = node, path_cost = cost)

To get Greedy Best First Search, define f(node) = h(node.state). To get A* Search, define f(node) = node.path_cost + h(node.state), which is exactly g(n) + h(n). This structural similarity is why implementations of A* and Greedy Best First Search in most textbooks and libraries differ by a single line: the definition of the priority function passed to an otherwise identical frontier-management routine.

Worked Example: Finding a Route on the Romania Map

The most widely used worked example for best-first search comes from Russell and Norvig's AIMA textbook: finding a driving route from Arad to Bucharest on a simplified map of Romania. Each city is a node, each road is an edge weighted by real driving distance, and the heuristic h(n) used is the straight-line ("as the crow flies") distance from a city to Bucharest. A small excerpt of that straight-line distance table is:

Greedy Best First Search, starting at Arad: Arad's neighbors include Sibiu, Timisoara, and Zerind. Greedy search picks whichever neighbor has the lowest h-value, ignoring road distance entirely. Sibiu (h = 253) looks far more promising than Timisoara or Zerind, so it is expanded next. From Sibiu, one neighbor is Fagaras (h = 178), which looks better than the alternative route through Rimnicu Vilcea and Pitesti, so greedy search commits to Fagaras. From Fagaras, Bucharest (h = 0) is reachable directly, so the algorithm terminates having found the path Arad, Sibiu, Fagaras, Bucharest. This path is found quickly, but it is not the shortest one: the actual road distance via Sibiu, Rimnicu Vilcea, and Pitesti is shorter, a discrepancy Greedy Best First Search cannot detect because it never considers g(n), the cost already paid.

A* Search, starting at Arad: A* evaluates f(n) = g(n) + h(n) at every step, so it keeps both the accumulated road distance and the straight-line estimate in view. Early on this can make A* favor the Sibiu, Rimnicu Vilcea, Pitesti branch, because even though Pitesti's straight-line distance to Bucharest is worse than Fagaras's in isolation, the combined g + h score along that branch turns out lower once real driving distances are added in. A* ultimately returns the truly shortest path, Arad, Sibiu, Rimnicu Vilcea, Pitesti, Bucharest, because it never commits to a branch until the priority queue proves no better-scoring alternative remains.

This example illustrates the core trade-off of the entire best-first search family in one comparison: Greedy Best First Search reaches a goal fast by trusting the heuristic completely, while A* takes the accumulated cost into account and is guaranteed to find the optimal path whenever the heuristic is admissible.

Greedy Best First Search vs A* Search

Because both algorithms are instances of best-first search, the difference comes down entirely to the evaluation function and its consequences:

• What each ignores: Greedy Best First Search ignores the cost already paid to reach a node (g(n)). A* ignores nothing; it uses both g(n) and h(n).
• Optimality: Greedy Best First Search is not guaranteed to find the optimal (lowest-cost) solution, because a node with a very attractive h-value can sit at the end of an expensive path. A* is guaranteed optimal when the heuristic function is admissible (never overestimates the true remaining cost), because the algorithm cannot terminate on a goal node until it can prove, from the priority queue, that no cheaper path remains unexplored.
• Completeness: Both algorithms are complete on finite graphs with non-negative edge costs; on infinite or unbounded state spaces, Greedy Best First Search can fail to terminate if it repeatedly follows an unproductive heuristic gradient, while A* still terminates given a finite state space.
• Speed: In practice, Greedy Best First Search often expands fewer nodes and runs faster than A*, precisely because it commits early and does not verify optimality, which is why some applications (e.g., real-time game AI where "good enough, fast" beats "optimal, slow") deliberately choose greedy search or a weighted hybrid.
• Memory: Both keep the entire frontier and (in graph search) explored set in memory, so both share the same worst-case space complexity, though A* frontiers can grow larger in practice because it explores more branches before committing.

Heuristic Function Properties: Admissibility and Consistency

The theoretical guarantees of A* Search depend entirely on properties of the heuristic function h(n), so understanding these two properties is essential to using best-first search correctly rather than just running it.

Admissibility

A heuristic h(n) is admissible if it never overestimates the true cost of reaching the goal from n; formally, h(n) ≤ h*(n) for every node n, where h*(n) is the actual optimal cost from n to the nearest goal. Straight-line distance is admissible for road-network routing because a straight line is always the shortest possible path between two points, so it can never exceed the true (necessarily longer, road-following) driving distance. Admissibility is the minimum requirement for A* Search (using tree search) to be guaranteed optimal.

Consistency (Monotonicity)

A heuristic h(n) is consistent if, for every node n and every successor n' generated by an action with step cost c(n, a, n'), the estimated cost satisfies h(n) ≤ c(n, a, n') + h(n'). In plain terms, the heuristic's estimate can never drop by more than the actual cost of the step just taken. Consistency is a stronger condition than admissibility: every consistent heuristic is admissible, but not every admissible heuristic is consistent. Consistency matters practically because it guarantees that the f-values along any path A* explores are non-decreasing, which in turn guarantees that A* graph search (the version that also tracks a CLOSED list to avoid re-expanding nodes) finds the optimal solution the first time it reaches any given node, without ever needing to revisit and revise that node's cost later.

Time and Space Complexity

Formally bounding best-first search's performance requires two parameters: the branching factor b (the maximum number of successors any node can have) and the maximum solution depth or path length m (or d, when specifically referring to the depth of the shallowest goal).

• Worst-case time complexity: O(b^m). In the worst case, a poorly informed heuristic provides no better guidance than blind search, so the algorithm may need to examine an exponential number of nodes just as Breadth-First Search would.
• Worst-case space complexity: O(b^m), because every generated node may need to be held in the OPEN or CLOSED list simultaneously in the worst case. This is the single biggest practical limitation of best-first search family algorithms (including A*) on very large state spaces: memory, not time, is usually what runs out first.
• Practical (average-case) behavior: With a well-designed, informative heuristic, both algorithms typically expand far fewer nodes than the worst-case bound suggests. The tighter the heuristic tracks the true remaining cost, the closer A* comes to only exploring nodes that lie on or very near the optimal path, a property sometimes summarized by saying A* is "optimally efficient" among admissible search algorithms that use the same heuristic information, meaning no other algorithm with access to the same h(n) is guaranteed to expand fewer nodes while still finding the optimal solution.

Because raw memory use is often the practical bottleneck, several memory-bounded variants exist in the research literature, including Iterative Deepening A* (IDA*), Simplified Memory-Bounded A* (SMA*), and, for the specific weaknesses of greedy best-first search under certain heuristic conditions, algorithms explored in academic work such as Heusner, Keller, and Helmert's analysis of greedy best-first search's search behavior, published at the 2017 Symposium on Combinatorial Search and extended in a 2018 IJCAI paper on the best-case and worst-case behavior of the algorithm.

Comparison Table: Best First Search vs BFS, DFS, Dijkstra, and A*

Advantages and Disadvantages

Advantages

• Generally much faster in practice than uninformed search strategies like BFS or DFS, because the heuristic actively steers the search toward the goal instead of exploring blindly.
• Flexible: by simply changing the definition of f(n), the same underlying algorithm produces Greedy Best First Search, A*, or Uniform Cost Search, making it a unifying framework rather than one rigid procedure.
• When paired with an admissible heuristic (A* specifically), the algorithm is guaranteed to return the optimal solution, combining speed with a correctness guarantee that pure greedy methods cannot offer.
• Well suited to large, weighted graphs, such as road networks or game maps, where uninformed search would be computationally impractical.

Disadvantages

• Worst-case time and space complexity remain exponential, O(b^m), so performance depends heavily on how good the heuristic actually is; a poor or uninformative heuristic can degrade performance close to uninformed search.
• Greedy Best First Search specifically is not optimal and is not even guaranteed to find a solution efficiently if the heuristic is misleading, since it can be drawn toward a dead end that merely looks close to the goal.
• Designing a good heuristic function is itself a nontrivial engineering problem; a heuristic that is too loose provides little guidance, while one that is not admissible breaks A*'s optimality guarantee entirely.
• Memory consumption can become the practical limiting factor before time does, since both OPEN and CLOSED lists must be kept for the duration of the search on large state spaces.

Real-World Applications

Best-first search algorithms, especially A* and its many derivatives, underpin a wide range of production systems that most people interact with regularly:

• GPS and navigation systems: Modern mapping services run best-first search variants over road networks containing hundreds of millions of nodes, with heuristics that combine straight-line distance with historical traffic patterns, road classifications, and live conditions to compute routes across continental-scale graphs in real time.
• Video game AI: Non-player characters in strategy games and role-playing games commonly use A* or a variant to navigate game maps, with heuristics blending geometric distance and terrain cost so characters prefer roads or open ground over difficult terrain.
• Robotics and autonomous vehicles: Robots plan movement through configuration space, the abstract space representing all possible positions and orientations of the robot, using best-first search to find collision-free paths while estimating physical distance to a target configuration.
• Puzzle solving: Classic AI puzzles such as the 8-puzzle and 15-puzzle are standard benchmarks for evaluating best-first search and A* heuristics (e.g., counting misplaced tiles, or summing Manhattan distances of each tile from its goal position).
• Logistics, scheduling, and planning: Warehouse robotics and automated planning systems apply heuristic search to sequence tasks or movements efficiently while avoiding collisions and dead ends.

For professionals building toward roles that involve designing or evaluating these systems, understanding classical search algorithms is typically a prerequisite before moving into modern machine learning and generative AI techniques; Simpliaxis's guide on how to become an AI engineer outlines where foundational algorithms like this fit into a broader AI career roadmap, and learners often pair that theoretical grounding with a structured Introduction to AI and Machine Learning course before progressing to applied data science work such as Simpliaxis's Data Science with Python certification training.

Implementation Notes and Common Mistakes

• Tree search vs graph search: A tree-search implementation of best-first search (no CLOSED list, no duplicate checking) can re-expand the same state repeatedly on graphs with cycles, wasting time or even failing to terminate. Graph search, which checks whether a state has already been reached, is almost always the correct choice for real-world state spaces.
• Updating costs on rediscovery: If a node already in OPEN is reached again via a cheaper path, its stored cost and parent pointer must be updated (and its position in the priority queue re-adjusted); skipping this step is a common bug that silently breaks A*'s optimality guarantee.
• Heuristic must match the problem's cost units: If g(n) is measured in kilometers but h(n) is estimated in some unrelated unit (or in a different distance metric that isn't a true lower bound), the sum f(n) = g(n) + h(n) becomes meaningless, and A*'s guarantees no longer hold.
• Ties in the priority queue: Many implementations break ties between equal f-values by preferring nodes with a higher g-value (i.e., nodes deeper into the search), which in practice reduces the number of nodes expanded, since it favors making progress toward the goal over hovering near the start.
• Verifying admissibility before trusting optimality: Before claiming an implementation of A* returns optimal paths, confirm the specific heuristic in use is genuinely admissible for that problem; a heuristic that works for one cost model (e.g., pure distance) may silently stop being admissible if the cost model changes (e.g., adding time penalties for turns or traffic).

Key Takeaways

• Best First Search is a family of informed search algorithms that expand the frontier node with the best evaluation function score f(n), using a priority queue rather than a plain FIFO or LIFO structure.
• Greedy Best First Search (f(n) = h(n)) is fast but not optimal; A* Search (f(n) = g(n) + h(n)) adds the accumulated path cost back into the decision and is optimal whenever the heuristic is admissible.
• The theoretical guarantees behind A* rest on two heuristic properties: admissibility (never overestimating true cost) and the stronger property of consistency (estimates never drop by more than the actual step cost).
• Worst-case time and space complexity for the whole family is O(b^m), but a well-designed heuristic routinely brings real-world performance far below that bound.
• The Romania map example from Russell and Norvig's AIMA textbook remains the standard way to see, side by side, how greedy heuristic-only decisions can diverge from the truly optimal path that A* finds.
• Best-first search variants, chiefly A*, power everyday systems including GPS navigation, video game pathfinding, and robotic motion planning, making this one of the most practically important algorithms taught in any foundational AI curriculum.

Schema Recommendation and Verification Notes

Schema recommendation: Implement Article structured data for the main content and FAQPage structured data for the Frequently Asked Questions section above, matching the questions and answers exactly as written.

Facts that could not be independently verified in this research pass: the exact 37% greedy-vs-A* speed differential figure sometimes cited in secondary sources was not traced to a specific, reproducible academic benchmark and is therefore omitted from the body of this article; readers should treat any specific speed-multiplier claims for greedy search versus A* as workload-dependent rather than universal. The precise founding date and authorship of the formal term "best-first search" as distinct from "Graph Traverser" is attributed here to the general historical record around Doran and Michie's 1966 paper, but this article does not claim that paper used the exact phrase "best-first search" itself, since that specific terminological detail could not be confirmed with full certainty from available sources during this research pass. All numeric straight-line-distance values in the Romania map table are drawn from the widely reproduced AIMA textbook example and should be verified against the current edition of Russell and Norvig's "Artificial Intelligence: A Modern Approach" if used in a context requiring textbook-level precision.