Best-first search

• 1. Introduction

  ›

  Best-first search is a class of algorithms that explores a graph by always choosing the most promising node to look at next. That single idea sounds simple, but it sits at the heart of how computers navigate some of the hardest problems in mathematics and artificial intelligence. What makes a node "promising"? Who decides? And what happens when a search strategy gets greedy? Those are the questions this documentary will answer.

  Judea Pearl gave one of the clearest formulations of the core idea. He described the promise of a node as estimated by a heuristic evaluation function. That function, Pearl wrote, may depend on the description of the node itself, the description of the goal, information gathered during the search so far, and most importantly, any extra knowledge the algorithm has about the problem domain. That last phrase is key: extra knowledge. The algorithm is not flying blind. It is guided by whatever the designer knows about the shape of the problem.

• 2. Heuristics and Priority

  ›

  At the operational level, best-first search relies on a priority queue to keep the exploration organized. Each candidate node sits in that queue ranked by how promising it looks, and the algorithm always pulls the highest-ranked node first. Without this structure, a large graph would be unnavigable. The priority queue makes the selection efficient.

  Some researchers use the term "best-first search" in a narrower sense: they mean only those algorithms whose heuristic tries to predict how close the end of a path is to the goal. Under that definition, paths judged to be nearer the goal get expanded before anything else. This specific variant goes by two names: greedy best-first search, or pure heuristic search. The word "greedy" here describes a precise behavior. The algorithm grabs the locally best option at every step without looking back.

• 3. Greedy Best-First in Practice

  ›

  Greedy best-first search follows a particular rhythm. At each step, the algorithm expands the first successor of the current parent node. After that successor is generated, the algorithm checks its heuristic. If the successor looks more promising than its parent, it jumps to the front of the priority queue, with the parent placed directly behind it, and the loop restarts immediately. If the successor does not beat the parent, it slots into the queue at the position its heuristic value earns, and the algorithm goes on to evaluate any remaining successors of the parent.

  The pseudocode for this procedure, known as GBS, begins by marking the starting node as visited and adding it to the queue. The main loop runs as long as the queue holds anything. Each pass takes the node with the minimum estimated distance to the target, removes it from the queue, and checks all of its neighbors. Any neighbor not yet visited either turns out to be the target, in which case the procedure returns it immediately, or gets marked as visited and added to the queue. If the queue empties without finding the target, the procedure returns failure. Crucially, this implementation tracks visited nodes, which means it can handle undirected graphs without looping forever. It can also be modified to retrieve the actual path taken, not just whether the target exists.

• 4. A* and B* as Relatives

  ›

  The A search algorithm is one of the most widely known members of the best-first family. So is B. Both qualify as best-first algorithms because they use a heuristic evaluation function to guide which node gets expanded next. Best-first algorithms as a category are often applied to path finding and combinatorial search, where the space of possible solutions is too large to examine exhaustively.

  Neither A* nor B* is a greedy best-first search, and the distinction matters. Greedy best-first search uses only an estimated distance to the goal when scoring nodes. A* and B* incorporate something extra: the distance already traveled from the start. That backward-looking component changes the character of the search. It means A* and B* weigh both how far a path has come and how far it still has to go, rather than caring only about the remaining distance.