A Star Search
A star is a pathfinding algorithm that finds the shortest route from a start to a goal while exploring far fewer nodes than blind search. It blends the known cost so far with an estimate of the remaining cost.
The scoring function
Every candidate node is ranked by a score that adds two parts:
- g is the actual cost of the path from the start to this node.
- h is a heuristic estimate of the cost from this node to the goal, such as straight line distance.
The algorithm always expands the node with the smallest g plus h total, pulled from a priority queue. This focuses effort toward the goal instead of spreading evenly.
Admissibility
For A star to guarantee an optimal path, the heuristic must be admissible, meaning it never overestimates the true remaining cost. If the heuristic is also consistent, no node needs to be reopened. A heuristic of zero turns A star back into uniform cost search.
Key idea
Ranking nodes by known cost plus an admissible estimate steers search straight toward the goal optimally.