Greedy Best-First Search

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.

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.