Best-First Search: Complete Search Algorithm Guide

1. Introduction and Core Concepts

Best-first search is a fundamental informed search algorithm that powers everything from GPS navigation to game AI and network routing. Unlike uninformed algorithms that explore blindly, best-first search uses domain-specific knowledge to prioritize the most promising paths first, dramatically reducing the search effort required to reach a goal. It represents a family of algorithms rather than a single rigid procedure, unified by one core principle: always expand the node that appears best according to an evaluation function.

At its heart, best-first search is a graph traversal strategy that maintains a priority queue (often called the open list) of candidate nodes. Each node is assigned a score by an evaluation function, typically a heuristic function h(n) that estimates the cost or distance from that node to the goal. On each iteration, the algorithm removes the node with the lowest (best) score from the queue, checks if it is the goal, and if not, expands it by generating its successors and inserting them into the queue according to their scores. This greedy, opportunistic approach allows the search to be directed toward the goal instead of wasting time exploring irrelevant regions of the search space.

Understanding best-first search matters because it forms the conceptual foundation for many of the most important algorithms in artificial intelligence. Greedy best-first search, A* search, and beam search are all variants of the best-first search paradigm. The trade-offs it introduces — between speed and optimality, between completeness and memory efficiency — are central to algorithm design. For developers building intelligent systems, mastering best-first search provides the intuition needed to choose the right heuristic, balance exploration and exploitation, and design systems that are both efficient and reliable under real-world constraints.

What Makes a Search "Best-First"?

A search is considered best-first when its node selection is driven entirely by an evaluation function f(n) that ranks nodes. In the purest form, known as greedy best-first search, f(n) = h(n), where h(n) is the heuristic estimate. In more sophisticated variants like A*, f(n) = g(n) + h(n), combining the actual cost from the start g(n) with the heuristic estimate. The key distinction from breadth-first search (BFS) or depth-first search (DFS) is that best-first search is informed: it uses problem-specific knowledge to make decisions, while BFS and DFS are uninformed and follow a fixed order.

This informed nature is both its greatest strength and its greatest vulnerability. With a good heuristic, best-first search can find solutions exponentially faster than uninformed methods. With a poor or misleading heuristic, it can be led astray, exploring dead ends or even failing to find a solution that exists. The quality of the heuristic function is therefore the single most important factor in the performance of any best-first search implementation.

2. How It Works

Best-first search operates by maintaining two key data structures: an open list (priority queue) containing frontier nodes that have been discovered but not yet expanded, and a closed list (visited set) containing nodes that have already been expanded. The algorithm begins by inserting the start node into the open list with its heuristic value. It then enters a loop where it repeatedly extracts the node with the smallest evaluation score, moves it to the closed list, and expands it.

Expansion involves generating all successors (neighbors) of the current node. For each successor that has not been visited, the algorithm computes its evaluation score and inserts it into the open list. The priority queue ensures that the next node extracted is always the most promising among all discovered but unexpanded nodes, regardless of when it was discovered or its depth in the search tree. This global prioritization is what distinguishes best-first search from depth-first search, which always expands the most recently discovered node, and breadth-first search, which expands nodes in FIFO order.

The evaluation function is what gives best-first search its direction. A common choice is straight-line distance for pathfinding, number of misplaced tiles for the 8-puzzle, or estimated remaining cost for scheduling problems. The algorithm does not commit to a single path; instead, it can switch to a different branch at any time if that branch appears more promising. This flexibility allows it to backtrack efficiently without explicit backtracking logic — the priority queue naturally handles it.

The Role of the Heuristic Function

The heuristic function h(n) is an estimate of the cheapest cost from node n to the goal. It must be fast to compute, because it is evaluated for every generated node. An admissible heuristic never overestimates the true cost, which is crucial for optimality in algorithms like A*. A consistent (or monotonic) heuristic satisfies h(n) <= cost(n, n') + h(n') for every successor n' of n, which guarantees that f(n) is non-decreasing along any path and avoids re-expansions.

Designing a good heuristic requires balancing accuracy and computational cost. A perfect heuristic (h(n) equals true cost) would make best-first search go directly to the goal without any wasted expansion, but computing such a heuristic is usually as hard as solving the original problem. In practice, heuristics are approximations derived from relaxed versions of the problem, such as ignoring obstacles for pathfinding or using Manhattan distance on a grid.

