AI Notes

Greedy Best-First Search - Heuristic AI Algorithm

Learn Greedy Best-First Search for AI. Understand heuristic-based search, priority queues, implementation, advantages and limitations. Technical interview guide 2024.

Introduction

Greedy Best-First Search (GBFS) is an informed search algorithm that uses heuristic knowledge to guide exploration toward the goal. Unlike uninformed strategies that expand nodes blindly, GBFS evaluates each node using a heuristic function h(n)—an estimate of the cost from that node to the goal—and always expands the node that appears closest to the goal.

The "greedy" in its name reflects the algorithm's myopic strategy: at each step, it makes the locally optimal choice (the node with smallest h(n)) without considering the cost already incurred to reach that node. This makes GBFS fast in practice but non-optimal in theory, since it may follow a seemingly short but ultimately expensive path.

GBFS is widely deployed in applications where speed matters more than optimality: real-time game AI, preliminary route suggestions, and any domain where an approximate answer quickly is better than the perfect answer slowly.

Algorithm Definition

Evaluation Function

GBFS uses: f(n) = h(n)

Compare with A*: f(n) = g(n) + h(n). GBFS drops the g(n) term entirely—it doesn't care how much it cost to reach node n, only how far n appears to be from the goal.

Pseudocode

Code example

function Greedy_Best_First_Search(problem, h):
    node ← Node(problem.initial_state)
    frontier ← PriorityQueue ordered by h(n)
    frontier.insert(node)
    explored ← empty set

    while frontier is not empty:
        node ← frontier.extract_min()  // lowest h(n)
        
        if problem.is_goal(node.state):
            return Solution(node)
        
        explored.add(node.state)
        
        for each action in problem.actions(node.state):
            child ← child_node(problem, node, action)
            if child.state not in explored and child not in frontier:
                frontier.insert(child)
            elif child in frontier with higher h:
                replace with lower-h version
    
    return Failure

Detailed Worked Example

Setup: Romania Road Map (Simplified)

Finding path from Arad to Bucharest with straight-line distance heuristic:

City connections (road distances)

Arad → Sibiu: 140

Arad → Timisoara: 118

Sibiu → Fagaras: 99

Sibiu → Rimnicu: 80

Fagaras → Bucharest: 211

Rimnicu → Pitesti: 97

Pitesti → Bucharest: 101

Timisoara → Lugoj: 111

Heuristic h (straight-line to Bucharest)

Arad=366, Sibiu=253, Timisoara=329

Fagaras=176, Rimnicu=193, Lugoj=244

Pitesti=100, Bucharest=0

Step-by-Step Trace

STEP 1	Expand Arad (h=366)
Frontier	{Sibiu(h=253), Timisoara(h=329)}
Explored	{Arad}
STEP 2	Expand Sibiu (h=253)
Frontier	{Fagaras(h=176), Rimnicu(h=193), Timisoara(h=329)}
Explored	{Arad, Sibiu}
STEP 3	Expand Fagaras (h=176)
Frontier	{Bucharest(h=0), Rimnicu(h=193), Timisoara(h=329)}
Explored	{Arad, Sibiu, Fagaras}
STEP 4	Bucharest is the GOAL!
Path found: Arad	Sibiu → Fagaras → Bucharest
Path cost	140 + 99 + 211 = 450

Is This Optimal?

The alternative path Arad → Sibiu → Rimnicu → Pitesti → Bucharest has cost 140 + 80 + 97 + 101 = 418, which is cheaper! GBFS missed it because Fagaras (h=176) looked closer than Rimnicu (h=193), so GBFS never explored the Rimnicu branch.

This perfectly illustrates GBFS's weakness: it's greedy about apparent proximity, ignoring accumulated cost.

Properties Analysis

Completeness

Tree search: Not complete (can loop in infinite state spaces)
Graph search (with explored set): Complete in finite spaces
Worst case: can explore the entire space before finding the goal

Optimality

Not optimal: Ignoring g(n) means it can find expensive paths
The example above shows a suboptimal solution found before optimal

Time Complexity

Worst case: O(b^m) where m is maximum depth
Best case: O(b·d) when heuristic is perfect — goes straight to goal
In practice: much better than uninformed search for good heuristics

Space Complexity

O(b^m) worst case — stores all generated nodes in frontier
Similar to BFS in worst case

When GBFS Excels vs. Fails

GBFS Works Well When:

The heuristic is highly accurate (h ≈ h*)
There are no "misleading" local minima
The topology doesn't create deceptive shortcuts
Speed matters more than optimality

GBFS Fails When:

Obstacles create heuristic "valleys" — nodes close by air but far by path
The state space has many nodes with similar h values
Optimal path goes temporarily away from the goal

