Informed search strategies use problem-specific knowledge to guide the selection of nodes during search. A heuristic function, written as h(n), estimates the remaining cost from node n to a goal state. Unlike the accumulated path cost g(n), which records the cost already paid, the heuristic estimates future cost. A useful heuristic can reduce the number of nodes explored compared with uninformed strategies. The quality of a heuristic depends on how accurately and efficiently it estimates the remaining cost. For a minimization problem, an admissible heuristic never overestimates the true minimum remaining cost. A consistent heuristic satisfies the condition h(n) ≤ c(n,a,n') + h(n') for every transition from n to n'. Consistency is a stronger property than admissibility and supports important optimality guarantees in graph search. Heuristics are central to algorithms such as Greedy Best-First Search and A* Search. A heuristic does not need to provide the exact remaining cost, but it should be computationally practical and appropriately designed for the problem.
Informed Search and Heuristics
Informed search uses additional knowledge, often represented by a heuristic function, to estimate how promising a state is for reaching a goal.
h(n) = Estimated remaining cost from n to a goal; Admissibility: h(n) ≤ h*(n)
Explanation
Variables
| Symbol | Meaning |
|---|---|
h(n) | The heuristic estimate of the remaining cost from node n to a goal. |
h*(n) | The actual minimum remaining cost from node n to a goal. |
g(n) | The accumulated cost from the initial state to node n. |
c(n,a,n') | The cost of moving from node n to successor n' using action a. |
Example or application
In a map-navigation problem, straight-line distance from a current city to the destination can be used as a heuristic estimate of remaining travel distance when roads are the available routes. It may be less than the actual road distance, but it provides useful guidance.
Text
A heuristic provides an estimate of the remaining cost from a state to a goal. Informed algorithms use this estimate to guide exploration toward potentially useful paths.
Key Points
Informed search uses additional problem-specific knowledge.
A heuristic estimates the remaining cost to a goal.
The path cost g(n) and heuristic h(n) represent different quantities.
An admissible heuristic does not overestimate the true remaining cost.
A consistent heuristic satisfies a local triangle-inequality-like condition.
Applications
GPS navigation
Game-playing systems
Robot path planning
Automated planning
Puzzle-solving algorithms
Learning Outcomes
Define a heuristic function.
Differentiate accumulated cost from estimated remaining cost.
Explain admissibility and consistency.
Practice Questions
What is a heuristic function?
How does informed search differ from uninformed search?
What makes a heuristic admissible?
Related Concepts
Greedy Best-First Search
A* Search Algorithm
Uniform-Cost Search
Heuristic Evaluation
Common Mistakes
Treating h(n) as the cost already traveled.
Assuming every heuristic is admissible.
Believing a larger heuristic value always means a better node.
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 and heuristic functions.
- Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving.
Suggest a correction or source · More in Artificial Intelligence & Machine Learning