Open List and Closed List Management

Efficient management of the open and closed lists is critical for performance. The open list is typically implemented as a binary heap (priority queue) to support O(log n) insertion and extraction. The closed list is usually a hash set for O(1) membership testing. Without a closed list, best-first search can cycle infinitely in graphs with loops, revisiting the same nodes repeatedly. With a closed list, each node is expanded at most once, though some variants allow re-expansion if a cheaper path is discovered.

3. Implementation

Implementing best-first search in Python is straightforward thanks to the heapq module, which provides an efficient binary heap implementation. The core pattern is consistent across variants: push nodes with their priority, pop the best node, check for goal, and push successors. The differences between variants lie in how the priority is computed and how visited nodes are handled.

The following implementation shows the canonical greedy best-first search. It uses only the heuristic value as priority, making it fast but not optimal. Note how the priority queue stores tuples of (heuristic, node, path) so that the heap is ordered by heuristic value. The visited set prevents redundant expansions and infinite loops in cyclic graphs.

import heapq

def greedy_best_first_search(graph, start, goal, heuristic):
    """
    Greedy Best-First Search implementation.
    graph: dict node -> list of (neighbor, cost)
    heuristic: dict node -> estimated cost to goal
    Returns path from start to goal if found.
    """
    open_list = []
    heapq.heappush(open_list, (heuristic[start], start, [start]))
    visited = set()

    while open_list:
        _, current, path = heapq.heappop(open_list)

        if current in visited:
            continue
        visited.add(current)

        if current == goal:
            return path

        for neighbor, _ in graph.get(current, []):
            if neighbor not in visited:
                # Priority is purely heuristic value
                heapq.heappush(open_list, (heuristic[neighbor], neighbor, path + [neighbor]))

        # Optional early exit if open_list empty
        if not open_list:
            break
    return None

While greedy best-first search is simple, it is not optimal and can be incomplete in some cases. A more robust variant is A* search, which is technically a best-first search where the evaluation function is f(n) = g(n) + h(n). A* combines the actual cost from the start with the heuristic estimate, guaranteeing optimality when the heuristic is admissible. The implementation below tracks both g and f scores and allows revisiting nodes if a cheaper path is found.

import heapq

def a_star_search(graph, start, goal, heuristic):
    """
    A* is a best-first search that uses f(n) = g(n) + h(n)
    g(n): actual cost from start to n
    h(n): heuristic estimate from n to goal
    """
    open_list = []
    # (f_score, g_score, node, path)
    heapq.heappush(open_list, (heuristic[start], 0, start, [start]))
    visited_cost = {start: 0}

    while open_list:
        f_score, g_score, current, path = heapq.heappop(open_list)

        if current == goal:
            return path, g_score

        for neighbor, cost in graph.get(current, []):
            new_g = g_score + cost
            # Only explore if we found cheaper path
            if neighbor not in visited_cost or new_g < visited_cost[neighbor]:
                visited_cost[neighbor] = new_g
                f_score = new_g + heuristic[neighbor]
                heapq.heappush(open_list, (f_score, new_g, neighbor, path + [neighbor]))
    return None

For problems defined on grids, such as maze solving or game maps, best-first search can be adapted to work with 2D coordinates. The heuristic is typically Manhattan distance or Euclidean distance, and successors are the four or eight neighboring cells. Obstacles are handled by checking grid values before insertion into the open list.

import heapq

def best_first_search_grid(grid, start, goal, heuristic_func):
    """
    Best-First Search on a 2D grid.
    grid: 2D list where 0 = free, 1 = obstacle
    heuristic_func: function to estimate distance
    """
    rows, cols = len(grid), len(grid[0])
    open_list = []
    heapq.heappush(open_list, (heuristic_func(start, goal), start, [start]))
    visited = set()

    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while open_list:
        _, current, path = heapq.heappop(open_list)

        if current in visited:
            continue
        visited.add(current)

        if current == goal:
            return path

        for dr, dc in directions:
            r, c = current[0] + dr, current[1] + dc
            # Check bounds and obstacle
            if 0 <= r < rows and 0 <= c < cols:
                if grid[r][c] == 0 and (r, c) not in visited:
                    h = heuristic_func((r, c), goal)
                    heapq.heappush(open_list, (h, (r, c), path + [(r, c)]))
    return None

