A (A-star)* is the most popular and powerful informed search algorithm used in Artificial Intelligence for finding the shortest path from a start node to a goal node in a weighted graph (where edges h

A* Search Algorithm – Complete Explanation

A (A-star)* is the most popular and powerful informed search algorithm used in Artificial Intelligence for finding the shortest path from a start node to a goal node in a weighted graph (where edges have different costs).

It combines the strengths of:

Dijkstra’s Algorithm (guarantees optimal path because it always expands the lowest-cost path so far)
Greedy Best-First Search (uses heuristic to guide search toward the goal quickly)

A* is both complete and optimal if the heuristic is admissible (and consistent for better performance).

Why A* is Better Than Others

Algorithm	Uses Heuristic?	Optimal?	Complete?	Speed (typically)
BFS	No	Yes	Yes	Slow (unweighted)
Dijkstra	No	Yes	Yes	Medium
Greedy Best-First	Yes	No	No	Fast but suboptimal
A*	Yes	Yes	Yes	Very Fast

Key Idea of A*

For every node n, A* computes an evaluation function:

f(n) = g(n) + h(n)

Where:

g(n) = actual (exact) cost from start node to node n (path cost so far)
h(n) = heuristic estimated cost from node n to the goal
f(n) = estimated total cost of a path going through node n

A* always expands the node with the smallest f(n) value (using a priority queue).

Properties Required for Heuristic h(n)

Admissible Heuristic (Must for optimality)
h(n) ≤ true cost from n to goal
→ Never overestimates the real distance
Example: In a map, straight-line (Euclidean) distance or Manhattan distance is admissible.
Consistent (Monotonic) Heuristic (Stronger condition – gives better performance)
For every node n and successor n' of n:
h(n) ≤ cost(n, n') + h(n')
→ Triangle inequality holds
If consistent → A* expands each node at most once (like Dijkstra).

Most real-world problems use consistent heuristics (e.g., Manhattan, Euclidean).

A* Algorithm – Step by Step (Pseudocode)

function A_Star(start, goal):
    open_set   = priority_queue()      # Nodes to be explored (sorted by f(n))
    open_set.insert(start) with f=0
    
    came_from  = {}                    # To reconstruct path
    g_score    = {}                    # Known cost from start to node
    g_score[start] = 0
    
    f_score    = {}                    # Estimated total cost
    f_score[start] = h(start)          # h = heuristic function
    
    while open_set is not empty:
        current = node in open_set with lowest f_score
        
        if current == goal:
            return reconstruct_path(came_from, current)
        
        remove current from open_set
        mark current as closed (or just track visited)
        
        for each neighbor of current:
            tentative_g = g_score[current] + cost(current, neighbor)
            
            if neighbor not visited or tentative_g < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f_score[neighbor] = tentative_g + h(neighbor)
                
                if neighbor not in open_set:
                    open_set.insert(neighbor)
                else:
                    update priority of neighbor in open_set
    
    return failure  # No path exists

Example: 8-Puzzle (or Grid Pathfinding)

Imagine finding shortest path from Bucharest to other cities (Romania map – classic AI example).

City	g(n) (cost so far)	h(n) (straight-line to Bucharest)	f(n) = g+h
Arad	0	366	366
Sibiu	140	253	393
Rimnicu Vilcea	220	193	413
Fagaras	239	176	415 ← expanded next

A* expands nodes in increasing order of f(n).

Time & Space Complexity

Worst case: O(b^d) same as BFS (b = branching factor, d = depth)
With good heuristic: dramatically faster (often exponential speedup)
Space: Keeps all generated nodes in memory → can be a bottleneck

Advantages of A*

Optimal and complete (with admissible heuristic)
Very efficient with good heuristic
Widely used in real applications:
- GPS navigation (Google Maps, etc.)
- Video games (pathfinding for NPCs)
- Robotics
- Puzzle solvers (15-puzzle, Rubik’s cube)

Disadvantages

Memory intensive (stores all open/closed nodes)
Solutions: Use Iterative Deepening A* (IDA*) or Memory-bounded A* (SMA*)

Summary Table: A* vs Others

Feature	BFS	Dijkstra	Greedy BFS	A*
Optimal	Yes	Yes	No	Yes
Complete	Yes	Yes	No	Yes
Uses heuristic	No	No	Yes	Yes
Guaranteed best path	Yes	Yes	No	Yes (if h admissible)
Best for large graphs	No	Medium	Fast	Best

Key Takeaway:
A* is the gold standard for pathfinding when you need the shortest/optimal path and have a reasonable heuristic. It intelligently balances exploring known costs (g) and estimated remaining costs (h).

Master A* → You’ve mastered 80% of real-world pathfinding problems in AI! 🚀