GBFS

Gold definitionUpdated Apr 2, 2026

Greedy Best-First Search (GBFS) is a prominent informed search algorithm used in artificial intelligence and computer science for pathfinding and state-space exploration. Unlike uninformed search methods that explore systematically (e.g., Breadth-First Search, Depth-First Search), GBFS leverages a heuristic function to estimate the cost from the current node to the goal. Its core mechanism involves always expanding the node that appears "closest" to the goal based solely on this heuristic estimate, without considering the cost incurred to reach that node. This "greedy" approach makes GBFS highly efficient in finding a solution quickly, often at the expense of optimality, meaning it might not find the shortest or cheapest path. GBFS is widely used in applications where finding *any* solution fast is more critical than finding the *best* solution, such as in game AI for non-player character navigation, robotics for real-time path planning, and certain types of puzzle-solving.

Key Principles of Greedy Best-First Search

Heuristic Function: GBFS relies entirely on a heuristic function, h(n), which estimates the cost from node n to the goal node. A good heuristic is crucial for its performance, guiding the search efficiently towards the target.
Greedy Expansion: At each step, GBFS expands the node that has the lowest heuristic value h(n) among all currently open (unexpanded) nodes. This strategy prioritizes nodes believed to be closest to the goal.
Open and Closed Lists: The algorithm maintains an 'open list' (priority queue) of nodes to be explored, ordered by their heuristic values, and a 'closed list' of already expanded nodes to prevent cycles.

Working Mechanism of Greedy Best-First Search

Initialization: The search starts by placing the initial node into the open list. This list typically functions as a priority queue, ensuring efficient retrieval of the most promising node.
Node Selection: In each iteration, the node with the smallest h(n) value is extracted from the open list. This node is considered the most promising candidate for reaching the goal quickly.
Goal Check & Expansion: If the selected node is the goal, the path is found. Otherwise, its neighbors are generated. For each neighbor not in the closed list, its h(n) is calculated, and it's added to the open list. The selected node is then moved to the closed list.

Advantages and Disadvantages of Greedy Best-First Search

Efficiency: GBFS is generally much faster than uninformed search algorithms like BFS or DFS, especially in large state spaces, because its heuristic guidance prunes many unpromising paths, reducing the number of nodes explored.
Non-Optimality: A significant drawback is that GBFS is not guaranteed to find the optimal (shortest or lowest-cost) path. Its greedy nature can lead it down paths that appear promising initially but turn out to be suboptimal.
Completeness: GBFS is complete if the state space is finite and there are no infinite loops (or if a closed list is used to prevent revisiting nodes). However, it can get stuck in infinite loops if not properly implemented with a closed list.

At a glance

Executive summary

Greedy Best-First Search is a pathfinding algorithm that uses an educated guess (a heuristic) to quickly find a path from a start to a goal. It always picks the next step that seems closest to the goal, making it fast but not always finding the absolute best or shortest path.

TL;DR

A fast search algorithm that uses a "best guess" to quickly find a solution, but might not find the absolute best one.

Key points

Expands nodes based solely on a heuristic estimate of distance to the goal.
Efficiently finds a path in large state spaces where optimality is not strictly required.
Used by game AI developers, robotics engineers, logistics planners, and researchers in AI planning.
Unlike A* search, GBFS does not consider the cost to reach the current node, making it faster but sacrificing optimality.
Often used as a baseline for comparison with more sophisticated informed search algorithms, or in scenarios requiring real-time, approximate solutions.

Use cases

Game AI: Pathfinding for non-player characters (NPCs) in video games where quick, plausible paths are preferred over strictly optimal ones to reduce computational load.
Robotics: Real-time navigation for autonomous robots in dynamic environments where rapid decision-making is crucial, even if the path isn't perfectly optimized.
Logistics and Delivery: Quickly finding a feasible route for delivery vehicles in scenarios where a good-enough route is needed fast, rather than spending time on finding the absolute shortest.
Puzzle Solving: Solving certain types of puzzles (e.g., 8-puzzle, Rubik's Cube) where a solution path is desired quickly, though not necessarily the minimum number of moves.

Also known as

GBFS, Best-First Search, Greedy Search