Greedy Best-First Search

The Greedy Best-First search algorithm uses only one numerical criterion to choose a node: the cost of reaching the target node. The algorithm does not pay attention to how much path it has traversed. This simplicity ensures that the algorithm works quickly. Simultaneously, this simplicity causes the algorithm to be able to ignore the shortest path, as the node close to the target might not be the closest node to the target.

What Is Greedy Best-First Search?

Greedy Best-First Search is an informed graph search algorithm that always expands the node with the lowest heuristic value, using the evaluation function f(n) = h(n), where h(n) is an estimate of the cost to get from n to the goal node. This algorithm is part of the larger family of best-first search algorithms, which is a set of algorithms that expand nodes depending on an evaluation function, not necessarily depth or breadth order as in uninformed searches.

The concept of using an evaluation function was first introduced by Judea Pearl in his work “Heuristics: Intelligent Search Strategies for Computer Problem Solving” (1984). Stuart Russell and Peter Norvig later made a distinction between greedy best-first search and A* in their book “Artificial Intelligence: A Modern Approach” (4th ed., 2021): A* uses f(n) = g(n) + h(n), including both the cost already paid, g(n), and the estimate of the remaining cost, h(n).

Greedy Best-First Search vs. A*, BFS, and DFS

The table below compares the four algorithms most often confused with each other.

Algorithm	Evaluation Function	Uses Path Cost g(n)?	Complete?	Optimal?
Greedy Best-First Search	f(n) = h(n)	No	No	No
A* Search	f(n) = g(n) + h(n)	Yes	Yes (with admissible h)	Yes (with admissible h)
Breadth-First Search	Node depth	No heuristic used	Yes	Yes (unweighted graphs)
Depth-First Search	Node order	No heuristic used	No (infinite spaces)	No

The Breadth First Search Algorithm (BFS) is often mistaken for Greedy Best-First Search as both algorithms have been referred to as “BFS.” The BFS algorithm searches level by level, and no heuristic is used. The Greedy Best-First Search searches solely on the basis of heuristics, which means it can bypass whole branches of nodes.

How Greedy Best-First Search Works

The algorithm consists of five steps for each execution.

1. Initialization. Place the start node into a priority queue sorted on the basis of heuristic.
2. Selection. Get the node which has the least heuristic value from the queue.
3. Checking. If the selected node is the goal, terminate the execution and get the path.
4. Expansion. Put each unvisited neighbor of the selected node into the queue based on the heuristic value.
5. Repeat. Keep selecting the node having the least heuristic value until the goal is reached.

Priority queue ensures that the step 2 always gets the node which is considered to be closest to the goal at the current moment irrespective of the number of steps taken to reach the node.

Choosing a Heuristic

The heuristic function, h(n), can yield meaningful results only when it meets certain mathematical properties. There are two important properties that a heuristic must meet for searching processes: admissible and consistent.

Admissible heuristics do not overestimate the actual cost of moving from node n to the goal state. An admissible heuristic may underestimate the rest of the cost, but it should never make a claim that the cost from node n to the goal is greater than the real one. In order to guarantee an optimal solution, A* requires an admissible heuristic. In the Greedy Best-First Search algorithm, g(n) is ignored, hence admissibility does not guarantee optimality here – it only influences the directness of the searching process.

Consistent heuristics meet the property h(n) ≤ cost(n, n’) + h(n’), where n’ is a neighbor of node n. Consistency is a stronger requirement than admissibility, as all consistent heuristics are admissible, but not vice versa.

There are two heuristic functions that are frequently used in pathfinding tasks.

• The Manhattan distance is the sum of the differences between two points’ coordinate values: |x1 − x2| + |y1 − y2|. The Manhattan distance works best when the movement is limited to four directions (up, down, left, right).
• The Euclidean distance is the distance between two points measured along the line connecting them: √((x1−x2)² + (y1−y2)²). The Euclidean distance works well on open fields or grids that allow diagonal movement.

A zero-value heuristic leads to an unsorted expansion for Greedy Best-First Search. An exaggerated value for the heuristic may mislead the search to expand a node with no path to the goal node.

Worked Example: Tracing the Algorithm

The graph below has six nodes. Each node’s heuristic value estimates its straight-line distance to goal node G.

Graph edges: S→A, S→B, A→C, A→D, B→D, C→G, D→G Heuristic values: S=10, A=8, B=7, C=4, D=3, G=0

Step	Node Expanded	New Nodes Added to Open List	Open List After Step
1	S	A (h=8), B (h=7)	B(7), A(8)
2	B	D (h=3)	D(3), A(8)
3	D	G (h=0)	G(0), A(8)
4	G	— (goal reached)	—

The algorithm returns the path S → B → D → G. Node C and a second route through A are never expanded, because B and D consistently offered a lower heuristic value at each comparison.

Python Implementation

