A* Search Algorithm – Detailed Explanation
Introduction
The A* (pronounced A-star) search algorithm is an informed search technique used in the field of
Artificial Intelligence to find the least-cost path from a given start node to a goal node. It is a widely
used algorithm in various domains due to its efficiency and optimality, provided certain conditions are
met. A* is applicable in:
• Pathfinding and navigation (e.g., GPS, robotics)
• Game development (AI decision-making)
• Solving search-based puzzles (e.g., 8-puzzle, 15-puzzle)
• Graph traversal problems
Working Principle of A*
A* operates by evaluating each node based on the following evaluation function:
f (n) = g(n) + h(n)
Where:
• f (n): Estimated total cost of the cheapest solution through node n
• g(n): Exact cost from the start node to node n
• h(n): Heuristic estimate of the cost from node n to the goal
The heuristic function h(n) plays a critical role in guiding the search towards the goal in an efficient
manner.
Step-by-Step Working of A*
1. Initialize the open list (priority queue) with the start node.
2. Maintain a closed list to store already evaluated nodes.
3. While the open list is not empty:
• Select the node n with the lowest f (n).
• If n is the goal node, terminate and return the solution path.
• Otherwise, expand node n and compute f (n) for all its successors.
• For each successor:
– If it is not in the open or closed list, add it.
– If it is in the open list with a higher cost, update its cost.
4. Repeat until the goal node is reached or the open list becomes empty.
Role of Heuristic Function
The heuristic function h(n) is an estimate of the minimum cost required to reach the goal from node
n. Its effectiveness determines the efficiency of A*. There are two desirable properties of a heuristic:
1. Admissibility: The heuristic never overestimates the true cost to reach the goal.
h(n) ≤ h∗ (n)
where h∗ (n) is the actual minimum cost from n to the goal.
2. Consistency (Monotonicity): For every node n and its successor n′ ,
h(n) ≤ c(n, n′ ) + h(n′ )
where c(n, n′ ) is the step cost from n to n′ .
Admissibility of A* Algorithm
Definition: An algorithm is said to be admissible if it is guaranteed to find an optimal solution (i.e.,
the path with the lowest cost), assuming such a solution exists. For A*, admissibility is ensured if:
• The heuristic h(n) is admissible (never overestimates).
• The step cost g(n) is non-negative for all nodes.
Formal Proof of Admissibility
Assumptions:
• Let A* be applied with an admissible heuristic h(n), i.e., h(n) ≤ h∗ (n).
• Let the goal node be denoted by G.
• Let f (n) = g(n) + h(n) for all nodes n.
• Let C ∗ be the actual cost of the optimal path from the start node to the goal.
Proof:
1. Suppose A* finds a suboptimal goal node G such that g(G) > C ∗ .
2. Consider a node n on the optimal path that has not yet been expanded when A* selects G.
3. Since h(n) ≤ h∗ (n), and g(n) is the cost from the start node to n, we get:
f (n) = g(n) + h(n) ≤ g(n) + h∗ (n) = C ∗
4. However,
f (G) = g(G) + h(G) = g(G) since h(G) = 0
Thus, f (G) > C ∗ .
5. This implies f (n) < f (G), and A* should have expanded n before G.
6. But this contradicts the assumption that A* selected G before n.
Conclusion: The assumption that A* finds a suboptimal path is false. Therefore, A* is admissible
and always finds the optimal path, given that the heuristic is admissible and the path costs are non-
negative.
Characteristics of A* Algorithm
Property Description
Completeness Yes, provided the branching factor is finite and each step
cost > 0
Optimality Yes, if h(n) is admissible
Time Complexity Depends on heuristic quality; can be exponential in the
worst case
Space Complexity High; A* maintains all generated nodes in memory
Applications of A*
• Route finding in navigation systems
• Robotic path planning
• Game AI for strategy and decision-making
• Solving logic puzzles and state space problems
