A* is an informed search algorithm that chooses the next node by combining the cost already paid with a heuristic estimate of the remaining distance to the goal. Its priority queue favors the node with the lowest estimated total cost. section 3.2 section 3.3
Unlike breadth-first search and depth-first search, A* follows no fixed traversal pattern. It is useful when problem knowledge can guide the search toward a promising goal, such as navigating a maze. section 3.2 section 3.3
A* repeatedly performs this search cycle:
- Place the root or start node in a priority queue, often implemented as a min-heap. section 3.4
- Remove the node with the lowest estimated total cost and mark it visited if it has not already been processed. section 3.4
- If the node is the goal, reconstruct the path by following parent links back to the root. section 3.4
- Otherwise, calculate costs for its neighbors, assign the current node as their parent, and add them to the queue. section 3.4
Maze navigation
For a maze, the path cost can combine the distance traveled so far, the cost of the next move, and a Manhattan-distance estimate to the goal. The queue then promotes the most promising frontier point, while parent links preserve the route used to reach it.
A* guarantees a shortest path only when its heuristic is admissible and consistent. Admissible heuristics never overestimate the actual remaining cost; consistency prevents estimates from dropping erratically in graphs with loops. section 3.3
