Best-First Search

A heuristic function is a problem-specific estimation function, denoted as h(n), that approximates the cost from a given node n to the goal. It is the core guiding mechanism in Best-First Search and other informed algorithms like A*. A good heuristic is admissible (never overestimates the true cost) and consistent, enabling the algorithm to find optimal paths efficiently. For example, in pathfinding, the straight-line Euclidean distance is a common heuristic.

A priority queue is the fundamental data structure used to implement Best-First Search's open list. Nodes are stored not in the order they are discovered, but are ordered by a priority score derived from an evaluation function (e.g., heuristic value). The node with the most promising (lowest or highest) score is always selected for expansion next. This efficient ordering is what differentiates Best-First Search from uninformed methods like Breadth-First or Depth-First Search.

Greedy Best-First Search is a specific, common variant of Best-First Search where the evaluation function f(n) is simply the heuristic estimate h(n). It expands the node that appears closest to the goal. While often very fast, it is not optimal and not complete (can get stuck in loops) because it ignores the cost already incurred to reach the node g(n). It tends to be myopic, potentially leading to suboptimal solutions.

A Search* is a seminal optimal search algorithm that extends Best-First Search. Its evaluation function is f(n) = g(n) + h(n), where g(n) is the actual cost from the start node to n, and h(n) is the heuristic estimate to the goal. By combining the path cost with the heuristic, A* guarantees finding an optimal solution if the heuristic is admissible. It is the workhorse algorithm for many pathfinding and planning applications in AI and robotics.

Beam Search is a best-first, breadth-limited search algorithm. At each level of the tree, it expands all successors of the current nodes but only retains the top-k most promising nodes (the beam width) based on an evaluation function. The rest are pruned permanently. This makes it a memory-efficient approximation of Best-First Search, suitable for large state spaces like those in neural sequence generation (e.g., machine translation, text summarization).

An evaluation function assigns a numerical score to a game state or partial solution, estimating its utility or desirability. In Best-First Search, this function guides node selection. In game-playing AI (e.g., chess engines), evaluation functions are complex, often combining material advantage, board control, and king safety into a single score. They serve as a static, heuristic assessment of a non-terminal state, crucial for algorithms like Minimax with Alpha-Beta pruning.