Greedy Best-First Search

The algorithm's core mechanism is its evaluation function, f(n) = h(n), where h(n) is a heuristic estimating the cost from node n to the goal. At each step, it expands the node from the frontier with the smallest h(n) value. This makes it myopic, as it considers only the estimated future cost, ignoring the accumulated cost from the start (g(n)). Common heuristics include Euclidean or Manhattan distance for spatial problems.

Unlike A* Search, Greedy Best-First Search does not guarantee an optimal path. By ignoring the path cost g(n), it can be misled by a heuristic that underestimates distance through difficult terrain, leading to longer, costlier final paths. It is also incomplete in infinite spaces or can fail in graph spaces if it does not employ cycle detection (a closed list), as it may oscillate between nodes with similarly attractive heuristic values.

In the worst case, its time and space complexity is O(b^m), where b is the branching factor and m is the maximum depth of the search space. However, with a good heuristic, it can be extremely fast in practice, often finding a solution quickly by aggressively moving toward the goal. Its memory usage is similar to other best-first algorithms, requiring storage of the open list (frontier), typically implemented with a priority queue.

This highlights the key trade-off between speed and optimality.

• Greedy Best-First: f(n) = h(n). Fast, less memory-intensive, but non-optimal.
• A Search*: f(n) = g(n) + h(n). Optimal (if h(n) is admissible), but generally explores more nodes. A* can be seen as a generalization; Greedy Best-First is A* with the path cost term g(n) set to zero. For applications where any reasonable path suffices, Greedy can be a efficient choice.

Used when a good heuristic is available and absolute optimality is secondary to speed.

• Real-time Strategy Games: For quick, plausible unit movement where computational resources are limited.
• Robotics Exploration: Initial rapid mapping or target approach.
• Network Routing Prototypes: Fast path discovery before running a more costly optimal algorithm.
• AI Agent Decision-Making: As a component in a larger agentic cognitive architecture for quick, heuristic-based action selection within a planning loop.

1. Initialize a priority queue (open list) with the start node, keyed by h(n).
2. While the queue is not empty:
   • Pop the node n with the lowest h(n).
   • If n is the goal, return the path.
   • Expand n: generate its successors.
   • For each successor s not in the closed list: calculate h(s) and push s onto the queue.
   • Add n to the closed list to prevent re-expansion.
3. Return failure if the queue empties. The lack of a g(n) term in the key is the defining simplification.

A heuristic function, denoted h(n), is a problem-specific estimator that guides search algorithms by approximating the cost from a given node to the goal. In Greedy Best-First Search, this function is the sole determinant of node expansion priority.

• Key Properties: Admissibility (never overestimates true cost) and consistency (obeys the triangle inequality) are critical for guaranteeing optimality in algorithms like A*.
• Common Examples: Euclidean or Manhattan distance for spatial navigation; a count of misplaced tiles for the 8-puzzle.
• The quality of the heuristic directly dictates search efficiency and solution optimality.

Best-First Search is the general family of algorithms to which Greedy Best-First Search belongs. It is defined by its use of an evaluation function, f(n), to select the next node to expand from a priority queue (the open list).

• Greedy Best-First Search is a specific instance where f(n) = h(n).
• A Search* is another instance where f(n) = g(n) + h(n).
• Beam Search is a memory-constrained variant that only keeps the top k nodes (the beam width) at each depth. The choice of evaluation function defines the algorithm's behavior, balancing optimality, completeness, and efficiency.

Uniform-Cost Search (UCS) is an uninformed search algorithm that expands the node with the lowest path cost from the start, g(n). It is optimal for any step cost and is a generalization of Breadth-First Search for weighted graphs.

• Contrast with Greedy: While Greedy Best-First Search uses only the heuristic h(n) (future cost), UCS uses only the known cost g(n) (past cost).
• Foundation for A*: A* Search synthesizes these two approaches by using f(n) = g(n) + h(n), ensuring optimality that neither Greedy (which can be suboptimal) nor UCS (which is slower) provides alone.

Hill Climbing is a local search and optimization algorithm, not a systematic pathfinding algorithm like Greedy Best-First Search. However, they share a myopic, greedy philosophy.

• Both algorithms make locally optimal choices: Hill Climbing moves to the best neighboring state; Greedy Best-First expands the node that seems closest to the goal.
• Both are highly susceptible to local optima, plateaus, and ridges, from which they cannot escape.
• While Greedy Best-First maintains a frontier and can backtrack via its open list, basic Hill Climbing has no memory and gets permanently stuck, making it less robust for pathfinding.

The search frontier, or open list, is the central data structure in algorithms like Greedy Best-First Search. It is a priority queue containing all generated nodes that have not yet been expanded.

• Management: In Greedy Best-First Search, nodes are ordered in the frontier by their heuristic value, h(n). The node with the most promising heuristic is always expanded next.
• Contrast with Closed List: The closed list (or explored set) tracks already-expanded nodes to prevent cycles. Efficient frontier management is critical for the performance of all best-first search variants.