A* Search is a widely used informed search algorithm. It evaluates a node n using the function f(n), which combines g(n), the actual cost from the initial state to n, and h(n), the estimated minimum remaining cost from n to a goal. The frontier is commonly maintained in a priority queue ordered by the smallest f(n). A* expands the node with the lowest estimated total solution cost. Under standard conditions, A* tree search is optimal when its heuristic is admissible and step costs are nonnegative. In graph search, a consistent heuristic supports optimality without reopening already expanded nodes; with an admissible but inconsistent heuristic, implementations may need to reopen states when a cheaper path is found. A* can be complete under suitable conditions, including finite branching and step costs bounded below by a positive value. Its major limitation is memory consumption because it stores many generated frontier and explored nodes. The effectiveness of A* depends on the quality of the heuristic: a more informative admissible heuristic can reduce unnecessary exploration while preserving optimality.
A* Search Algorithm
A* is an informed search algorithm that combines the accumulated path cost with a heuristic estimate of the remaining cost to guide search.
f(n) = g(n) + h(n)
Explanation
Variables
| Symbol | Meaning |
|---|---|
f(n) | The estimated total cost of a solution path through node n. |
g(n) | The actual accumulated path cost from the initial state to node n. |
h(n) | The estimated remaining cost from node n to a goal. |
n | A node in the search frontier. |
Example or application
Suppose node A has an accumulated cost g(A) = 5 and a heuristic estimate h(A) = 8. Its A* evaluation is 13. If node B has g(B) = 9 and h(B) = 2, its evaluation is 11, so A* selects B first because its estimated total cost is smaller.
Text
A* evaluates each frontier node using two components: the cost already spent to reach it and an estimate of the cost still required to reach a goal. This allows it to balance progress so far with estimated future effort.
Key Points
A* combines actual path cost and estimated remaining cost.
The evaluation function is f(n) = g(n) + h(n).
A* uses a priority queue to select the lowest evaluation value.
Admissibility and consistency are important for optimality guarantees.
A* can require substantial memory.
Applications
GPS and route planning
Video-game pathfinding
Robot navigation
Puzzle solving
Automated planning
Learning Outcomes
Explain the three values used in A* evaluation.
Calculate f(n) from g(n) and h(n).
Describe the conditions that support A* optimality.
Practice Questions
What is the A* evaluation function?
What is the difference between g(n) and h(n)?
Why is heuristic consistency useful in graph-search A*?
Related Concepts
Greedy Best-First Search
Uniform-Cost Search
Informed Search and Heuristics
Admissible Heuristic
Common Mistakes
Using only h(n) and forgetting g(n).
Assuming A* is always optimal regardless of heuristic properties.
Confusing an estimated total cost with the actual path cost.
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.
- Hart, P. E., Nilsson, N. J., and Raphael, B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths, 1968.
- Russell, S. and Norvig, P. Artificial Intelligence: A Modern Approach, A* search.
Suggest a correction or source · More in Artificial Intelligence & Machine Learning