def manhattan(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

When memory is constrained, beam search offers a memory-bounded variant of best-first search. Instead of keeping all frontier nodes, it keeps only the top k most promising nodes at each depth level, where k is the beam width. This sacrifices completeness and optimality for a fixed memory footprint, making it popular in natural language processing and speech recognition.

import heapq

def beam_best_first_search(graph, start, goal, heuristic, beam_width=2):
    """
    Beam Search: keeps only top-k promising nodes at each level.
    Trades completeness for memory efficiency.
    """
    # Each level holds at most beam_width nodes
    current_level = [(heuristic[start], start, [start])]

    visited = set([start])

    while current_level:
        next_level = []

        for _, node, path in current_level:
            if node == goal:
                return path

            for neighbor, _ in graph.get(node, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    h = heuristic[neighbor]
                    next_level.append((h, neighbor, path + [neighbor]))

        # Keep only best beam_width nodes
        next_level.sort(key=lambda x: x[0])
        # Slice with beam_width
        if len(next_level) > beam_width:
            next_level = next_level[:beam_width]

        current_level = next_level

    return None

4. Step-by-Step Example

To make best-first search concrete, consider a small road network where we want to travel from city A to city G. The graph has the following connections with travel costs: A connects to B (cost 2) and C (cost 3), B connects to D (cost 4) and E (cost 2), C connects to F (cost 5), D connects to G (cost 3), E connects to G (cost 4), and F connects to G (cost 2). The heuristic values estimating straight-line distance to G are: h(A)=6, h(B)=4, h(C)=4, h(D)=2, h(E)=1, h(F)=2, h(G)=0. Greedy best-first search will use only these heuristic values to decide which node to expand next.

Initialization: The open list starts as [(6, A)]. The closed list is empty. We pop A (the only node), mark it visited, and expand it. Its successors are B with h=4 and C with h=4. Both are inserted, so the open list becomes [(4, B), (4, C)]. Note that the actual travel costs from A are ignored — only the heuristic matters for ordering.

Iteration 1: We pop B (tie-breaking arbitrarily picks B before C). B is not the goal, so we expand it. Its successors are D (h=2) and E (h=1). The open list now contains [(1, E), (2, D), (4, C)]. The algorithm has already found a very promising node E with heuristic 1, so it will be explored next even though it is deeper in the tree than C.

Iteration 2: We pop E (h=1), the most promising node. Expanding E generates G (h=0). The open list becomes [(0, G), (2, D), (4, C)]. Iteration 3: We pop G (h=0) and recognize it as the goal. The algorithm returns the path A -> B -> E -> G with total actual cost 2+2+4=8. Interestingly, the optimal path is A -> B -> D -> G with cost 2+4+3=9 or A -> C -> F -> G with cost 3+5+2=10, so in this case greedy best-first search happened to find the cheapest path, but this is not guaranteed. If the heuristic had been misleading, it could have chosen a more expensive route.

Trace Table for the Example

The following trace summarizes the open list state at each step. Notice how the priority queue always surfaces the node with the smallest heuristic, allowing the search to jump between branches. This global ordering is the defining characteristic of best-first search and explains why it can be much faster than depth-first search, which would have committed to exploring all of B's subtree before ever considering C.

If we had used A* instead, the ordering would be by f(n) = g(n) + h(n). After expanding A, B would have f=2+4=6 and C would have f=3+4=7, so B would still be first. After expanding B, D would have f=6+2=8 and E would have f=4+1=5, so E would still be first. The behavior is similar in this small example, but in larger graphs with more misleading heuristics, A* is more robust because it balances actual cost with estimated cost, preventing the search from being fooled by an overly optimistic heuristic.

5. Complexity Analysis

The time and space complexity of best-first search depends heavily on the quality of the heuristic and the structure of the search space. In the worst case, with a completely uninformative heuristic (e.g., h(n)=0 for all n), best-first search degenerates to a form of breadth-first search and may explore the entire graph. In the best case, with a perfect heuristic, it goes straight to the goal without any backtracking.

Let b be the branching factor (average number of successors per node), d be the depth of the shallowest goal, and m be the maximum depth of the search space. For greedy best-first search, the worst-case time complexity is O(b^m), as it may explore all nodes in the worst case. The space complexity is also O(b^m) because it must store all frontier nodes in the priority queue. For A*, the complexity is O(b^d) in the worst case with an admissible heuristic, but can be much better with a well-informed heuristic.

The effective branching factor is a useful metric for evaluating heuristic quality. It is the branching factor that a uniform tree of depth d would need to have to contain the same number of nodes as actually expanded. A good heuristic reduces the effective branching factor close to 1, meaning the search is almost linear. A poor heuristic leaves it close to the actual branching factor b, providing little benefit over uninformed search.

Space complexity is often the limiting factor for best-first search, especially A*, which must keep all frontier nodes in memory. For large search spaces, this can exhaust available RAM long before time becomes an issue. This is why memory-bounded variants like Recursive Best-First Search (RBFS) and Simplified Memory-Bounded A* (SMA*) were developed — they trade time for space by regenerating nodes as needed.

Impact of Heuristic Accuracy

Heuristic accuracy directly determines practical performance. An admissible heuristic that never overestimates guarantees that A* will find an optimal solution, but if it consistently underestimates by a large margin, the search will still expand many nodes. The closer h(n) is to the true cost h*(n), the fewer nodes are expanded. In the extreme, if h(n) = h*(n) perfectly, A* expands only nodes on the optimal path. Conversely, an inadmissible heuristic that overestimates may cause the algorithm to miss the optimal path entirely, though it may find a solution faster.

6. Variations and Optimizations

Best-first search is a framework with many instantiations. Greedy best-first search is the simplest, using only h(n). A* search uses f(n) = g(n) + h(n) and is optimal with an admissible heuristic. Weighted A* uses f(n) = g(n) + w * h(n) with weight w > 1 to favor speed over optimality, finding solutions faster while guaranteeing the solution cost is at most w times optimal. This is widely used in robotics where a near-optimal path found quickly is more valuable than a perfect path found slowly.

Beam search, as shown in the implementation section, limits the frontier to the top k nodes at each level. It is incomplete (may miss the goal) and not optimal, but it is highly memory efficient and is the workhorse of modern sequence generation in large language models and machine translation. Another variant is Recursive Best-First Search (RBFS), which mimics best-first search using only linear space by recursively exploring the best path and backtracking when a better alternative appears, storing only the current path and the best alternative cost.

For very large graphs, iterative deepening versions and anytime algorithms are valuable. Anytime best-first search quickly finds a suboptimal solution and then continues to improve it as time allows, which is ideal for real-time systems with deadlines. Bidirectional best-first search runs two searches simultaneously — one from the start and one from the goal — and tries to meet in the middle, potentially reducing the search space from O(b^d) to O(b^(d/2)).

Optimization Techniques

Several optimizations can significantly improve performance. Heuristic caching avoids recomputing h(n) for the same node multiple times. Tie-breaking strategies, such as preferring nodes with smaller g(n) when f(n) values are equal, can reduce the number of expansions. Using a more efficient priority queue, like a Fibonacci heap or a bucketed queue for integer priorities, can improve asymptotic performance, though binary heaps are usually sufficient in practice.

Another powerful optimization is heuristic improvement through pattern databases or landmark heuristics. For example, in pathfinding on road networks, precomputed distances to selected landmark nodes can provide much more accurate heuristics than straight-line distance, dramatically reducing search effort. Similarly, for the 15-puzzle, pattern databases that store exact costs for subsets of tiles provide highly informed heuristics that make otherwise intractable problems solvable.

7. Real-World Applications

Best-first search and its variants are deployed in a wide range of production systems. In GPS navigation and mapping services like Google Maps, A* search with sophisticated heuristics based on road hierarchy and speed limits finds optimal routes through continental-scale road networks with billions of edges. The heuristic combines Euclidean distance with precomputed highway information to guide the search, allowing real-time queries that would be impossible with uninformed search.

In game development, best-first search drives pathfinding for non-player characters (NPCs). Games like StarCraft, Civilization, and countless Unity and Unreal Engine titles use A* on navigation meshes or grids to move units around obstacles. The heuristic is typically Euclidean or Manhattan distance, and optimizations like hierarchical pathfinding and jump point search are layered on top to handle large maps with hundreds of moving agents simultaneously.

Beyond pathfinding, best-first search is used in network routing, where routers use heuristic estimates of latency to forward packets; in web crawling, where crawlers prioritize URLs that appear most relevant to the crawl goal; in database query optimization, where the search space of query plans is explored using cost estimates; and in AI planning for robotics, where actions are sequenced to achieve a goal state. Even in natural language processing, beam search (a best-first variant) is used to generate text by keeping the most probable partial sequences at each step.

The choice of variant depends on the domain constraints. When optimality is critical, such as in network routing where suboptimal paths waste bandwidth, A* with an admissible heuristic is preferred. When speed is paramount and near-optimal is acceptable, such as in games or real-time robotics, weighted A* or greedy best-first search is used. When memory is limited, such as in embedded systems or large-scale NLP, beam search is the go-to choice.

8. Comparison with Alternatives

Choosing the right search algorithm requires understanding how best-first search compares to other fundamental approaches. Uninformed algorithms like BFS and DFS guarantee completeness without needing a heuristic, but they pay for it in efficiency. Dijkstra's algorithm is essentially a best-first search where f(n) = g(n) (no heuristic), guaranteeing optimality for weighted graphs but expanding many more nodes than A*. Understanding these trade-offs helps engineers select the appropriate tool for each problem.

Greedy best-first search is the fastest but least reliable, as it can be misled by a poor heuristic and is neither complete nor optimal in general. A* is complete and optimal with an admissible heuristic, but it can be memory-intensive. BFS is complete and optimal for unweighted graphs, but it explores uniformly and is slow for large spaces. DFS is memory-efficient but can get lost in deep branches and is not optimal. The right choice depends on whether you have a good heuristic, whether you need optimality, and what your memory constraints are.

In practice, the decision often comes down to heuristic availability. If you can define a meaningful heuristic, best-first search variants will almost always outperform uninformed methods. If no heuristic is available, Dijkstra's or BFS may be the only options. For very large search spaces where even A* runs out of memory, iterative deepening A* (IDA*) or beam search provide memory-bounded alternatives at the cost of optimality. Modern systems often combine approaches, such as using best-first search for high-level planning and Dijkstra's for low-level refinement.

9. Common Mistakes and Best Practices

One of the most frequent mistakes when implementing best-first search is using an inadmissible or inconsistent heuristic without understanding the consequences. An inadmissible heuristic that overestimates can cause A* to return a suboptimal path while still appearing to work correctly, making the bug hard to detect. Always verify admissibility by testing that h(n) <= h*(n) on small instances where the true cost can be computed via exhaustive search. For consistency, check that h(n) <= cost(n, n') + h(n') for all edges.

Another common pitfall is neglecting the closed list or implementing it inefficiently. Without a visited set, best-first search can revisit nodes exponentially many times, especially in graphs with many cycles. Using a list instead of a hash set for the closed list turns O(1) lookups into O(n) scans, crippling performance on large graphs. Similarly, using an unsorted list instead of a heap for the open list turns O(log n) operations into O(n) operations, which becomes prohibitive when the frontier contains thousands of nodes.

A third mistake is failing to handle tie-breaking and priority updates correctly. When two nodes have the same heuristic value, the order in which they are expanded can affect efficiency. Preferring nodes with smaller g(n) or deeper depth can reduce expansions. More critically, when a cheaper path to an already discovered node is found, the priority in the heap must be updated. Many naive implementations simply push a duplicate entry and skip visited nodes on pop, which works but wastes memory. For large graphs, implementing a decrease-key operation or using a visited-cost dictionary as shown in the A* example is more efficient.

Best Practices for Production Code

• Choose the right heuristic: Invest time in designing an informative, admissible heuristic. A better heuristic often yields more speedup than any code optimization. Consider precomputation, pattern databases, or landmark techniques for complex domains.
• Profile before optimizing: Use the effective branching factor and number of expansions as metrics. If the search expands too many nodes, the heuristic is likely weak; if heap operations dominate, consider a more efficient queue.
• Handle edge cases: Explicitly handle cases where the start equals the goal, where no path exists, and where the graph is disconnected. Return clear indicators (e.g., None or empty path) instead of crashing.
• Make the search interruptible: For real-time applications, implement the search as a generator or with a timeout so it can return the best path found so far if interrupted, enabling anytime behavior.
• Test on small, verifiable instances: Validate correctness by comparing against BFS or Dijkstra on small graphs where optimal solutions are known. Test with both admissible and inadmissible heuristics to observe the impact on optimality.

Finally, remember that best-first search is not always the answer. For unweighted graphs with no heuristic, BFS is simpler and optimal. For problems requiring exhaustive enumeration, DFS with backtracking may be more appropriate. Always consider the problem constraints — graph size, heuristic availability, optimality requirements, and memory limits — before committing to best-first search.

10. Interview Questions

Q1: What is the difference between greedy best-first search and A* search?

Greedy best-first search expands the node that appears closest to the goal according to the heuristic alone, using f(n) = h(n). It is fast but neither complete nor optimal, as it can be misled by a poor heuristic and may ignore the cost already incurred. A* search uses f(n) = g(n) + h(n), combining the actual cost from the start with the heuristic estimate. With an admissible heuristic (never overestimates), A* is both complete and optimal, guaranteeing the cheapest path. In an interview, illustrate with an example where greedy search picks a path that looks good heuristically but is actually expensive, while A* correctly balances both factors. Mention that Dijkstra's is a special case of A* with h(n)=0.

Q2: Is best-first search complete and optimal? Under what conditions?

Greedy best-first search is not complete in general — it can get stuck in loops or infinite branches, especially without a visited set, and it is not optimal because it ignores path cost. However, with a visited set and a finite search space, it becomes complete in the sense that it will eventually explore all reachable nodes if the heuristic does not trap it. A* search, which is a best-first search variant, is complete and optimal if the heuristic is admissible and the search space is finite with positive edge costs. If the heuristic is also consistent, A* is optimally efficient, meaning no other optimal algorithm will expand fewer nodes. Be prepared to define admissibility and consistency formally.

Q3: How would you implement best-first search efficiently in Python? What data structures would you use?

Use a binary heap via heapq for the open list to get O(log n) push and pop operations, and a hash set or dictionary for the closed list/visited costs to get O(1) membership checks. Store tuples of (priority, node, path) or (priority, node) with a separate parent pointer dictionary to reconstruct the path without copying lists on every push. Discuss the trade-off between storing full paths (simpler but memory-heavy) versus storing parent pointers (more memory-efficient but requires reconstruction). Also mention handling duplicate priorities and the need to skip already visited nodes when popping from the heap, since Python's heap does not support efficient decrease-key.

Q4: What makes a good heuristic? Can you give examples?

A good heuristic is admissible (never overestimates), consistent (satisfies the triangle inequality), informative (close to the true cost), and cheap to compute. For grid pathfinding, Manhattan distance is admissible for 4-directional movement, while Euclidean distance is admissible for any direction. For the 8-puzzle, the number of misplaced tiles and Manhattan distance of tiles to their goal positions are classic admissible heuristics, with Manhattan distance being more informative. For road networks, straight-line distance or landmark-based heuristics are used. Explain the trade-off: a more informative heuristic reduces expansions but may cost more to compute, so the net benefit depends on the balance.

Q5: How does beam search relate to best-first search, and when would you use it?

Beam search is a memory-bounded variant of best-first search that keeps only the top k nodes (beam width) at each level, discarding the rest. It is essentially a truncated best-first search that trades completeness and optimality for fixed memory usage O(k * d). It is used when the search space is too large for standard best-first search to fit in memory, such as in natural language processing for machine translation or text generation, where the vocabulary size makes the branching factor enormous. Mention that with beam width = 1, it becomes greedy search, and with infinite width, it becomes standard best-first search. Discuss how to choose beam width based on the time-memory-quality trade-off.