✦ScienexySCIENCE KNOWLEDGE LIBRARY
Science reference · SCI-CS-003-038

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

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.

Variables

SymbolMeaning

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