Greedy Best-First Search is an informed search algorithm that uses a heuristic function h(n) to select the most promising frontier node. It typically maintains the frontier in a priority queue ordered by heuristic value. The node with the smallest estimated remaining cost is expanded first. The algorithm is called greedy because it focuses on apparent progress toward the goal rather than considering the full cost of the path taken so far. This can make it fast when the heuristic is useful, but it can also lead to poor choices when the heuristic is misleading. Greedy Best-First Search is not generally optimal because it ignores accumulated path cost. Its completeness depends on the search implementation and problem assumptions; graph-search implementations with duplicate-state handling can be complete in finite graphs, but the general tree-search version may fail in infinite spaces. Its performance can vary significantly with the quality of the heuristic.
Greedy Best-First Search
Greedy Best-First Search selects the frontier node with the smallest heuristic estimate of the remaining cost to a goal.
f(n) = h(n)
Explanation
Variables
| Symbol | Meaning |
|---|---|
f(n) | The priority value used to rank frontier nodes in Greedy Best-First Search. |
h(n) | The estimated remaining cost from node n to a goal. |
n | A node currently available in the search frontier. |
Example or application
Suppose a search has two frontier nodes. Node A has an estimated remaining cost of 4, while node B has an estimated remaining cost of 7. Greedy Best-First Search selects node A, even if the path already taken to reach A is more expensive than the path to B.
Text
Greedy Best-First Search chooses the node that appears closest to the goal according to a heuristic. It does not include the path cost already accumulated when ranking nodes.
Key Points
Greedy Best-First Search uses heuristic values to rank nodes.
It selects the node with the smallest h(n).
It ignores accumulated path cost g(n).
It is not generally guaranteed to find a minimum-cost solution.
Its performance depends heavily on heuristic quality.
Applications
Route-finding with heuristic guidance
Puzzle-solving
Game search
Robot navigation
Planning problems with useful estimates
Learning Outcomes
Explain the selection rule used by Greedy Best-First Search.
Calculate and compare heuristic values.
Explain why ignoring accumulated cost can produce a nonoptimal path.
Practice Questions
What value does Greedy Best-First Search minimize?
Does it consider the cost already paid to reach a node?
Why is Greedy Best-First Search not generally optimal?
Related Concepts
Informed Search and Heuristics
A* Search Algorithm
Priority Queue
Path Cost
Common Mistakes
Confusing Greedy Best-First Search with A* Search.
Assuming the smallest heuristic value guarantees the cheapest complete path.
Including g(n) in the standard Greedy Best-First evaluation function.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Russell, S. and Norvig, P. Artificial Intelligence: A Modern Approach, informed search algorithms.
- Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving.
Suggest a correction or source · More in Artificial Intelligence & Machine Learning