Greedy Best-First Search Theory Guide
Try the Greedy Best-First Search Solver →Heuristic Search Algorithm, Pathfinding Calculator, f(n) = h(n), Shortest Path Finder, Graph Traversal
The Greedy Best-First Search algorithm calculator and step-by-step solver demonstrates one of the fastest, yet most flawed, pathfinding techniques in Artificial Intelligence. Imagine trying to navigate a maze by only walking toward the direction of the exit, regardless of the walls in front of you. Greedy Search is 'myopic'—it ignores how far it has already traveled and relies entirely on a heuristic (an educated guess) to pick the next closest node. While incredibly fast, its greediness often leads it into traps, dead ends, or highly inefficient overall routes.
The Greedy Evaluation Function
What do these variables mean?
- f(n)The evaluation score of node n. The algorithm always expands the node with the lowest f(n) first.
- h(n)The heuristic. This is the estimated cost from node n directly to the goal.
- Notice what is missing: Unlike A* Search, there is no g(n) (cost traveled so far). Edge weights are completely ignored during the decision-making process!
How Does it Work?
Initialize Lists: Create an empty 'Closed List' and an 'Open List'. Add the starting node to the Open List with its heuristic value.
Pick the Best Node: Find the node in the Open List with the lowest heuristic value: f(n) = h(n). Pop it off the list.
Check for Goal: If this popped node is your target destination, the search is complete!
Close the Node: If it is not the goal, add this node to the Closed List so you do not get trapped in an infinite loop.
Expand Neighbors: Look at all directly connected neighbors of the popped node. Ignore the edge costs completely; just look at the neighbor's heuristic value.
Update Lists: Add unvisited neighbors to the Open List. Repeat from Step 2 until the goal is found.
Solved Example: The Greedy Trap
Finding a path from S to G. Node heuristics: S=10, A=2, B=4, G=0. S connects to A (cost 100) and B (cost 1). A connects to G (cost 100). B connects to G (cost 1).
Step 1: Start at S. Open List: [ S(10) ].
Step 2: Pop S. Check neighbors A(2) and B(4). Because Greedy Search ignores edge costs, it sees A(2) is a smaller number than B(4). Open List: [ A(2), B(4) ].
Step 3: Pop A. Its neighbor is G(0). Open List: [ G(0), B(4) ].
Step 4: Pop G. Goal reached! Final Path: S -> A -> G.
Analysis: The algorithm chose S -> A -> G because A looked closer to the goal than B. However, the total actual edge cost was 200. If it had chosen S -> B -> G, the cost would have only been 2. This perfectly illustrates why Greedy Search is not optimal!
Student Tip: You can verify these exact manual calculations using our interactive Greedy Best-First Search step-by-step solver. Simply plug in the values from the table above to see the logic in action.
Implementation Pseudocode
function GreedyBestFirstSearch(start, goal):
open_list = [start]
closed_list = []
while open_list is not empty:
// Find node with lowest heuristic f(n) = h(n)
current_node = node in open_list with lowest h(n)
if current_node == goal:
return reconstruct_path(current_node)
remove current_node from open_list
add current_node to closed_list
for each neighbor of current_node:
if neighbor in closed_list or neighbor in open_list:
continue
neighbor.parent = current_node
add neighbor to open_list
return "No Path Found"Rules & Common Mistakes
Exam Trap: A common trick question on exams is adding massive edge weights to a graph. Remember, Greedy Search is completely blind to edge costs! It will happily take a path costing 1000 if the heuristic looks slightly better than a path costing 1.
Because Greedy Search only looks forward, it does not update existing nodes in the Open List if it finds a 'cheaper' path to them, because it doesn't track path costs at all!
If two nodes have the exact same h(n) value, algorithms typically break the tie alphabetically or by the order they were generated.
Advantages
- ✓ Incredibly Fast: By ignoring path costs, it dramatically reduces the amount of math required at each step.
- ✓ Low Memory Footprint: It typically explores far fewer nodes than uninformed search algorithms, saving RAM.
Disadvantages
- × Not Optimal: It is easily tricked by bad heuristics and will frequently return a highly inefficient path.
- × Gets Trapped Easily: It can easily walk down deep dead-ends if a node has a deceptively low heuristic, forcing massive backtracking.
Algorithm Complexity
| Scenario | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Worst Case Time | Where 'b' is the branching factor and 'm' is the maximum depth of the graph. A bad heuristic can lead the algorithm down a massive dead-end, forcing it to backtrack heavily. | ||
| Best Case Time | If the heuristic perfectly guides the algorithm directly to the goal without any obstacles, it finds the target in exactly 'd' steps (the depth of the goal). | ||
| Optimality & Completeness | Unlike A*, Greedy Search is NOT optimal (it rarely finds the absolute shortest path). Without a Closed List, it is also NOT complete (it can get stuck in infinite loops). |
Greedy Best-First Search vs. A* Algorithm
While both algorithms rely on heuristics to navigate, they treat historical data entirely differently.
- •The Formula: Greedy search evaluates nodes using only the forward-looking heuristic (f(n) = h(n)). A* evaluates nodes by combining the historical cost with the forward-looking heuristic (f(n) = g(n) + h(n)).
- •Optimality: A* is mathematically guaranteed to find the absolute shortest path. Greedy Search will usually find a path much faster, but it is rarely the most efficient route.
- •Implementation: A* constantly updates nodes in its Open List if it finds a cheaper path to them. Greedy Search ignores path costs, so it never updates an existing node; it simply skips it.
Summary
Greedy Best-First Search is the sprinter of pathfinding algorithms—it moves fast and aims straight for the finish line, but it lacks the foresight to avoid massive obstacles in its way. By evaluating nodes purely on their estimated distance to the goal (f(n) = h(n)), it requires far less computation than A*. However, this speed comes at the cost of optimality. It is best used in scenarios where finding 'a' path quickly is much more important than finding the 'perfect' path.
Common Exam Questions & FAQ
+ Why would anyone use Greedy Search instead of A*?
Speed and memory. A* is perfect, but calculating and tracking the exact historical cost for every single path takes significantly more computational power. In massive video game environments where an NPC just needs to run roughly toward the player quickly, a slightly sub-optimal path generated in 1 millisecond is better than a perfect path generated in 100 milliseconds.
+ Does Greedy Search look at edge costs at all?
No. This is the most critical concept to understand for university exams. Even if a path has an edge cost of 1,000,000, Greedy Search will blindly take it if the destination node has a heuristic value of 1.
+ Can Greedy Search get stuck in an infinite loop?
Yes, if you do not use a Closed List. If Node A thinks Node B is closer to the goal, and Node B thinks Node A is closer to the goal, the algorithm will bounce between them forever. A Closed List explicitly prevents this by acting as a memory bank of explored nodes.
🎓 Core University Curriculum
This algorithm and its manual calculation methods are foundational requirements in leading Computer Science and Software Engineering programs worldwide. You will find this topic heavily featured in the syllabi of these standard AI courses:
Explore Related Algorithms
Try the A* Algorithm Calculator
Interactively solve pathfinding problems with A* and observe how adding the cumulative cost g(n) to Greedy's heuristic h(n) corrects the suboptimal routes Greedy can produce.
A* Algorithm Theory
Explore the mathematical relationship between Greedy Best-First Search and A*: both share the same heuristic-driven priority queue, but A*'s combined f(n) = g(n) + h(n) evaluation makes it complete and optimal in ways Greedy is not.