đ¯ What is A*?
A* (A-star) is a best-first search algorithm that finds the least-cost path from a given initial node to one goal node out of one or more possible goals. It uses both the actual distance from the start and a heuristic estimate to guide its search.
⥠How It Works
A* evaluates nodes using the formula:
- g(n): Exact cost from start node to node n
- h(n): Heuristic estimate from node n to goal
- f(n): Estimated total cost of path through n
đ Key Properties
A* is both complete and optimal when the heuristic function is admissible (never overestimates the actual cost). It combines the advantages of Dijkstra's algorithm (guaranteed shortest path) with the efficiency of greedy best-first search.
đ§ Algorithm Steps
- Initialize open list with start node
- Select node with lowest f(n) from open list
- Move selected node to closed list
- Examine each neighbor of current node
- Update costs and continue until goal is reached
đ Real-World Applications
- GPS navigation and route planning
- Video game AI pathfinding
- Robotics and autonomous vehicles
- Network routing protocols
- Puzzle solving and optimization problems
đ Advantages & Complexity
Time Complexity: O(b^d) where b is branching factor
Space Complexity: O(b^d) stores all generated nodes
Advantages: Optimal, complete, and efficient
Invented: 1968 by Peter Hart, Nils Nilsson, Bertram Raphael