Pathological Case: The Wall Problem

Example

Start(h=4) . . . . Goal(h=0) | | . [WALL WALL WALL] . | | . . . . . . . . . . . GBFS goes right toward goal, hits wall, then must explore many nodes to find path around. A straight BFS around the wall would be faster.

GBFS vs. A* vs. UCS

Feature	GBFS	A*	UCS
f(n) =	h(n)	g(n)+h(n)	g(n)
Uses heuristic	Yes	Yes	No
Optimal	No	Yes	Yes
Fast (good h)	Very	Yes	Slow
Memory	O(b^m)	O(b^d)	O(b^(C*/ε))

Improving GBFS

Weighted A* as Middle Ground

If you want something between GBFS (fast, non-optimal) and A* (optimal, slower):

w = 1	Pure A* (optimal)
w = ∞	Pure GBFS (fast, non-optimal)
w = 2	Common choice — at most 2x optimal cost

Beam Search Variant

Limit frontier size to k best nodes (beam width):

Example

GBFS with beam width k: Keep only top-k nodes by h(n) at each step Reduces memory from O(b^m) to O(k) Even less complete, but very memory efficient

Implementation Tips

Priority Queue Efficiency

Use a min-heap keyed on h(n). Python's heapq or Java's PriorityQueue work directly.

Example

import heapq def greedy_bfs(graph, start, goal, heuristic): frontier = [(heuristic[start], start)] explored = set() parent = {start: None} while frontier: h_val, current = heapq.heappop(frontier) if current == goal: return reconstruct_path(parent, goal) explored.add(current) for neighbor, cost in graph[current]: if neighbor not in explored: heapq.heappush(frontier, (heuristic[neighbor], neighbor)) if neighbor not in parent: parent[neighbor] = current return None

Common Interview Questions

Q: Why is GBFS incomplete in tree search? A: Without tracking visited states, GBFS can oscillate between two nodes that each look closer to the goal than their neighbors, creating an infinite loop. Graph search with an explored set prevents this.

**Q: Give a scenario where GBFS outperforms A*.** A: When the heuristic is nearly perfect and the state space is enormous. GBFS with h ≈ h* goes almost directly to the goal in O(d) time, while A* may still need to verify optimality by expanding more nodes.

Q: Can GBFS find the optimal solution? A: Yes, but only by luck—when the heuristically shortest path happens to also be the cheapest. There's no guarantee, and for most problems it won't be optimal.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Greedy Best-First Search - Heuristic AI Algorithm.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Artificial Intelligence topic.

Search Terms

artificial-intelligence, artificial intelligence, artificial, intelligence, search, algorithms, greedy, best

Continue learning this concept

Search AlgorithmsBreadth-First Search (BFS) - AI Algorithm GuideComplete BFS algorithm tutorial for artificial intelligence. Learn breadth-first search implementation, shortest path, complexity analysis, and interview preparation. Essential BTech notes on graph algorithms 2024.Search AlgorithmsDepth-First Search (DFS) - Complete BTech GuideMaster DFS algorithm for artificial intelligence. Learn depth-first search implementation, backtracking, complexity analysis, and interview preparation with code examples. AI search algorithms explained for BTech students 2024.Search AlgorithmsA* Search Algorithm - Complete AI GuideMaster A* pathfinding algorithm for artificial intelligence. Learn heuristic functions, admissibility, optimality, implementation with code. Technical interview preparation 2024.Search AlgorithmsInformed Search Strategies - AI AlgorithmsComplete tutorial on informed search strategies in artificial intelligence. Learn greedy search, best-first, A*, heuristic functions. BTech notes 2024.Search AlgorithmsIterative Deepening Search (IDS) - AI AlgorithmMaster Iterative Deepening Search (IDS) combining benefits of BFS and DFS. Learn depth-limited search, memory efficiency, implementation. Complete BTech guide 2024.Search AlgorithmsSearch Algorithms Comparison - AI TechniquesCompare BFS, DFS, UCS, A*, and search algorithms. Learn when to use each algorithm, complexity analysis, practical applications in AI systems.

PreviousDepth-First Search (DFS) - Complete BTech Guide NextInformed Search Strategies - AI Algorithms

AI Notes

Greedy Best-First Search - Heuristic AI Algorithm

Learn Greedy Best-First Search for AI. Understand heuristic-based search, priority queues, implementation, advantages and limitations. Technical interview guide 2024.

Introduction

Algorithm Definition

Evaluation Function

GBFS uses: f(n) = h(n)

Compare with A*: f(n) = g(n) + h(n). GBFS drops the g(n) term entirely—it doesn't care how much it cost to reach node n, only how far n appears to be from the goal.