The following implementation uses Python’s heapq module as the priority queue.

python
import heapq

def greedy_best_first_search(graph, heuristic, start, goal):
    open_list = [(heuristic[start], start)]
    came_from = {start: None}
    visited = set()

    while open_list:
        _, current = heapq.heappop(open_list)
        if current in visited:
            continue
        visited.add(current)

        if current == goal:
            path = []
            node = goal
            while node is not None:
                path.append(node)
                node = came_from[node]
            path.reverse()
            return path

        for neighbor in graph[current]:
            if neighbor not in visited:
                heapq.heappush(open_list, (heuristic[neighbor], neighbor))
                if neighbor not in came_from:
                    came_from[neighbor] = current

    return None

graph = {
    'S': ['A', 'B'],
    'A': ['C', 'D'],
    'B': ['D'],
    'C': ['G'],
    'D': ['G'],
    'G': []
}

heuristic = {'S': 10, 'A': 8, 'B': 7, 'C': 4, 'D': 3, 'G': 0}

result = greedy_best_first_search(graph, heuristic, 'S', 'G')
print("Path found:", " -> ".join(result))

Output:

Path found: S -> B -> D -> G

The output matches the manual trace in the previous section, confirming the implementation follows the same expansion order.

Greedy Best-First Search vs. A*: Measured on the Same Graph

Testing both algorithms on the same graph gives a clear example of the trade-off between them rather than giving an abstract definition of the trade-off. In the graph that will be used for the testing, the graph will consist of an 8-connected 10×9 grid and a wall between the start and goal nodes.

Metric	Greedy Best-First Search	A* Search
Nodes expanded	29	56
Path length (nodes)	18	15
Path cost	19.49	17.73

Greedy Best First Search expended 48% less nodes than A*, proving the superiority of the former algorithm in terms of speed. The path found by A* was 9% cheaper, proving its optimality. Both conclusions do not apply to any arbitrary graph and their extent is dependent upon the characteristics of the specific graph and the quality of the heuristic, but the direction of the trade-off applies almost universally to all weighted graphs.

Why the Algorithm Can Fail to Find the Shortest Path

The greedy best-first search algorithm may pick up a node that seems close to the goal but is situated on a path which is disconnected to the goal. In such cases, the algorithm will not terminate. Instead, it pops the next lowest heuristic node off the open list till it gets one connected to the goal node. The increased node count seen in the measurements above is caused by the fact that the algorithm expands some nodes in the vicinity of the wall prior to finding a path through the lone gap.

The Greedy Best-First search algorithm terminates even when the search space is finite and there is a visited-node list for the search space. It always finds the goal node whenever a goal is reachable but is not guaranteed to provide the shortest path to it. It is an incomplete algorithm under certain circumstances. The circumstances that make the algorithm incomplete include an infinite search space and tree search implementation with no visited-node check.

Advantages

Here are three advantages provided by the Greedy Best-First Search algorithm compared to the uninformed search strategies.

• Efficiency. It expands less number of nodes than Breadth-First Search in graphs in which the heuristic is always oriented towards the goal state.
• Small memory overhead. The open list stores only the frontier nodes with the best values of the heuristic function.
• Simple implementation. The algorithm uses only one heuristic function and priority queue without the information about path cost.

Limitations

There are three restrictions on the use of Greedy Best-First Search.

• Suboptimal paths. Since the algorithm does not consider g(n), the path found by it may have greater total cost than the shortest path, as seen from the above experiment.
• Dependency on the heuristic. Search performance decreases linearly with decrease in the quality of the heuristic; a bad heuristic results in many unnecessary node expansions and possibly a suboptimal path.
• Incompleteness in particular cases. The algorithm is incomplete without checking for already visited nodes or when the search space is infinite.

Real-World Applications

Four areas use Greedy Best-First Search when finding the solution quickly outweighs finding the optimal solution.

• Video game pathfinding. Non-playing characters find the path towards the player or a destination using the algorithm for the purpose of calculating a path within one engine frame that is suboptimal but good enough if rendered on time.
• Robot navigation. Robots navigate in partially-known environments using heuristic distance to a target point for moving while avoiding the cost of recalculating a full-cost path every time sensor data changes.
• Puzzle solving. Eight and fifteen puzzle games solve puzzles faster than exhaustive search but do not find the optimal solution which is the minimum number of moves.
• Navigation systems route sketching. Some navigation systems employ greedy heuristic in estimating the initial route prior to applying a more exhaustive algorithm.

When to Use Greedy Best-First Search Instead of A*

Greedy Best-First Search should be used when a rapid, decent route is preferred to an optimal route, while A* search is preferred when optimality of the route is crucial.* In real-time applications where there is a time constraint, such as game artificial intelligence, Greedy Best-First Search is preferred. On the other hand, routing problems and robotics safety routes prefer A*.

Frequently Asked Questions