Pseudocode

Code example

function Greedy_Best_First_Search(problem, h):
    node ← Node(problem.initial_state)
    frontier ← PriorityQueue ordered by h(n)
    frontier.insert(node)
    explored ← empty set

    while frontier is not empty:
        node ← frontier.extract_min()  // lowest h(n)
        
        if problem.is_goal(node.state):
            return Solution(node)
        
        explored.add(node.state)
        
        for each action in problem.actions(node.state):
            child ← child_node(problem, node, action)
            if child.state not in explored and child not in frontier:
                frontier.insert(child)
            elif child in frontier with higher h:
                replace with lower-h version
    
    return Failure

Detailed Worked Example

Setup: Romania Road Map (Simplified)

Finding path from Arad to Bucharest with straight-line distance heuristic:

City connections (road distances)

Arad → Sibiu: 140

Arad → Timisoara: 118

Sibiu → Fagaras: 99

Sibiu → Rimnicu: 80

Fagaras → Bucharest: 211

Rimnicu → Pitesti: 97

Pitesti → Bucharest: 101

Timisoara → Lugoj: 111

Heuristic h (straight-line to Bucharest)

Arad=366, Sibiu=253, Timisoara=329

Fagaras=176, Rimnicu=193, Lugoj=244

Pitesti=100, Bucharest=0

Step-by-Step Trace

STEP 1	Expand Arad (h=366)
Frontier	{Sibiu(h=253), Timisoara(h=329)}
Explored	{Arad}
STEP 2	Expand Sibiu (h=253)
Frontier	{Fagaras(h=176), Rimnicu(h=193), Timisoara(h=329)}
Explored	{Arad, Sibiu}
STEP 3	Expand Fagaras (h=176)
Frontier	{Bucharest(h=0), Rimnicu(h=193), Timisoara(h=329)}
Explored	{Arad, Sibiu, Fagaras}
STEP 4	Bucharest is the GOAL!
Path found: Arad	Sibiu → Fagaras → Bucharest
Path cost	140 + 99 + 211 = 450

Is This Optimal?

This perfectly illustrates GBFS's weakness: it's greedy about apparent proximity, ignoring accumulated cost.

Properties Analysis

Completeness

Tree search: Not complete (can loop in infinite state spaces)
Graph search (with explored set): Complete in finite spaces
Worst case: can explore the entire space before finding the goal

Optimality

Not optimal: Ignoring g(n) means it can find expensive paths
The example above shows a suboptimal solution found before optimal

Time Complexity

Worst case: O(b^m) where m is maximum depth
Best case: O(b·d) when heuristic is perfect — goes straight to goal
In practice: much better than uninformed search for good heuristics

Space Complexity

O(b^m) worst case — stores all generated nodes in frontier
Similar to BFS in worst case

When GBFS Excels vs. Fails

GBFS Works Well When:

The heuristic is highly accurate (h ≈ h*)
There are no "misleading" local minima
The topology doesn't create deceptive shortcuts
Speed matters more than optimality

GBFS Fails When:

Obstacles create heuristic "valleys" — nodes close by air but far by path
The state space has many nodes with similar h values
Optimal path goes temporarily away from the goal

Pathological Case: The Wall Problem

Example

GBFS vs. A* vs. UCS

Feature	GBFS	A*	UCS
f(n) =	h(n)	g(n)+h(n)	g(n)
Uses heuristic	Yes	Yes	No
Optimal	No	Yes	Yes
Fast (good h)	Very	Yes	Slow
Memory	O(b^m)	O(b^d)	O(b^(C*/ε))

Improving GBFS

Weighted A* as Middle Ground

If you want something between GBFS (fast, non-optimal) and A* (optimal, slower):

w = 1	Pure A* (optimal)
w = ∞	Pure GBFS (fast, non-optimal)
w = 2	Common choice — at most 2x optimal cost

Beam Search Variant

Limit frontier size to k best nodes (beam width):

Example

GBFS with beam width k: Keep only top-k nodes by h(n) at each step Reduces memory from O(b^m) to O(k) Even less complete, but very memory efficient

Implementation Tips

Priority Queue Efficiency

Use a min-heap keyed on h(n). Python's heapq or Java's PriorityQueue work directly.

Example

Common Interview Questions

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Greedy Best-First Search - Heuristic AI Algorithm.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Artificial Intelligence topic.

Search Terms

artificial-intelligence, artificial intelligence, artificial, intelligence, search, algorithms, greedy, best

Continue learning this concept

PreviousDepth-First Search (DFS) - Complete BTech Guide NextInformed Search Strategies - AI Algorithms